Größenvergleich zweier Mengen: „kleinergleich“
Motiviert durch obige Überlegungen definieren wir:
Definition (|A| ≤ |B|)
Seien A und B Mengen. Dann ist die Mächtigkeit von A kleinergleich der Mächtigkeit von B, in Zeichen |A| ≤ |B|, falls gilt:
Es existiert ein injektives f : A → B.
Übung
Sei |A| ≤ |B| und |B| ≤ |C|. Dann gilt |A| ≤ |C|.
Der folgende Satz hält eine wichtige Äquivalenz zu |A| ≤ |B| fest, und gehört zu den mathematischen Resultaten des Typs: „Ich sehe den Beweis.“
Satz
Seien A und B Mengen, und sei A ≠ ∅. Dann sind äquivalent:
(i) | Es existiert f : A → B injektiv. |
(ii) | Es existiert g : B → A surjektiv. |
Beweis
(i) ↷ (ii):
Sei f : A → B injektiv. Wir setzen g′ = f −1 = { (b, a) | (a, b) ∈ f }.
Dann ist g′ : rng(f) → A surjektiv. Sei nun a* ∈ A beliebig und
g = g′ ∪ { (b, a*) | b ∈ B − rng(f) }.
Dann ist g eine Funktion von B nach A und
A = rng(g′) ⊆ rng(g),
also ist g : B → A surjektiv.
(ii) ↷ (i):
Sei g : B → A surjektiv. Für jedes a ∈ A ist also
Ua = g−1″ { a }
nichtleer. Für jedes a ∈ A fixieren wir ein beliebiges ba ∈ Ua.
Wir setzen f = { (a, ba) | a ∈ A }. Dann ist f : A → B injektiv.
Denn seien (a1, b), (a2, b) ∈ f. Dann ist b ∈ Ua1 und b ∈ Ua2, also g(b) = a1 und g(b) = a2. Also a1 = a2.
Der Beweis wiederholt Argumente aus dem Satz über die „Verkettung zur Identität“ aus dem letzten Kapitel. In der Beweisrichtung von (ii) nach (i) findet sich wieder ein Argument vom Typ „ein …“, wobei wir diesmal die Sprechweise „für jedes … fixieren wir“ verwendet haben, was mit „für jedes … wählen wir“ gleichbedeutend ist. (Man spricht in Beweisen gern von „fixieren“ o. ä., wenn ein sonst unbelastetes Zeichen für den Rest des Beweises ein beliebiges Objekt aus einer bestimmten nichtleeren Menge bedeuten soll. Z. B. „Wir fixieren eine Primzahl p ∈ ℕ, und setzen A = { n · p | n ∈ ℕ }.“)
Eine natürliche Definition eines „größergleich“ für Mengen ist:
Definition (|B| ≥* |A|)
Seien A und B Mengen. Wir setzen
|B| ≥* |A| falls A = ∅ oder ein surjektives f : B → A existiert.
Ein Ausdruck |A| ≤* |B| ist dann gleichbedeutend mit |B| ≥* |A|, so wie |B| ≥ |A| gleichbedeutend mit |A| ≤ |B| ist. Daher der Stern, um die Begriffe erst einmal getrennt zu halten. Aus dem obigen Satz folgt aber, dass für alle Mengen A, B gilt: |A| ≤ |B| gdw |A| ≤* |B|.