Benutzer:Jürgen-Michael Glubrecht/Funktion

Ordnungsrelation

Totalordnung

Aufgabe: Sei $\leq$ eine Totalordnung auf der Menge $M$ und $<$ wie üblich definiert. Zeige:

$\forall x,y\in M:(x<y\Leftrightarrow y\nleq x)$

Beweis:

Gilt $x<y$, so gilt nach Definition $x\leq y$ und $x\neq y$. Aus $x\neq y$ folgt wegen der Antisymmetrie $x\nleq y\lor y\nleq x$. Da $x\nleq y$ nicht gilt, muss $y\nleq x$ gelten. Gelte nun $y\nleq x$. Dann folgt mit der Linearität $x\leq y$. Gälte $x=y$, dann folgte mit der Reflexivität $y\leq x$ ↯. Also gilt $x\neq y$ und insgesamt folgt $x<y$.

Aufgabe: Sei $\leq$ eine transitive binäre Relation auf der Menge $M$ und $<$ wie üblich definiert. Zeige:

Gilt $\forall x,y\in M:(x<y\Leftrightarrow y\nleq x)$, so ist $\leq$ eine Totalordnung auf $M$.

Beweis:

Mit der Definition von $<$ lautet die Voraussetzung:

(*)   $x\leq y\land x\neq y\Leftrightarrow y\nleq x$

Da $\leq$ transitiv ist, sind nur noch die drei anderen Eigenschaften zu zeigen.

Beweisschritt: Reflexivität

Für den Spezialfall $y=x$ ist die linke Seite von (*) immer falsch. Also ist auch die rechte Seite falsch und es gilt die Reflexivität: $x\leq x$.

Beweisschritt: Antisymmetrie

Gelte $x\leq y\land y\leq x$. Dann ist (*) nur wahr, wenn $x=y$ gilt. Das zeigt die Antisymmetrie.

Beweisschritt: Linearität

Gilt $y\leq x$, dann gilt auch $x\leq y\lor y\leq x$, also die Linearität. Gelte nun $y\nleq x$. Dann liefert (*) $x\leq y\land x\neq y$, also ebenfalls die Linearität.

Also ist $\leq$ eine Totalordnung. ✔

Satz

Sei $\leq$ eine Totalordnung auf der Menge $M$. Sei weiterhin die 2-stellige Relation $<$ auf $M$ wie folgt definiert:

• $x<y:\Leftrightarrow x\leq y\land x\neq y$

Dann gilt: $\forall x,y\in M:(x<y\Leftrightarrow y\nleq x)$.

Beweis

Gilt $x<y$, so gilt nach Definition $x\leq y$ und $x\neq y$. Aus $x\neq y$ folgt wegen der Antisymmetrie $x\nleq y\lor y\nleq x$. Da $x\nleq y$ nicht gilt, muss $y\nleq x$ gelten. Gelte nun $y\nleq x$. Dann folgt mit der Linearität $x\leq y$. Gälte $x=y$, dann folgte mit der Reflexivität $y\leq x$ ↯. Also gilt $x\neq y$ und insgesamt folgt $x<y$.

Wohlordnungen

Was brauchen wir zum Zählen?

Die natürlichen Zahlen $\{1,2,3,\dots \}$ benutzen wir zum Zählen. Ist eine beliebige Menge $A$ gegeben, so können wir den Elementen von $A$ der Reihe nach natürliche Zahlen zuordnen: $a_{1},a_{2},a_{3},{\text{ usw.}}$. Haben wir auf diese Weise alle Elemente von $A$ gezählt und sind dabei bei einer Zahl $n$ angekommen, hat $A$ genau $n$ Elemente. Gleichzeitig haben wir die Elemente von $A$ in eine Reihenfolge gebracht. Während die Menge $A$ ungeordnet ist, ist die abgezählte Menge $\{a_{1},a_{2},a_{3},\dots \}$ geordnet. Diese Ordnung ist durch die Ordnungsrelation $<$ auf den natürlichen Zahlen gegeben, denn $<$ ist auf den natürlichen Zahlen eine strikte Totalordnung. Zur Erinnerung:

Definition (strikte Totalordnung)

