Lösung für Aufgabe 4.2.27
Seien die geordneten Mengen
)
)
B\begin{equation*}
(a,b)\unlhd(a',b'):\liff a < a' \vee (a=a' \wedge b\preceq b').
\end{equation*}
Zeigen Sie, dass \unlhd eine Ordnungsrelation auf A\x B
definiert, die so genannte lexikographische Ordnung.
Wir weisen die erforderlichen Eigenschaften nach:
- Reflexivität: Sei (a,b)\in A\times B. Wegen a=a und b\preceq b (\preceq ist eine Ordnungsrelation) gilt (a,b)\unlhd(a,b).
- Antisymmetrie: Sei (a,b),(a',b')\in A\times B, und es gelte (a,b)\unlhd(a',b') und (a',b')\unlhd(a,b). Es muss a=a' sein, da nicht beide a < a' und a' < a gelten können, weil < als Ordnungsrelation antisymmetrisch ist. Daraus folgen aber b\preceq b' und b'\preceq b, und aus der Antisymmetrie von \preceq erhalten wir b=b', und damit gilt (a,b)=(a',b').
- Transitivität: Seien (a,b),(a',b'),(a'',b'')\in A\times B mit (a,b)\unlhd(a',b') und (a',b')\unlhd(a'',b''). Wir unterscheiden im Beweis zwei Fälle: Gilt zunächst a < a' oder a' < a'', so folgt aus Transitivität und Reflexivität von <, dass a < a'' gilt, und damit (a,b)\unlhd(a'',b''). Haben wir andererseits, dass a=a'=a'', dann wissen wir b\preceq b' und b'\preceq b''. In diesem Fall folgt aus der Transitivität von \preceq, dass b\preceq b'', und mit a=a'' sofort (a,b)\unlhd(a'',b'').
Die lexikographische Ordnung trägt ihren Namen im Übrigen wegen der Tatsache, dass Wörter in Lexika nach diesem Schema geordnet werden.