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]

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

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

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

  • entweder a_1<b_1
  • oder a_1=b_1 und a_2<b_2

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]

Unendliche Folgen[Bearbeiten]

Analog lässt sich die lexikographische Ordnung auch auf unendlichen Folgen definieren: Eine Folge (s_i)_{i\in\mathbb{N}} ist lexikographisch kleiner als eine Folge (t_i)_{i\in\mathbb{N}} wenn beide Folgen vor einem bestimmten Index k gleich sind aber s_k < t_k. Nehmen z. B. die Folgenglieder die Ziffern 0,1,2,3,4,5,6,7,8,9 an, so kann die Folge als ein Dezimalbruch interpretiert werden, der eine reelle Zahl zwischen 0 und 1 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 9 annimmt, lexikographisch einen unmittelbaren Nachfolger hat, der die gleiche reelle Zahl darstellt. (z. B. 0,1399999... = 0,1400000... )

Weitere Verallgemeinerung[Bearbeiten]

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

Anwendung: Ketten in der Potenzmenge einer Ordinalzahl[Bearbeiten]

In der Mengenlehre wird oft der Spezialfall betrachtet, bei dem die Indexmenge eine Ordinalzahl \lambda ist und die Folgenglieder nur die Werte 0 oder 1 annehmen. Diese Grundmenge wird mit 2^\lambda bezeichnet und sie steht in einer bijektiven Beziehung zu der Potenzmenge von \lambda. Eine Ordinalzahl wird immer als die Menge ihrer Vorgänger-Ordinalzahlen gesehen. Einer Teilmenge X von \lambda kann man die Funktion f_X\in2^\lambda zuordnen für die f_X(\sigma)=1, wenn \sigma\in{X} und f_X(\sigma)=0, wenn \sigma\not\in{X}. Umgekehrt kommt man von einer Funktion f\in2^\lambda mit der Menge \{\sigma\in\lambda : f(\sigma)=1\} wieder zu einer Teilmenge von \lambda . Wir betrachten jetzt 2^\lambda 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 S von 2^\lambda gilt |S|\le|\lambda| .

Zum Beweis durch Induktion nehmen wir an, dass die Aussage für alle Ordinalzahlen <\lambda bereits gegeben ist. Ist \mu<\lambda so betrachten wir die Einschränkungen f\mid_\mu der Funktionen f\in2^\lambda auf die Teilmenge \mu=\{\nu<\mu\}. Die Mengen S_\mu=\{f\mid_\mu : f\in{S}\} sind dann wohlgeordnete Teilmengen der lexikographisch geordneten Mengen 2^\mu . Aus der Induktionsvorausetzung folgt, dass |S_\mu|\le|\mu|\le|\lambda|. Jetzt nehmen wir wieder ein f in der wohlgeordneten Menge S\subseteq2^\lambda und betrachten auch den direkten Nachfolger f^+\in{S}. Wir definieren \mu_f als das kleinste \mu\in\lambda mit f(\mu){\ne}f^+(\mu). Dann gilt für \mu<\mu_f stets f(\mu)=f^+(\mu) sowie f(\mu_f)=0 und f^+(\mu_f)=1 . Zwei Funktionen f und g in 2^\lambda mit \mu_f=\mu=\mu_g müssen sich schon unterhalb von \mu unterscheiden. Nehmen wir an, dass f\mid_\mu=g\mid_\mu gilt. Dann ist f(\mu)=0, g(\mu)=0, f^+(\mu)=1 und g^+(\mu)=1. Daraus folgt, dass in der lexikographischen Ordnung auch f<g^+ und g<f^+ gilt und folglich f{\le}g und g{\le}f , also f=g . Die Mengen \{f\in2^\lambda : \mu_f=\mu\} für ein gegebenes \mu\in\lambda werden also jeweils durch die Einschränkung auf \mu injektiv auf eine Teilmengen von S_\mu abgebildet und haben somit auch nur eine Mächtigkeit \le\lambda. Da aber S=\bigcup_{\mu\in\lambda} \{f{\in}S : \mu_f=\mu\} ist |S|\le|\lambda|\cdot|\lambda|=|\lambda| bewiesen.

Anwendung in der Mikroökonomik[Bearbeiten]

→ Siehe auch: Präferenzrelation

Sei durch \mathbf{x}_{i}=\left(x_{i}^{1},x_{i}^{2},\ldots,x_{i}^{m}\right) mit i=a das Güterbündel / die Alternative \mathbf{x}_{a} gegeben und mit i=b die Alternative \mathbf{x}_{b} (x_{b}^{2} ist entsprechend beispielsweise die Menge von Gut 2 im Güterbündel \mathbf{x}_{b}). Man bezeichnet eine Präferenz-Indifferenz-Relation R als lexikographisch, wenn \mathbf{x}_{a}R\mathbf{x}_{b} dann und nur dann, wenn entweder x_{a}^{1}>x_{b}^{1} oder x_{a}^{1}=x_{b}^{1} und zugleich x_{a}^{2}\geq x_{b}^{2}.[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]

Anmerkungen[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.