Eine binäre und homogene Relation $<$ auf einer Menge $A$ heißt strikte Totalordnung, wenn $<$ für alle $x,y,z\in A$ die folgenden Eigenschaften besitzt:

• $x\nless x$ (irreflexiv)
• $x<y\land y<z\Rightarrow x<z$ (transitiv)
• $x<y\ \lor x=y\ \lor y<x$ (konnex)

Verständnisfrage: Zeige:

1. In der letzten Bedingung lässt sich das "oder" ($\lor$) zu "entweder - oder" (${\dot {\lor }}$) verschärfen.
2. Aus der verschärften Bedingung folgt die Irreflivität.

1. Wenn $x<y\land x=y$ oder $y<x\land x=y$ gälte, folgte $x<x$, im Widerspruch zur Irreflivität. Gälte $x<y\land y<x$, folgte mit der Transitivität ebenfalls $x<x$. ↯
2. Gelte nun $x<y\ \;{\dot {\lor }}\ \;x=y\;{\dot {\lor }}\ \;y<x$. Dann gilt wegen $x=x$ auch $\neg (x<x)$, also $x\nless x$.

Nun ist $<$ auch auf den ganzen Zahlen $\mathbb {Z}$ und auf den reellen Zahlen $\mathbb {R}$ eine strikte Totalordnung. Aber zum Zählen sind diese Ordnungen nicht zu gebrauchen. Warum? Was benötigen wir eigentlich zum Zählen? Wir brauchen dazu zwei Bedingungen:

• ein eindeutiges Element für den Anfang,
• einen eindeutiges nächstes Element, um weiterzuzählen, wenn wir schon eine Weile gezählt haben.

Aber $\mathbb {Z}$ und $\mathbb {R}$ haben keinen eindeutigen Anfang und $\mathbb {R}$ hat auch keinen eindeutigen Nachfolger. Wenn aber für die strikte Totalordnung gilt:

(*)   jede nichtleere Teilmenge hat ein kleinstes Element,

dann gelten die oben genannten Bedingungen für das Zählen:

• das kleinste Element der strikten Totalordnung ist der Anfang,
• mit dem kleinsten Element der Menge der Elemente der Totalordnung, die wir noch nicht zum Zählen genutzt haben, zählen wir weiter.

Eine strikte Totalordnung, die zum Zählen geeignet ist, wird Wohlordnuing genannt.

Definition der Wohlordnung

Definition (Wohlordnung)

Eine strikte Totalordnung $<$ auf der Menge $A$ ist eine Wohlordnung genau dann, wenn jede nichtleere Teilmenge ein kleinstes Element hat:

• $\forall z\subseteq A:(\varnothing \neq z\Rightarrow \exists x\in z\;\forall y\in z:x\leq y)$

Dabei ist $\leq$ definiert als $x\leq y:\Leftrightarrow x<y\lor x=y$.

Die Bedingung des kleinsten Elements ist in einer strikten Totalordnung gleichwertig zur der Bedingung, dass jede nichtleere Teilmenge von A ein minmales Element hat:

(**)   $\forall z\subseteq A:(\varnothing \neq z\Rightarrow \exists x\in z\;\forall y\in z:y\nless x)$

Verständnisfrage: Zeige: in einer strikten Totalordnung gilt (*) $\Longleftrightarrow$ (**).

Sei $\varnothing \neq z\subseteq A$ und gelte $x,y\in z$. In einer strikten Totalordnung gilt $x<y\;{\dot {\lor }}x=y\;{\dot {\lor }}\;y<x$. Mit (*) gilt $x<y\lor x=y$, also auch $y\nless x$, also (**). Gilt umgekehrt $y\nless x$, sind nur noch die beiden anderen Fälle möglich: $x<y\lor x=y$.

Satz

Die natürlichen Zahlen $\mathbb {N} _{0}$ sind mit der Echt-Kleiner-Relation $<$ eine Wohlordnung.

Beweis

$\mathbb {N} _{0}$ ist mit $<$ eine strikte Totalordnung, vgl. Kapitel Ordnungsrelation.

