3.6 Der Trichotomiesatz
3.6 Der Trichotomiesatz
Rekapitulieren wir: für zwei Mengen $A$ und $B$ schreiben $A \leq B$, wenn es eine injektive Funktion $f : A \rightarrow B$ gibt. Das $\leq$ schaut wie eine Partialordnung aus.
Es ist reflexiv, weil $A \leq A$ gilt: Die Identität ${\rm id}_A: A \rightarrow A$ ist injektiv.
Es ist transitiv, weil aus $A \leq B$ und $B \leq C$ folgt, dass $A \leq C$: Wenn $f: A \rightarrow B$ und $g: B \rightarrow C$ injektiv sind, dann ist $g \circ f: A \rightarrow C$, $a \mapsto g(f(a))$ auch injektiv.
Es ist (so gut wie) antisymmetrisch, weil aus $A \leq B$ und $B \leq A$ zwar nicht $A = B$ folgt, aber laut Schröder-Bernstein-Theorem immerhin $A \approx B$.
Wenn wir also equipotente Mengen als identifisch betrachten, dann ist $\leq$ tatsächlich eine Partialordnung. Ist es eine totale Ordnung? Gilt also immer $A \leq B$ oder $B \leq A$? Dies klingt offensichtlich, ist es aber nicht. Aber wahr ist es, wenn auch nicht ganz einfach zu beweisen.
Theorem 3.6.1 (Trichotomiesatz der Mengenlehre). Seien $A$ und $B$ zwei Mengen. Dann gibt es eine injektive Funktion $f : A \rightarrow B$ oder eine injektive Funktion $g : A \rightarrow B$. Es gilt also immer genau einer der drei folgenden Fälle:
$A \lt B$,
$A \approx B$,
$A \gt B$.
(Unvollständiger) Beweis. Will man ein Objekt mit gewissen Eigenschaften (hier: Funktion, injektiv) konstruieren, so lohnt es sich oft, die gestellten Bedingungen zu relaxieren und sich langsam zu einer "richtigen" Lösung hinzutasten. Wir müssen zuerst uns in Erinnerung rufen, was eine Funktion formal ist. $A \times B := \{ (a,b) \ | \ a \in A, b \in B\}$, die Menge aller Paare, heißt das cartesische Produkt. Eine Relation ist eine Teilmenge $R \subseteq A \times B$.
Definition Eine Relation $R \subseteq A \times B$ heißt
Funktion, wenn es für jedes $a \in A$ genau ein $b \in B$ mit $(a,b) \in R$ gibt; wir schreiben dann üblicherweise $f$ statt $R$ und schreiben $f(a)$, um dieses $b$ zu benennen.
Matching, wenn es für jedes $a \in A$ höchstens ein $b \in B$ gibt mit $(a,b) \in R$ und umgekehrt für jedes $b \in B$ höchstens ein $a \in A$ mit $(a,b) \in R$.
Wenn $R$ ein Matching ist, dann sättigt $R$ die Menge $A$, wenn es für jedes $a \in A$ ein $b \in B$ mit $(a,b) \in R$ gibt; es sättigt $B$ , wenn es für jedes $b \in B$ ein $a \in A$ gibt mit $(a,b) \in R$.
Wir beobachten: wenn $R$ ein Matching ist und die Menge $A$ sättigt, dann ist $R$ eine injektive Funktion, und umgekehrt. Wenn $R$ ein Matching ist und sowohl $A$ als auch $B$ sättigt, dann ist $R$ eine bijektive Funktion. Wir betrachten nun die Menge $\mathcal{M}$ aller Matchings in $A \times B$:
$(\mathcal{M}, \subseteq)$ ist eine Partialordnung.
Beobachtung Wenn $R \in \mathcal{M}$ ein maximales Element in der Partialordnung $(\mathcal{M}, \subseteq)$ ist, dann sättigt es $A$ oder $B$ (oder beide). Wenn es $A$ sättigt, dann ist es eine injektive Funktion $A \rightarrow B$ und es gilt somit $A \leq B$ . Wenn es $B$ sättigt, dann ist $R^{-1} := \{ (b,a) \ | \ (a,b) \in R\}$ eine injektive Funktion $B \rightarrow A$ und es gilt $B \leq A$.
Beweis. Nehmen wir an, dass es weder $A$ noch $B$ sättigt. Dann gibt es also ein $a \in A$, das mit keinem $b' \in B$ "gepaart" ist, und auch ein $b \in B$, das mit keinem $a' \in A$ gepaart ist. Also ist $R \cup \{(a,b)\}$ auch ein Matching, und $R$ ist nicht maximal.A\(\square\)
Wir bekommen also unsere gewünschte injektive Funktion, solange wir ein maximales Element in der Partialordnung $(\mathcal{M}, \subseteq)$ vorweisen können. Aber Vorsicht: nicht jede Partialordnung hat ein maximales Element! Ein Gegenbeispiel ist $(\N, \leq)$. Es gibt immer größere natürliche Zahlen, aber kein maximales Element. Die Gefahr ist also, dass es unendliche aufsteigende Folgen $a_1 \lt a_2 \lt a_3 \t \dots$ geben kann, für die man keine obere Schranke findet.
Definition Sei $(X, \preceq)$ eine Partialordnung und $S \subseteq X$ eine Menge. Ein Element $x \in X$ ist eine obere Schranke für $S$ wenn
gilt. Dabei ist unerheblich, ob die obere Schranke $x$ selbst in $S$ ist oder nicht.
Die unendliche aufsteigende Folge $1,2,3,\dots$ hat keine obere Schranke in $\N$. Somit gibt es auch kein maximales Element. Was nun mit $(\mathcal{M}, \subseteq)$? Wenn $M_1 \subseteq M_2 \subseteq M_3 \subseteq \dots$ eine unendliche Folge von Matchings ist, dann können wir die doch alle zusammenwerfen: $M_1 \cup M_2 \cup M_3 \cup \dots$ und erhalten ein (vielleicht) größeres. Dies gilt nicht nur für unendliche Folgen, sondern ganz allgemein für Ketten in dieser Partialordnung (also Mengen paarweise vergleichbarer Elemente).
Beobachtung Sei $S \subseteq \mathcal{M}$ eine Kette in $(\mathcal{M}, \subseteq)$, also eine Menge von Matchings, so dass für alle $M_1, M_2 \in S$ gilt: $M_1 \subseteq M_2$ oder $M_2 \subseteq M_1$. Dann ist
selbst ein Matching.
Wir gehen nun wie folgt vor: wir starten mit einem beliebigen $M_0 \in \mathcal{M}$; solange dies nicht maximal ist, finden wir ein größeres: $M_1 \supsetneq M_0$; und wieder und wieder. Dies ergibt im schlimmsten Fall eine unendliche Folge $M_0 \subsetneq M_1 \subsetneq ...$ Wir bilden nun $M'_0 := M_0 \cup M_1 \cup \dots$, was wiederum ein Matching ist. Nun ist aber eventuell $M'_0$ wieder nicht maximal, und wir finden $M'_1 \supsetneq M'_0$ und so weiter. Wir müssen also diesen "Schritt zur Unendlichkeit" wiederholen, selbst wiederum unendlich mal. Endet das irgendwann? Die Antwort ist "ja", allerdings brauchen wir dafür ein großes Geschütz:
Zornsches Lemma. Sei $(X, \preceq)$ eine Partialordnung. Wenn jede Kette $S \subseteq X$ eine obere Schranke $x \in X$ hat, dann enthält $X$ mindestens ein maximales Element. Wir sind nun fertig! Wir können das Zornsche Lemma auf $(\mathcal{M}, \subseteq)$ anwenden und erhalten ein maximales Matching. Dies sättigt $A$ oder $B$ und gibt uns somit eine injektive Funktion $A \rightarrow B$ oder $B \rightarrow A$.
Glauben Sie das, was das Zornsche Lemma besagt? Bei unendlichen Mengen verlässt und leider schnell die Intuition, oder schlimmer: sie wird trügerisch. Gegen Ende des 19. Jahrhunderts tauchten in der Mathematik, insbesondere in der Analysis und Geometrie, mehr und mehr "paradoxe" Ergebnisse auf, die irgendwie "nicht wahr sein konnten". Man begann, an der mathematischen Intuition zu zweifeln und wollte ein genaues Regelwerk definieren, welche Rechen- und Beweisschritte in der Mathematik erlaubt seien. In moderner Sprache: wann wollte die gesamte Mathematik axiomatisieren. Treibende Kraft hinter diesem Vorhaben war der deutsche Mathematiker David Hilbert, und somit ist es auch als Hilbertprogramm bekannt. Das Bestreben, mathematisches Beweisen und somit auch Rechnen zu mechanisieren, trug maßgeblich zur Entwicklung der Informatik und des Computers bei.