Wst¸ep do logiki i teorii mnogości, wyk lad 14
Marek Balcerzak
1
Moc zbioru. Porównywanie mocy.
Definicja 1. Każdemu zbiorowi A przypisujemy pewien obiekt zwany moc¸
a
zbioru A, przy czym dwa zbiory A i B maj¸
a t¸
e sam¸
a moc wtedy i tylko
wtedy, gdy s¸
a one równoliczne. Moc zbioru A oznaczamy przez |A| (inne oznaczenia: A, card(A)). Mamy wi¸
ec
|A| = |B| ⇔ A ∼ B.
Moc zbioru skończonego utożsamiamy z liczb¸
a jego elementów (liczności¸
a).
Dla zbioru nieskończonych moc jest odpowiednikiem liczności.
Definicja 2. Mówimy, że moc zbioru A jest nie wi¸
eksza niż moc zbioru B,
gdy zbiór A jest równoliczny z pewnym podzbiorem zbioru B. Symbolicznie zapisujemy
|A| ≤ |B| ⇔ (∃C)(C ⊂ B ∧ A ∼ C).
W teorii zbiorów (teorii mnogości) wyst¸
epuje nast¸
epuj¸
acy aksjomat zwany
aksjomatem wyboru [ang. Axiom of Choice, w skrócie AC].
• Dla każdej rodziny zbiorów niepustych parami roz l¸acznych istnieje zbiór, który ma z każdym zbiorem danej rodziny po jednym elemencie wspólnym i żadnych innych elementów nie ma. Zbiór ten nazywamy selektorem danej rodziny.
Twierdzenie 1. Niech A i B b¸
ed¸
a niepustymi zbiorami. Nast¸
epuj¸
ace wa-
runki s¸
a równoważne:
(1) |A| ≤ |B|;
(2) istnieje iniekcja f : A → B;
(3) istnieje suriekcja g : B → A.
Twierdzenie 2 (W lasności nierówności mi¸
edzy mocami). Dla dowol-
nych zbiorów A, B i C zachodz¸
a w lasności:
(1) |A| ≤ |A|;
(2) (|A| ≤ |B| ∧ |B| ≤ |C|) ⇒ |A| ≤ |C|;
(3) (|A| ≤ |B| ∧ |B| ≤ |A|) ⇒ |A| = |B|
(tw. Cantora-Bernsteina);
2
Definicja 3. Mówimy, że moc zbioru A jest mniejsza od mocy zbioru B, gdy |A| ≤ |B| oraz zbiory A i B nie s¸a równoliczne. Zapisujemy |A| < |B|.
Uwaga 1. Odnotujmy, że |A| ≤ |N| oznacza przeliczalność zbioru A (wynika z tw. 1 (1) ⇔ (3)), zaś |A| < |N| oznacza skończoność zbioru A.
Przyk lad 1.
• Moc |N| oznaczamy hebrajsk¸a liter¸a alef z indeksem zero:
ℵ0.
Mamy wi¸
ec n < ℵ0 dla n ∈ N. Z równoliczności Z ∼ N ∼ Q wynika, że |Z| = |Q| = ℵ0.
• Zauważmy, że |N| < |R|. Istotnie, nierówność |N| ≤ |R| jest oczywista.
Wiemy, że |[0, 1]| = |(0, 1)| = |R| oraz, że nie zachodzi N ∼ [0, 1].
Zatem |N| < |R|. Moc |R| oznaczamy gotyck¸a liter¸a c (continuum).
Mamy wi¸ec ℵ0 < c.
• Zauważmy, że |A| < |P(A)| dla dowolnego zbioru A. Istotnie, funkcja f : A → P(A) dana wzorem f (x) = {x}. x ∈ A, jest iniekcj¸a. Z twierdzenia Cantora wiemy, że A ∼ P(A) nie zachodzi. Zatem |A| < |P(A)|.
W szczeg ˙olności mamy
|N| < |P(N)| < |P(P(N))| < . . . .
Istnieje wi¸
ec nieskończenie wiele mocy.
Wniosek: Nie istnieje zbiór wszystkich zbiorów. Gdyby taki zbiór X istnia l, to musia loby zachodzić P(X) ⊂ X, sk¸ad |P(X)| ≤ |X|, sprzeczność, bo |X| < |P(X)|.
• Dowodzi si¸e że:
|{0, 1}N| = c; |R \ Q| = c; |R × R| = c.
3
Dowód twierdzenia Cantora-Bernsteina Lemat 3. Niech D ∩ X = ∅ i niech {Dn : n ∈ N} b¸edzie ci¸agiem parami roz l¸
acznych podzbiorów zbioru X (tzn. Dn ∩ Dm = ∅ dla n 6= m), przy czym Dn ∼ D dla każdego n ∈ N. Wówczas X ∪ D ∼ X.
Dowód. Ustalmy bijekcj¸
e f : D → D1. Skoro Dn ∼ D i D ∼ Dn+1, to
Dn ∼ Dn+1. Zatem znajdziemy bijekcj¸e fn : Dn → Dn+1. Definiujemy funkcj¸
e g : X ∪ D → X wzorem
f (x)
dla x ∈ D
g(x) =
fn(x) dla x ∈ Dn (n ∈ N)
x
dla x ∈ X \ S
D
n∈N
n.
Zauważmy, że g jest bijekcj¸
a, która świadczy o tym, że X ∪ D ∼ X.
Lemat 4. Niech D ∩ X = ∅. Jeśli |X ∪ D| ≤ |X|, to |X ∪ D| = |X|.
Dowód. Z za lożenia istnieje iniekcja F : X ∪D → X. Określmy ci¸ag zbiorów
{Dn : n ∈ N} wzorami
D1 = F [D], Dn+1 = F [Dn], n ∈ N.
Wtedy Dn s¸a podzbiorami zbioru X. Ponadto F |D : D → D1 jest bijekcj¸a, sk¸
ad D ∼ D1. Podobnie F |Dn : Dn → Dn+1 jest bijekcj¸a, sk¸ad Dn ∼ Dn+1.
Przez latw¸
a indukcj¸
e wnioskujemy st¸
ad, że Dn ∼ D dla każdego n ∈ N.
Nast¸
epnie przez indukcj¸
e wzgl¸
edem n ∈ N pokazujemy, że
(∀n ∈ N)(∀m > n)(Dn ∩ Dm = ∅).
Dalej stosuj¸
ac lemat 3 wnioskujemy, że X ∪ D ∼ X. St¸ad |X ∪ D| = |X|.
Twierdzenie 5 (Cantora-Bernsteina). Dla dowolnych zbiorów A i B, jeśli |A| ≤ |B| i |B| ≤ |A|, to |A| = |B|.
Dowód. Skoro |A| ≤ |B| i |B| ≤ |A|, to istniej¸a iniekcje f : A → B oraz g : B → A. Przyjmijmy X = g[B], D = A \ X oraz h = g ◦ f . Wtedy h : A → X jest iniekcj¸a, wi¸ec |A| ≤ |X|. Ponadto A = X ∪ D i D ∩ X = ∅.
Zatem z lematu 4 mamy |A| = |X|. Ale
X = g[B] ∼ B (bo g jest iniekcj¸a).
St¸
ad |A| = |X| = |B|.
4
Ważnym twierdzeniem w matematyce jest nast¸
epuj¸
acy lemat udowod-
niony niezależnie przez Kuratowskiego (1922) i Zorna (1935).
Twierdzenie 6 (Lemat Kuratowskiego-Zorna). Niech (X, ≤) b¸edzie niepustym zbiorem cz¸
eściowo uporz¸
adkowanym takim, że każdy lańcuch A ⊂ X
(podzbiór liniowo uporz¸
adkowany przez ≤) ma w X ograniczenie górne (tzn.
istnieje x ∈ X taki, że a ≤ x dla każdego a ∈ A). Wtedy istnieje w X
element maksymalny.
Dowód tego lematu opiera si¸
e na aksjomacie wyboru. Co wi¸
ecej, okazuje
si¸
e, że lemat Kuratowskiego-Zorna jest równoważny aksjomatowi wyboru.
W oparciu o lemat Kuratowskiego-Zorna można wykazać m.in., że każda przestrzeń liniowa ma baz¸
e.
5