Wir zeigen, dass jede nichtleere Teilmenge $A\subset \mathbb {N} _{0}$ ein kleinstes Element hat. Annahme: $A$ hat kein kleinstes Element. Wir müssen dann zeigen: $A=\varnothing$. Dazu definieren wir $B:=\mathbb {N} _{0}\setminus A$ und zeigen durch Induktion über $n$:

Induktionsbehauptung: $\forall n\in \mathbb {N} _{0}:n\in B$

Induktionsanfang: $0\in B$, denn da $A$ kein kleinstes Element hat, gilt $0\notin A$.

Induktionsschritt: Gelte $\forall m\leq n:n\in B$. Wäre $n+1\in A$, so wäre $n+1$ das kleinste Element in $A$, denn alle kleineren Elemente von $n+1$ liegen ja in $B$. Also gilt $n+1\in B$.

Damit ist die Induktionsbehauptung bewiesen. Daher ist $B=\mathbb {N} _{0}$ und weil $B$ als $B=\mathbb {N} _{0}\setminus A$ definiert war, folgt $A=\varnothing$. ✔

Folgerung: Jede Teilmenge von $\mathbb {N} _{0}$ ist eine Wohlordnung.

Sei $A\subseteq \mathbb {N} _{0}$. Die Einschränkung von $<$ auf $A$ ist eine strikte Totalordnung. Weiterhin haben wir gerade bewiesen, dass jede Teilmenge von $\mathbb {N} _{0}$ ein kleinstes Element hat, insbesondere also auch jede Teilmenge von $A$.

Die ganzen Zahlen $\mathbb {Z}$ mit der Relation $<$ sind keine Wohlordnung, denn $\mathbb {Z}$ hat kein kleinstes Element. Wir können aber eine modifizierte Ordnung $\sqsubset$ auf $\mathbb {Z}$ definieren, so dass $\sqsubset$ eine Wohlordnung ist. Die Idee ist folgende: alle negativen Zahlen sind größer als alle postiven Zahlen, für die positiven Zahlen einschließlich der Null stimmt $\sqsubset$ mit $<$ überein, für die negativen Zahlen setzen wir $x\sqsubset y:\Leftrightarrow y<x$. In aufzählender Schreibweise lässt sich das so darstellen:

• $\{0,1,2,3,\dots ,-1,-2,-3,\dots \}$

Satz (Beispiel)

Auf den ganzen Zahlen $\mathbb {Z}$ sei die 2-stellige Relation $\sqsubset$ wie folgt definiert:

$x\sqsubset y:=\{x,y\in \mathbb {Z} \,|\,(x\geq 0\land y\geq 0\land x<y)\lor (x\geq 0\land y<0)\lor (x<0\land y<0\land y<x)\}$

Dann ist $\sqsubset$ eine Wohlordnung auf $\mathbb {Z}$

Beweis (Beispiel)

$x\sqsubset y\;{\dot {\lor }}\;x=y\;{\dot {\lor }}y\;\sqsubset x$ ergibt sich aus der Definition indem die einzelnen Fälle betrachtet werden. Wir zeigen die Transitivität: Sei $x\sqsubset y\land y\sqsubset z$. Sei $x\geq 0$ und $y\geq 0$. Ist $z<0$ gilt $x\sqsubset z$, anderenfalls folgt die Transitivität mit der Transitivität von $<$. Ist $x\geq 0$ und $y<0$, so muss auch $z<0$ sein, als gilt $x\sqsubset z$. Ist schließlich $x<0$ , so sind auch $y<0$ und $z<0$. Dann ergibt sich die Transitivität aus der Transitivität von $>$.

Sei $z$ eine nichtleere Teilmenge von $\mathbb {Z}$. Hat $z$ Elemente aus den positiven Zahlen einschließlich $0$, so ist das kleinste Elelement bezüglich $<$ auch das kleinste Element bezüglich $\sqsubset$. Enthält $z$ nur negative Zahlen, so gibt es ein größtes Element $x\in \mathbb {Z}$ bezüglich $>$. Für $x$ gilt also $\forall y\in z:z<x$. Das heißt aber nach Definition von $\sqsubset$ gerade $\forall y\in z:x\sqsubset z$. ✔