Ordnung/Lexikographisch/Definiere/Aufgabe/Kommentar

Wie in Beispiel erläutert, stammt der Name „lexikographische Ordnung“ von der Art und Weise, wie Wörter in einem Wörterbuch angeordnet sind. Wenn z.B. ${}A$ das deutsche Alphabet ist, dann ist ${}A\cup \{\mathrm {\textvisiblespace} \}$ eine geordnete Menge mit der offensichtlichen totalen Ordnung:

    ${}\mathrm {\textvisiblespace}$ < a < ä < b < c < ${}\cdots$ < x < y < z,

wobei ${}\mathrm {\textvisiblespace}$ das Leerzeichen bezeichnet. Diese Ordnung induziert die sogenannte „lexikographische Ordnung“ auf die Menge aller deutschen Wörter, die verwendet wird, um Wörter in einem Wörterbuch anzuordnen: wenn man zwei Wörter ${}W_{1}$ und ${}W_{2}$ (z.B. ${}W_{1}$ = "Vorlesung" und ${}W_{2}$ = "Vorlesen") vergleichen möchte, werden die Wörter zunächst als gleich lang angesehen, indem dem kürzeren Wort Leerzeichen hinzugefügt werden (z.B. ${}W_{1}$ = "Vorlesung" und ${}W_{2}$ = "Vorlesen${}\mathrm {\textvisiblespace}$"). Dann definiert man ${}W_{1}<W_{2}$ (d.h. ${}W_{1}$ kommt vor ${}W_{2}$ in einem Wörterbuch, das beide Wörter enthält) wenn an der ersten Stelle von vorne gelesen, wo sich ${}W_{1}$ und ${}W_{2}$ unterscheiden, der Buchstabe von ${}W_{1}$ an dieser Stelle kleiner als der Buchstaben von ${}W_{2}$ an dieser Stelle ist (also "Vorlesen" < "Vorlesung", da V = V, o = o, r = r, l = l, e = e, s = s, e < u).

Die obigen Überlegungen können direkt auf jede total geordnete Menge ${}A$ erweitert werden: Für ${}x,y\in A^{n}$ mit ${}x=(a_{1},\dots ,a_{n}),y=(b_{1},\dots ,b_{n})$ definiert man ${}x\leq y$ falls ${}x=y$ oder ein ${}j\in \{1,\dots ,n\}$ existiert mit

$a_{1}=b_{1},a_{2}=b_{2},\dots ,a_{j-1}=b_{j-1},a_{j}<b_{j}.$

Man überprüft leicht, dass dies eine Ordnung auf ${}A^{n}$ ist. Die Linearität sieht man so: wenn ${}x\neq y$, dann existiert ein ${}j\in \{1,\dots ,n\}$ mit ${}a_{j}\neq b_{j}$. Da ${}A$ eine total geordnete Menge ist, gilt entweder ${}a_{j}<b_{j}$ oder ${}b_{j}<a_{j}$. Somit ist entweder ${}x<y$ oder ${}y<x$.

Zur kommentierten Aufgabe