Lexikographische Ordnung

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

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	Silber	Bronze
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

Unendliche Folgen

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

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

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.

Präferenzen

Hat man zwei Präferenzrelationen, so könnte man einen bestehenden Zielkonflikt dadurch auflösen, dass man Paare der Präferenzen lexikographisch anordnet: Werden beide Präferenzen durch reelle Nutzenfunktionen $u_1$ und $u_2$ gegeben, so kann man die Paare der Werte der Nutzenfunktionen lexikographisch anordnen. Demnach ist $x \prec y$ genau dann, wenn $u_1(x)<u_1(y)$ oder $u_1(x)=u_1(y)$ und $u_2(x)<u_2(y)$.

Allerdings kommt man so zu Präferenzen, die sich nicht mehr durch Nutzenfunktionen darstellen lassen. Sind etwa beide gegebenen Präferenzen schon reelle Zahlen und daher die Nutzenfunktionen $u_i$ die identische Abbildung, so führt die oben beschriebene Konstruktion zur lexikographischen Ordnung auf $\R^2$. Diese ist das Standardbeispiel einer nicht durch Nutzenfunktionen repräsentierbaren Anordnung.