2
Gleichmächtigkeit von Mengen, Kardinalzahlen
Definition 2.1. Zwei Mengen M und N heißen gleichmächtig, wenn es eine bijektive Ab1−1
bildung f : M → N gibt. Wir schreiben M ←→ N , wenn M und N gleichmächtig sind.
Lemma 2.2. Gleichmächtigkeit ist eine Äquivalenzrelation auf der Klasse aller Mengen.
Beweis.
• Reflexivität: Die Identität ist eine Bijektion.
• Symmetrie: Ist σ : M → N eine Bijektion, dann auch σ −1 : N → M .
• Transitivität: Sind σ : M → N und τ : N → L Bijektionen, dann ist τ ◦ σ : M → L
ebenfalls eine Bijektion.
Bemerkung 2.3. Ist M = ∅, dann gilt |Abb(∅, ∅)| = 1. Die Abbildung ι : ∅ → ∅ ist injektiv
und surjektiv, denn
∀a6=b∈∅ ι(a) 6= ι(b)
∀m∈∅ ∃n∈∅ ι(n) = m
sind wahre Aussagen, da ∅ keine Elemente besitzt.
Definition 2.4. (a) Die Äquivalenzklasse [M ] einer Menge bzgl. Gleichmächtigkeit nennt
man die Kardinalzahl von M und schreibt card(M ).
1−1
(b) Ist M ←→ {1, . . . , n}, dann schreibt man card(M ) = n.
(c) Ist M = ∅, dann schreibt man card(M ) = 0.
(d) Ist M nicht endlich, dann sagt man, M sei eine unendliche Menge. Man schreibt
card(M ) = ∞, aber Vorsicht: sind M und N zwei Mengen mit card(M ) = ∞ und
card(N ) = ∞, dann gilt nicht unbedingt card(M ) = card(M ). Diese Notation ist also
nicht ganz sauber!
(e) Eine Menge M mit card(M ) = card(N) nennt man abzählbar (unendlich).
(f) Ist M unendlich und nicht abzählbar, dann sagt man auch, dass M überabzählbar
ist.
Satz 2.5 (Cantor). Es gibt keine surjektive Abbildung von M in die Potenzmenge P(M )
von M .
12
Beweis. Sei f : M → P(M ) eine surjektive Abbildung. Betrachte die Menge
N = {x ∈ M | x ∈
/ f (x)}.
Beachte: ist x ein Element von M , dann ist f (x) eine Teilmenge von M , die Bedingung
x∈
/ f (x) macht also Sinn.
Wir haben somit eine Menge N ∈ P(M ) konstruiert. Da f surjektiv ist, gibt es ein Urbild
m ∈ M von N , d. h. es gilt f (m) = N . Wir untersuchen nun, ob m ∈ N ist.
Angenommen, m ∈ N , dann ist die Bedingung m ∈
/ f (m) wahr, aber f (m) = N , ein
Widerspruch. Ist m ∈
/ N , dann ist m ∈ f (m) = N , ebenfalls ein Widerspruch. Somit ist die
Annahme falsch und es gibt keine surjektive Abbildung f : M → P(M ).
Beispiel 2.6.
1−1
(a) N ←→ Q (Cantorsches Diagonalverfahren)
1−1
1−1
(b) P(N) ←→ [0, 1] ←→ R, daraus folgt mit dem Satz von Cantor, dass [0, 1] und R
überabzählbar sind.
(c) Es gibt auch direkte Beweise, dass [0, 1] oder R nicht abzählbar sind.
(d) M endlich, card(M ) = n, dann ist card(P(M )) = 2n .
(e) Sind M , N endlich, dann gilt card(Abb(M, N )) = card(N )card(M ) .
Spezialfälle:
M
∅
6= ∅
∅
N
∅
∅
=
6 ∅
card(M ) = m card(N ) = n card(Abb(M, N )) = nm
0
0
00 = 1
>0
0
0m = 0
0
>0
n0 = 1
Die (einzige) Abbildung M → N im Fall M = ∅ ist die Inklusion ∅ → N (sowohl für
N = ∅ und N 6= ∅).
Satz 2.7 (Cantor-Schröder-Bernstein). Seien A und B Mengen. Falls es injektive Abbildungen f : A → B und g : B → A gibt, dann sind A und B gleichmächtig (d. h. dann gibt es
eine Bijektion σ : A → B ).
Beweis. Wir setzen α = g ◦ f : A → A und β = f ◦ g : B → B . Sei α0 = idA und
αi = α
| ◦ α ◦{z· · · ◦ α}
i−mal
für i ∈ N die i-fache Hintereinanderausführung von α, β i sei ähnlich definiert.
Beweisidee: Wir zerlegen A und B jeweils in eine disjunkte Vereinigung von Teilmengen
und zeigen, dass es Bijektionen zwischen jeweils zwei dieser Teilmengen gibt, die sich dann
13
∪˙
∪˙
G
f20 00
00
g2 00
00
0
∪˙
g(β 2 (B)) \ α3 (A)
00
00
0
∪˙ · · · ∪˙
A∞
f∞
f (α2 (A)) \ β 3 (B)
∪˙
∪˙
α2 (A) \ g(β 2 (B))
G
f10 00
00
g1 00
00
0
g(β(B)) \ α2 (A)
∪˙
β 2 (B) \ f (α2 (A))
∪˙
00
00
0
f (α(A)) \ β 2 (B)
∪˙
∪˙
α(A) \ g(β(B))
G
f00 00
00
g0 00
00
0
g(B) \ α(A)
A \ g(B)
∪˙
β(B) \ f (α(A))
=
00
00
0
f (A) \ β(B)
B
=
B \ f (A)
A
∪˙ · · · ∪˙
B∞
Abbildung 3: Teilmengen von A und B
zu einer Bijektion zwischen A und B zusammensetzen. Abbildung 3 zeigt diese Zerlegung
in Teilmengen und die Abbildungen dazwischen. Hierbei ist
A∞ = ∩i∈N0 αi (A) = {a ∈ A | ∀i∈N0 ∃x∈A a = αi (x)}.
Analog definiert man B∞ = ∩j∈N0 β j (B). Beachte, dass
αi+1 = (g ◦ f )i+1 = g ◦ (f ◦ g)i ◦ f = g ◦ β i ◦ f und g ◦ β i = αi ◦ g
ist, daher gelten folgende Inklusionen von Teilmengen von A:
A∞ ⊆ . . . ⊆ αi+1 (A) ⊆ g(β i (B)) ⊆ αi (A) ⊆ . . . ⊆ α2 (A) ⊆ g(β(B)) ⊆ α(A) ⊆ g(B) ⊆ A
Es folgt, dass jedes Element von A in genau einer der Teilmengen von A in Abbildung 3 ist,
und dies damit tatsächlich eine disjunkte Zerlegung von A ist. Ähnliche Argumente gelten
für die Zerlegung von B .
Wir werden nun die Abbildungen f∞ , f0 , f1 , . . . definieren. Die Grundidee dabei ist immer
dieselbe: Seien à ⊆ A und B̃ ⊆ B . Die Frage ist, ob durch f˜ : à → B̃ : x 7→ f (x) eine
Abbildung oder sogar eine Bijektion definiert ist. Die Abbildung f˜ ist wohldefiniert, wenn
für alle x ∈ Ã auch f (x) ∈ B̃ gilt. Da f injektiv ist, ist in diesem Fall f˜ ebenfalls injektiv,
d. h. um zu zeigen, dass f˜ eine Bijektion ist, ist dann nur noch die Surjektivität zu zeigen.
Nun zu den konkreten Fällen:
Wir definieren
f∞ : A∞ → B∞ : x 7→ f (x).
• Wohldefiniertheit von f∞ :
Sei x ∈ A∞ , dann gibt es für jedes i ∈ N0 ein xi ∈ A mit x = αi (xi ). Dann ist
f (x) = f ◦ αi (xi ) = f ◦ (g ◦ f )i (xi ) = (f ◦ g)i ◦ f (xi ) = β i ◦ f (xi ) ∈ β i (B). (2.1)
Also ist f (x) ∈ B∞ .
14
• Surjektivität von f∞ :
Sei b ∈ B∞ , dann gibt es für jedes i ∈ N0 ein yi ∈ B , sodass b = β i (yi ) ist. Da
für i ≤ j ∈ N0 β i (yi ) = b = β j (yj ) = β i (β j−i (yj )) gilt und β injektiv ist, folgt, dass
yi = β j−i (yj ) ist. Insbesondere ist y1 = β j (yj+1 ) ∈ β j (B) für alle j ∈ N0 , also
y1 ∈ B∞ , somit g(y1 ) ∈ A∞ (mit derselben Argumention wie bei der Wohldefiniertheit
von f∞ ). Es folgt b = β(y1 ) = f (g(y1 ))) = f∞ (g(y1 ) und f∞ ist surjektiv.
| {z }
∈A∞
Weiter definieren wir für i ∈ N0
fi : αi (A)\g(β i (B)) → f (αi (A))\β i+1 (B) : x 7→ f (x).
• Wohldefiniertheit von fi :
Ist x = αi (a) ∈ αi (A)\g(β i (B)) mit a ∈ A, dann ist f (x) = f (αi (a)) ∈ f (αi (A)). Angenommen, f (x) ∈ β i+1 (B). Dann gibt es y ∈ B mit f (x) = β i+1 (y) = f (g(β i (y))).
Aus der Injektivität von f folgt x = g(β i (y)) ∈ g(β i (B)), ein Widerspruch. Also ist
f (x) ∈ f (αi (A))\β i+1 (B) und damit ist die Abbildung fi wohldefiniert.
• Surjektivität von fi :
Sei y ∈ f (αi (A))\β i+1 (B), dann existiert x ∈ αi (A) mit f (x) = y . Wäre x ∈ g(β i (B)),
dann wäre y = f (x) ∈ β i+1 (B), ein Widerspruch. Somit ist x ∈ αi (A)\g(β i (B)) ein
Urbild von y unter fi und fi ist surjektiv.
Analog zu den Abbildungen fi definiert man die Abbildungen
gi : β i (B)\f (αi (A)) → g(β i (B))\αi+1 (A) : y 7→ g(y)
und zeigt, dass diese wohldefinierte Bijektionen sind.
Nun setzt man diese Abbildungen zusammen und erhält eine Bijektion σ : A → B . Für
diese Abbildung gilt σ(x) = f (x), falls x ∈ A∞ oder es ein i ∈ N0 gibt, sodass x ∈
αi (A)\g(β i (B)) ist. Andernfalls ist x ∈ g(β i (B))\αi+1 (A) für ein i ∈ N0 . Ist y ∈ B in
diesem Fall das (eindeutig bestimmte) Element von B mit g(y) = x, dann ist σ(x) = y .
Korollar 2.8. Durch card(M ) ≤ card(N ) genau dann, wenn es eine injektive Abbildung
M → N gibt, wird eine Ordnungsrelation auf der Klasse der Kardinalzahlen definiert.
Beweis. Die Reflexivität gilt, da die Identität auf einer Menge injektiv ist. Die Transitivität
folgt, da die Verknüpfung injektiver Abbildungen injektiv ist. Die Antisymmetrie ist gerade
die Aussage von Satz 2.7.
Bemerkung 2.9. (a) Die (einfache) Kontinuumshypothese, die Georg Cantor 1878 aufstellte, besagt:
15
© Copyright 2024 ExpyDoc
