Lexikographische Ordnung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die lexikographische Ordnung ist eine Methode, um aus einer linearen Ordnung für einfache Objekte, beispielsweise alphabetisch angeordnete Buchstaben, eine lineare Ordnung für zusammengesetzte Objekte, beispielsweise aus Buchstaben zusammengesetzte Wörter, zu erhalten. Das namengebende Beispiel ist die Anordnung der Wörter in einem Lexikon: Sie werden zunächst nach ihren Anfangsbuchstaben sortiert, dann die Wörter mit gleichen Anfangsbuchstaben nach dem jeweils zweiten Buchstaben usw. Ist ein Wort ganz in einem anderen als Anfangsteil enthalten (wie beispielsweise „Tal“ in „Talent“), so wird das kürzere Wort zuerst aufgeführt.

Definition und Beispiele[Bearbeiten | Quelltext bearbeiten]

Formal kann diese Ordnung wie folgt beschrieben werden: Eine Zeichenkette ist kleiner als eine Zeichenkette (d. h. liegt in der Sortierung vor ), wenn

  • entweder das erste Zeichen von , in dem sich beide Zeichenketten unterscheiden, kleiner ist als das entsprechende Zeichen von ,
  • oder wenn den Anfang von bildet, aber kürzer ist.

Ein Spezialfall dieser Ordnung ist die lexikographische Ordnung endlicher Folgen einer festen Länge. Beispielsweise ist ein geordnetes Paar lexikographisch kleiner als ein Paar , wenn

  • entweder
  • oder und

gilt.

Ein Beispiel für eine derartige Ordnung ist die zeitliche Reihenfolge für Zahlentripel (Jahr, Monat, Tag): Ein Datum X ist früher als ein anderes Datum Y, wenn

  • entweder die Jahreszahl von X kleiner ist als die Jahreszahl von Y
  • oder die Jahreszahlen gleich sind, aber X in einem im Jahresverlauf früheren Monat liegt
  • oder die Jahreszahlen und Monate gleich sind, aber der Tag von X kleiner als der Tag von Y ist.

Ein weiteres Beispiel ist die übliche Rangfolge innerhalb eines Medaillenspiegels, bei der als erstes Kriterium die Anzahl der Goldmedaillen ausschlaggebend ist, bei gleicher Goldmedaillenzahl die Anzahl der Silbermedaillen und bei nochmaligem Gleichstand die Anzahl der Bronzemedaillen:

Land Gold Gold medal-2008OB.svg Silber Silver medal-2008OB.svg Bronze Bronze medal-2008OB.svg
Land 1 10 5 7
Land 2 8 7 4
Land 3 8 5 7
Land 4 5 3 7
Land 5 5 3 2

Mathematische Verwendung[Bearbeiten | Quelltext bearbeiten]

Unendliche Folgen[Bearbeiten | Quelltext bearbeiten]

Analog lässt sich die lexikographische Ordnung auch auf unendlichen Folgen definieren: Eine Folge ist lexikographisch kleiner als eine Folge wenn beide Folgen vor einem bestimmten Index k gleich sind aber . Nehmen z. B. die Folgenglieder die Ziffern an, so kann die Folge als ein Dezimalbruch interpretiert werden, der eine reelle Zahl zwischen und darstellt. Die lexikographische Ordnung der Folgen entspricht im Wesentlichen der natürlichen Ordnung der reellen Zahlen. Man muss dabei nur beachten, dass ein Dezimalbruch, der schließlich nur noch die Ziffer annimmt, lexikographisch einen unmittelbaren Nachfolger hat, der die gleiche reelle Zahl darstellt. (z. B. )

Weitere Verallgemeinerung[Bearbeiten | Quelltext bearbeiten]

Das Prinzip kann weiter ausgedehnt werden auf Folgen, in denen der Indexbereich eine beliebige wohlgeordnete Menge ist. In diesem Fall definiert man für Funktionen (wobei linear geordnet ist), falls für das minimale Element des Definitionsbereiches , für das sich und unterscheiden, gilt. Die so entstandene Ordnung auf den Funktionen ist wieder linear geordnet.

