Kardinalitäten mit Surjektionen vergleichen
(Abkürzung: ≤*)
Wenn das Auswahlaxiom nicht gilt können wir die „Größe“ (Kardinalität) von Mengen auf 2 verschiedene Arten vergleichen:
| Übliche Definition (mit Injektionen) | Alternative Definition (mit Surjektionen) | |
|---|---|---|
| Menge A hat keine größere Kardinalität als Menge B, wenn es eine injektive Funktion von A nach B gibt (oder wenn A leer ist). | Menge A hat keine größere Kardinalität als Menge B, wenn es eine surjektive Funktion von B auf A gibt (oder wenn A leer ist). | |
| formal: | |A| ≤ |B| | |A| ≤* |B| |
| Einige Gesetzmäßigkeiten gelten bei beiden Varianten: | A ⊆ B ⇒ |A| ≤ |B| | A ⊆ B ⇒ |A| ≤* |B| |
| |A| ≤ |B| und |B| ≤ |C| ⇒ |A| ≤ |C| | |A| ≤* |B| und |B| ≤* |C| ⇒ |A| ≤* |C| | |
nicht jedoch der wichtige Äquivalenzsatz von Cantor-| |A| ≤ |B| und |B| ≤ |A| ⇒ |A| = |B|
|
| Aus einer Surjektion lässt sich ohne Auswahlaxiom keine Injektion in Gegenrichtung gewinnen, und daher auch keine Bijektion. Wir können lediglich definieren, dass |A| =* |B| bedeuten soll: |A| ≤* |B| und |B| ≤* |A| |
Eigenschaften
Ohne Auswahlaxiom ist nicht viel über ≤* beweisbar.[1]
(Mit Auswahlaxiom ist ≤* dasselbe wie ≤.)
Wir wissen:
- |A| ≤ |B| ⇒ |A| ≤* |B| (denn aus einer Injektion lässt sich auch ohne Auswahlaxiom eine Surjektion in Gegenrichtung definieren – Da jedes Bildelement nur ein Urbild hat, ist keine Auswahl nötig.)
- Wenn doch der Äquivalenzsatz von Cantor-
Bernstein für ≤* gilt, dann kann es keine Dedekind- endlichen Mengen geben. Aber es gibt dann eine unmessbare Menge.[2] - Wenn alle Mengen mittels ≤* vergleichbar sind, dann gilt das Auswahlaxiom.[3]
- |A| ≤* |B| ⇒ |𝒫(A)| ≤ |𝒫(B)| [4]
Beispiele
| formal | |||
|---|---|---|---|
| Wenn ℝ nicht wohlordenbar ist, dann kann es keine Injektion von der Ordinalzahl ω1 (= Menge aller höchstens abzählbaren Ordinalzahlen) nach ℝ geben oder umgekehrt; eine Surjektion von ℝ auf ω1 aber schon. | |ω1| ≰ |ℝ|,
|ω1| ≱ |ℝ| und | ||
| Ab einer gewissen Ordinalzahl (Θ) lässt sich ℝ nicht mehr surjektiv darauf abbilden. Auch umgekehrt ist keine Surjektion möglich.[5] | |Θ| ≰ |ℝ|,
|Θ| ≱ |ℝ|, | ||
Wenn alle Mengen reeller Zahlen Lebesgue-| |ℝ| < |ℝ/ℚ| und
| |ℝ| ≥* |ℝ/ℚ| Es kann auch eine Surjektion von so einer Menge wie in der vorigen Zeile (Quotientenmenge) auf ℝ geben.
|
| |ℝ| ≥* |𝒦| und (= Gegenbeispiel zum Äquivalenzsatz von Cantor- |
Mögliche Zusatzannahmen (Alternativen zum Auswahlaxiom)
| Name | Abk. | formal | Bemerkungen |
|---|---|---|---|
| Partitionsprinzip | PP | |A| ≤* |B| ⇒ |A| ≤ |B|
und, da die Umkehrung immer gilt, somit |
Jede Surjektion B → A erzeugt (indem man die Urbilder jedes Elements a ∈ A betrachtet) eine Zerlegung (Partition) von B. Das Partitionsprinzip sagt, dass diese Zerlegung von B in |A| viele Teile keine größere Kardinalität als B selbst haben kann. |
| schwaches Partitionsprinzip (englisch: weak partition principle) | WPP | |A| ≤* |B| ⇒ |B| ≮ |A| | Besagt, dass wir keine Menge in mehr Teile zerlegen können, als diese Menge Elemente hat.[6] |
| schwacher dualer Äquivalenzsatz von Cantor- | WDCBT | |A| ≤* |B| und |B| ≤* |A| ⇒ |A| ≤ |B| oder |B| ≤ |A| |
Weiter
| Kardinalitäten: Kardinalitäten unter dem Determiniertheitsaxiom | |
|
| Auswahlaxiom: Argumente pro und contra Auswahlaxiom |
Quellen
| [1] | Asaf Karagila im Diskussionsforum StackExchange – „without the axiom of choice not much is provable about ≤*.“ | ||||||||
| [2] | Asaf Karagila auf seiner Website – „It can be shown, for example, that if ≤* is antisymmetric then there are no Dedekind-| [3]
| Asaf Karagila auf StackExchange – „We also know that if it is a total ordering then the axiom of choice holds.“
| [4]
|
|
[5]
| Gabe Goldberg auf StackExchange – „No injections or surjections: ℝ and Θ = sup {a ∈ Ord : α ≤* ℝ}“
| [6]
| Asaf Karagila: One the partition principle – „we cannot partition a set into strictly more parts than elements“.
| |