Vergleichbarkeitssatz

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Vergleichbarkeitssatz ist ein Satz aus der Mengenlehre und besagt, dass die Mächtigkeiten zweier beliebiger Mengen verglichen werden können.

Inhaltsverzeichnis

1 Satz
2 Definitionen
3 Hilfssätze
4 Beweis
5 Literatur

[Bearbeiten] Satz

Seien M, N zwei beliebige Mengen, so folgt stets |M| ≤ |N| oder |N| ≤ |M|.

Dies impliziert, dass für zwei Mengen M und N gilt: |M| < |N|, |M| = |N| oder |M| > |N| und sichert damit die Vergleichbarkeit der Mächtigkeiten von Mengen.

Der nachfolgende Beweis wurde von Ernst Zermelo (1904) unter Verwendung der Ideen von Erhard Schmidt durchgeführt. Dabei wird unter Annahme der Nichtgültigkeit des Satzes mit mengentheoretischen Mitteln ein Widerspruch herbeigeführt und somit die Gültigkeit des Satz aufgezeigt. Zur Durchführung werden hierfür zunächst verschiedene Begrifflichkeiten eingeführt:

[Bearbeiten] Definitionen

Sei f ⊂ M×N und (x, y) ∈ M×N mit (x, y) ∉ f, dann heißt f^* = f ∪ (x, y) eine echte Fortsetzung von f in M×N.
Sei Z ein Mengensystem und K eine (nichtleere) Teilmenge von Z, dann heißt K eine (nichttriviale) Kette in Z genau dann, wenn für alle f, g in K gilt: f ⊆ g oder g ⊆ f.
Sei K eine Kette in Z und f in K, dann heißt f ein Schnitt von K, wenn für alle g ≠ f in K gilt: f ⊆ g oder g^* ⊆ f
Sei Z ein Mengensystem und T eine Teilmenge von Z, dann heißt T geschlossen ab f₀ genau dann, wenn gilt:

f₀ ∈ T
Alle echten Fortsetzungen von f₀ in Z sind auch in T.
Ist K eine Kette in T und f_U die Vereinigung aller Elemente von K, dann folgt: f_U ∈ T.

siehe Zermelosystem

[Bearbeiten] Hilfssätze

Sei Z eine Menge von Abbildungen f und T^* die Schittmenge aller ab f₀ geschlossenen Ketten in Z, dann gilt:

Lemma 0: Jede ab f₀ geschlossenen Teilmenge T von T^* ist gleich mit T^*

Beweis:	Folgt unmittelbar aus der Definition von T^*:
	Für ein beliebiges ab f₀ geschlossenes T ⊆ T^* gilt: T ⊆ T^* = ∩T und ∩T ⊆ T. Somit folgt aus dem Cantor-Bernstein-Schröder-Theorem T = T^*.

Lemma 1: T^* ist in Z ab f₀ geschlossen.

Beweis:	Sei T = {f ∈ T^* \|f₀ ⊆ f}, dann folgt:
	Es gilt f₀ ⊆ f₀ und somit f₀∈ T Für alle Fortsetzungen f^* von f₀ in Z gilt: f^* ∈ T^* (Definition von T^) und f₀ ⊆ f^ und somit f^* ∈ T. Sei K eine Kette in T und f_∪ die Vereinigung aller f in K, dann folgt: f₀ ⊆ f ⊆ f_∪ und somit f_∪ ∈ T
	Somit ist T ab f₀ geschlossen und da T^* = T (Lemma 0) auch T^*.

Lemma 2: Für jeden Schnitt f in T^* gilt: ∀ g ≠ f: g^* ⊆ f oder f^* ⊆ g

Beweis:	Sei T = {g ∈ K\| g ⊆ f oder f^* ⊆ g}, dann folgt:
	Es gilt f₀ ⊆ f und somit f₀ ∈ T Aus der Definition von T folgt für ein beliebiges g: g ⊆ f oder f^* ⊆ g und da f ein Schnitt ist zusätzlich: g^* ⊆ f oder f ⊆ g. Für f^* ⊆ g oder g^* ⊆ f gilt somit g^* ∈ T, für g ⊆ f und f ⊆ g folgt f = g und somit f^* ⊆ g^, womit wiederum gilt g^ ∈ T. Sei K eine Kette in T und f_∪ die Vereinigung aller f in K. Aus der Definition von T folgt: g ⊆ f oder f^* ⊆ g. Für g ⊆ f gilt f_∪ ⊆ f und somit: f_∪ ∈ T. Für f^* ⊆ g gilt f^* ⊆ f_∪ und somit: f_∪ ∈ T.
	Da T ab f₀ geschlossen ist gilt T^* = T (Lemma 0) und es folgt für jeden Schnitt f in T^: ∀ g ≠ f: g^ ⊆ f oder f^* ⊆ g.