Anwendung: Ketten in der Potenzmenge einer Ordinalzahl[Bearbeiten | Quelltext bearbeiten]

In der Mengenlehre wird oft der Spezialfall betrachtet, bei dem die Indexmenge eine Ordinalzahl ist und die Folgenglieder nur die Werte oder annehmen. Diese Grundmenge wird mit bezeichnet und sie steht in einer bijektiven Beziehung zu der Potenzmenge von . Eine Ordinalzahl wird immer als die Menge ihrer Vorgänger-Ordinalzahlen gesehen. Einer Teilmenge von kann man die Funktion zuordnen für die , wenn und , wenn . Umgekehrt kommt man von einer Funktion mit der Menge wieder zu einer Teilmenge von . Wir betrachten jetzt mit der lexikographischen Ordnung, wie sie oben definiert wurde. Diese lineare Ordnung kann für kombinatorische Fragen über unendliche Kardinalzahlen verwendet werden. Es gilt:

Für jede wohlgeordnete Teilmenge von gilt .

Zum Beweis durch Induktion nehmen wir an, dass die Aussage für alle Ordinalzahlen bereits gegeben ist. Ist so betrachten wir die Einschränkungen der Funktionen auf die Teilmenge . Die Mengen sind dann wohlgeordnete Teilmengen der lexikographisch geordneten Mengen . Aus der Induktionsvoraussetzung folgt, dass . Jetzt nehmen wir wieder ein f in der wohlgeordneten Menge und betrachten auch den direkten Nachfolger . Wir definieren als das kleinste mit . Dann gilt für stets sowie und . Zwei Funktionen und in mit müssen sich schon unterhalb von unterscheiden. Nehmen wir an, dass gilt. Dann ist , , und . Daraus folgt, dass in der lexikographischen Ordnung auch und gilt und folglich und , also . Die Mengen für ein gegebenes werden also jeweils durch die Einschränkung auf injektiv auf eine Teilmengen von abgebildet und haben somit auch nur eine Mächtigkeit . Da aber , ist bewiesen.

Anwendung in der Mikroökonomik[Bearbeiten | Quelltext bearbeiten]

→ Siehe auch: Präferenzrelation

Sei durch mit das Güterbündel / die Alternative gegeben und mit die Alternative ( ist entsprechend beispielsweise die Menge von Gut 2 im Güterbündel ). Man bezeichnet eine Präferenz-Indifferenz-Relation R als lexikographisch, wenn dann und nur dann, wenn entweder oder und zugleich .[1] Mit anderen Worten wird bei einer lexikographischen Präferenz-Indifferenz-Relation ein Güterbündel nur dann schwach gegenüber einem zweiten vorgezogen (das heißt als mindestens so gut wie dieses angesehen), wenn es mehr Einheiten vom ersten Gut enthält oder hilfsweise, falls beide Güterbündel gleich viele Einheiten von diesem Gut umfassen, wenn es mehr Einheiten vom zweiten Gut beinhaltet.

Eigenschaften der lexikographischen Präferenzenordnung[2]:

  1. Eine lexikographische Präferenzenordnung ist vollständig, asymmetrisch (und folglich auch antisymmetrisch), negativ transitiv und transitiv. (Zur Definition der Eigenschaften wird auf den Artikel Präferenzrelation verwiesen.)
  2. (Debreu 1959[3]:) Eine lexikographische Präferenzenordnung kann nicht durch eine Nutzenfunktion repräsentiert werden.

Literatur[Bearbeiten | Quelltext bearbeiten]

Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  1. Vgl. Mas-Colell/Whinston/Green 1995, S. 46.
  2. Vgl. Moore 2007, S. 14.
  3. Gerard Debreu: Theory of value. An axiomatic analysis of economic equilibrium. John Wiley & Sons, New York 1959.