Lexikographische Ordnung

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.

Inhaltsverzeichnis

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 (a1,a2) lexikographisch kleiner als ein Paar (b1,b2), wenn

  • entweder a1 < b1
  • oder a1 = b1 und a2 < b2

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 sk < tk. 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 λ ist und die Folgenglieder nur die Werte 0 oder 1 annehmen. Diese Grundmenge wird mit 2λ 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 X von λ kann man die Funktion f_X\in2^\lambda zuordnen für die fX(σ) = 1, wenn \sigma\in{X} und fX(σ) = 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 λ . Wir betrachten jetzt 2λ 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λ gilt |S|\le|\lambda| .

Zum Beweis durch Induktion nehmen wir an, dass die Aussage für alle Ordinalzahlen < λ bereits gegeben ist. Ist μ < λ so betrachten wir die Einschränkungen f\mid_\mu der Funktionen f\in2^\lambda auf die Teilmenge μ = {ν < μ}. Die Mengen S_\mu=\{f\mid_\mu : f\in{S}\} sind dann wohlgeordnete Teilmengen der lexikographisch geordneten Mengen 2μ . 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 μf als das kleinste \mu\in\lambda mit f(\mu){\ne}f^+(\mu). Dann gilt für μ < μf stets f(μ) = f + (μ) sowie ff) = 0 und f +f) = 1 . Zwei Funktionen f und g in 2λ mit μf = μ = μg müssen sich schon unterhalb von μ unterscheiden. Nehmen wir an, dass f\mid_\mu=g\mid_\mu gilt. Dann ist f(μ) = 0, g(μ) = 0, f + (μ) = 1 und g + (μ) = 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 μ injektiv auf eine Teilmengen von Sμ 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 u1 und u2 gegeben, so kann man die Paare der Werte der Nutzenfunktionen lexikographisch anordnen. Demnach ist x \prec y genau dann, wenn u1(x) < u1(y) oder u1(x) = u1(y) und u2(x) < u2(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 ui 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.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lexikographische Präferenzordnung — Die lexikographische Präferenzordnung ist eine Präferenzordnung, die der Ordnung in einem Lexikon entspricht. Geht man von einem (papierbasiertem) Lexikon aus, so werden die Wörter geordnet, indem die Ordnung des Alphabets zugrunde gelegt wird.… …   Deutsch Wikipedia

  • Strenge schwache Ordnung — Eine strenge schwache Ordnung ist eine Ordnungsrelation, die mehrere gleichartige Objekte erlaubt, sonst aber eine eindeutige Reihenfolge definiert. Beispiel: Die Relation A kostet weniger als B ist eine strenge schwache Ordnung: Zwei oder… …   Deutsch Wikipedia

  • Lexikographisch — Die lexikographische Ordnung ist in der Informatik und Mathematik eine Methode, um aus einer linearen Ordnung für einfache Objekte (beispielsweise Buchstaben angeordnet nach dem Alphabet) eine lineare Ordnung für zusammengesetzte Objekte… …   Deutsch Wikipedia

  • Präferenzrelation — Eine strenge schwache Ordnung ist eine Ordnungsrelation, die mehrere gleichartige Objekte erlaubt, ansonsten aber eine eindeutige Reihenfolge definiert. Beispiel: Die Relation A kostet weniger als B ist eine strenge schwache Ordnung: Zwei oder… …   Deutsch Wikipedia

  • Sortieralgorithmen — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Sortieralgorithmus — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Dominanzprinzip — Von Entscheidungen unter Sicherheit spricht man im Rahmen der Entscheidungstheorie dann, wenn der Entscheidungsträger den eintretenden Umweltzustand mit Sicherheit kennt (wj = 1) und er also sämtliche Konsequenzen aus einer Handlung voraussagen… …   Deutsch Wikipedia

  • Entscheidung unter Sicherheit — Von Entscheidungen unter Sicherheit spricht man im Rahmen der Entscheidungstheorie dann, wenn der Entscheidungsträger den eintretenden Umweltzustand mit Sicherheit kennt (wj = 1) und er also sämtliche Konsequenzen aus einer Handlung voraussagen… …   Deutsch Wikipedia

  • Zustandsdominanz — Von Entscheidungen unter Sicherheit spricht man im Rahmen der Entscheidungstheorie dann, wenn der Entscheidungsträger den eintretenden Umweltzustand mit Sicherheit kennt (wj = 1) und er also sämtliche Konsequenzen aus einer Handlung voraussagen… …   Deutsch Wikipedia

  • Sommer-Paralympics 1960/Medaillenspiegel — Diese Tabelle zeigt den Medaillenspiegel der Sommer Paralympics 1960. Die Platzierungen sind nach der Anzahl der gewonnenen Goldmedaillen sortiert, gefolgt von der Anzahl der Silber und Bronzemedaillen (lexikographische Ordnung). Weisen zwei oder …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”