Lemma 3: T^* ist eine Kette in Z.

Beweis:	Sei T die Menge aller Schnitte f in T^*, dann folgt:
	f₀ ist Schnitt von T^* und somit in T. Sei f ein Schnitt von T^* dann ist entweder g^* ⊆ f^* oder f^* ⊆ g und somit f^* in T'. Sei K eine Kette in T und f_∪ die Vereinigung aller f in K. Da jedes f in K ein Schnitt ist, gilt stehts g^* ⊆ f oder f ⊆ g. Somit gilt für alle f: Aus f ⊆ g folgt f_∪ ⊆ g und f ist ein Schitt. Existiert hingegen mindestens ein f mit g^* ⊆ f, so folgt g^* ⊆ f_∪ wegen f ⊆ f_∪ und f ist ein Schnitt. Somit ist f_∪ immer ein Schnitt von T^* und in T enthalten.
	Da T ab f₀ geschlossen ist gilt T^* = T (Lemma 0) und es folgt: T^* ist eine Kette in Z.

[Bearbeiten] Beweis

Voraussetzung: Seien M, N Mengen.

Sei Z die Menge aller bijektiver Abbildungen f von M nach N. Existiert nun ein Abbildung mit dom(f) = M oder mit rng(f) = N, folgt unmittelbar: |M| ≤ |N| oder |N| ≤ |M|.

Annahme:

Angenommen, es existiere keine solche Abbildung, so muss es also für jedes f ein geordnetes Paar x ∈ M und y ∈ N geben für welches gilt: (x, y) ∉ f.

Sei f₀ nun eine beliebige Abbildung in Z und T^* die Schittmenge aller ab f₀ geschlossenen Ketten. Dann ist T^* eine in Z geschlossene (Lemma 1) Kette (Lemma 3). Somit ist auch die Vereinigung f_U aller f ∈ T^* wieder in T^*.

Widerspruch:

Da f_U aber ein Schnitt von T^* ist folgt sofort f^* ∈ T^* (Lemma 2.2). Dies ist ein offensichtlicher Widerspruch, da dadurch die Vereinigung f_U aller (!) Elemente in T^* eine echte Teilmenge eines einzelnen Elementes f_U^* von T^* wäre.

Somit ist die Annahme falsch und es folgt, für zwei beliebige Mengen M und N existiert immer eine bijektive Abbildung f, für die gilt: dom(f) = M oder rng(f) = N.

Schluss: |M| ≤ |N| oder |N| ≤ |M|

[Bearbeiten] Literatur

Oliver Deiser: Einführung in die Mengenlehre. Berlin 2004. ISBN 3-540-20401-6

Von „http://de.wikipedia.org../../../v/e/r/Vergleichbarkeitssatz.html“

Kategorien: Satz (Mathematik) | Mengenlehre

Beweis:	Sei T = {g ∈ K\| g ⊆ f oder f^* ⊆ g}, dann folgt:
	Es gilt f₀ ⊆ f und somit f₀ ∈ T Aus der Definition von T folgt für ein beliebiges g: g ⊆ f oder f^* ⊆ g und da f ein Schnitt ist zusätzlich: g^* ⊆ f oder f ⊆ g. Für f^* ⊆ g oder g^* ⊆ f gilt somit g^* ∈ T, für g ⊆ f und f ⊆ g folgt f = g und somit f^* ⊆ g^, womit wiederum gilt g^ ∈ T. Sei K eine Kette in T und f_∪ die Vereinigung aller f in K. Aus der Definition von T folgt: g ⊆ f oder f^* ⊆ g. Für g ⊆ f gilt f_∪ ⊆ f und somit: f_∪ ∈ T. Für f^* ⊆ g gilt f^* ⊆ f_∪ und somit: f_∪ ∈ T.
	Da T ab f₀ geschlossen ist gilt T^* = T (Lemma 0) und es folgt für jeden Schnitt f in T^: ∀ g ≠ f: g^ ⊆ f oder f^* ⊆ g.

Vergleichbarkeitssatz

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Satz

[Bearbeiten] Definitionen

[Bearbeiten] Hilfssätze

[Bearbeiten] Beweis

[Bearbeiten] Literatur

Views

Navigation

Mitmachen

Suche