Zbiory mocy continuum

Zbiory mocy continuum



Definicja 3.1

Zbiór nazywamy nieprzeliczalnym, gdy nie jest przeliczalny.

Ćwiczenie 3.2

Zbiory \( \displaystyle 2^{\mathbb{N}} \) oraz \( \displaystyle \mathbb{N}^{\mathbb{N}} \) nie są przeliczalne.


Definicja 3.3

Mówimy, że zbiór jest mocy continuum, gdy jest równoliczny z \( \displaystyle \mathbb{R} \).

Lemat 3.4

Każdy przedział obustronnie otwarty jest mocy continuum.

Dowód

Na początku pokażemy, że istnieje bijekcja pomiędzy przedziałem otwartym liczb rzeczywistych \( \displaystyle (-1,1) \) a \( \displaystyle \mathbb R \). Bijekcją taką jest \( \displaystyle x \rightarrow \frac{x}{1-x^2} \). (Jako ćwiczenie spróbuj narysować wykres tej funkcji.) Następnie łatwo zauważyć, że każde dwa przedziały otwarte są równoliczne. (Jako ćwiczenie napisz wzór na funkcję liniową pomiędzy dwoma zadanymi otwartymi przedziałami.)

Lemat 3.5

Jeżeli \( \displaystyle A \subset \mathbb{R} \) i \( \displaystyle A \) zawiera pewien przedział otwarty, to \( \displaystyle A \) jest mocy continuum.

Dowód

Prosta konsekwencja Twierdzenia 2.12 Cantora-Bernsteina.

Następne dwa lematy pokazują, że zbiory mocy kontinuum są odporne na dodawanie i ujmowanie zbiorów przeliczalnych. Po każdej takiej operacji moc zbioru jest taka, jak była. Proszę o zapoznanie się z prostymi dowodami tych lematów. Może to być pomocne w rozwiązywaniu zadań.

Lemat 3.6

Jeżeli \( \displaystyle B \subset A \) jest przeliczalnym podzbiorem zbioru \( \displaystyle A \) mocy continuum, to
\( \displaystyle A \setminus B \) jest mocy continuum.

Dowód

Załóżmy bez straty ogólności, że \( \displaystyle B \subset A \). Zauważmy, że \( \displaystyle A \setminus B \) jest nieprzeliczalny. Inaczej przeczyłoby to Twierdzeniu 2.9 o nieprzeliczalności \( \displaystyle \mathbb R \). W takim razie \( \displaystyle A \setminus B \) jest nieskończony. Można zatem odnaleźć w nim na mocy Twierdzenia 2.15 (stosując aksjomat wyboru, zapoznaj się z dowodem tego twierdzenie w wykładzie 11, "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady", Twierdzenie 4.1) nieskończony zbiór przeliczalny \( \displaystyle B' \). Mamy więc \( \displaystyle B \cup B' \) jest nieskończonym zbiorem przeliczalnym. Istnieje zatem bijekcja \( \displaystyle f: B \cup B' \rightarrow B' \). Mając ją, możemy określić bijekcję \( \displaystyle h: A \rightarrow A \setminus B \) następująco:

\( \displaystyle h(x) =\left\{\begin{array}{lll} f(x) , & x \in B\cup B', \\ x, & x \notin B\cup B'. \end{array} \right. \)

Lemat 3.7

Jeżeli \( \displaystyle B \) jest przeliczalnym, a \( \displaystyle A \) jest mocy continuum, to \( \displaystyle A \cup B \) jest mocy continuum.

Dowód

Opiszmy słowami dowód podobny do poprzedniego. Na początku należy odnaleźć w \( \displaystyle A \) zbiór nieskończony przeliczalny \( \displaystyle B_0 \). Zbiór ten musi być równoliczny z \( \displaystyle B\cup B_0 \). W takim razie można bijektywnie schować zbiór \( \displaystyle B\cup B_0 \) w zbiorze \( \displaystyle B_0 \). Następnie należy zdefiniować bijekcję między \( \displaystyle A \cup B \) a \( \displaystyle A \) tak, aby na fragmencie z poza \( \displaystyle B_0 \) była identycznością, a na \( \displaystyle B \cup B_0 \) była poprzednią bijekcją. Sklejenie takich bijekcji na zbiorach rozłącznych jest bijekcją.

Twierdzenie poniższe będzie mieć dla nas fundamentalne znaczenie. Porównuje ono moc dwóch podstawowych dla nas zbiorów \( \displaystyle \mathbb N \) i \( \displaystyle \mathbb R \). Do dowodu posłużymy się konstrukcją rozwinięcia dwójkowego przeprowadzonego w Twierdzeniu 3.15 z Wykładu 8 (patrz "Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek", Twierdzenie 3.15). Twierdzenie 3.18 tego rozdziału pokazuje bijekcje pomiędzy pewnymi specjalnymi ciągami ze zbioru \( \displaystyle 2^\mathbb N \) a przedziałem \( \displaystyle [0,1) \). Przed przeczytaniem tego dowodu zapoznaj sie z Twierdzeniami 3.15, 3.17, 3.18 z Wykładu 8 (patrz "Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek").

Twierdzenie 3.8

\( \displaystyle 2^{\mathbb{N}} \) jest mocy continuum.

Dowód

Zbiór \( \displaystyle 2^\mathbb N \) rozbijmy na dwa rozłączne podzbiory. Zbiór \( \displaystyle X \) taki, jak w Twierdzeniu 3.18 wykładu 8 to znaczy \( \displaystyle X= \{a\in 2^{\mathbb{N}}: \forall_{k} \;\; \exists_{n>k} \;\; a_n = 0\} \) oraz zbiór \( \displaystyle X' = \{a \in 2^{\mathbb{N}}: \exists_{k} \;\; \forall_{n>k} \;\; a_n = 1\} \) będący jego uzupełnieniem. Łatwo zauważyć, że \( \displaystyle X' \) jest przeliczalny, bo można go przedstawić jako przeliczalną sumę zbiorów skończonych. \( \displaystyle X' \) składa się z ciągów, które od pewnego miejsca są stale równe \( \displaystyle 1 \). Zauważmy, że jest jedynie \( \displaystyle 2^{k_0} \) takich ciągów, które od \( \displaystyle k_0 +1 \) miejsca są stale równe \( \displaystyle 1 \). Zbiór \( \displaystyle X \), jak pokazaliśmy w Twierdzeniu 3.18 w wykładzie 8, jest równoliczny z przedziałem \( \displaystyle [0,1) \), a więc przeliczalny. Nasz zbiór \( \displaystyle 2^\mathbb N = X \cup X' \) jako suma zbioru continuum i przeliczalnego na mocy Lematu 3.7 jest mocy continuum.

Twierdzenie 3.9

\( \displaystyle \mathbb{N} < _m \mathcal{P} (\mathbb{N}) \sim_m 2^{\mathbb{N}} \sim_m \mathbb{R}. \)

Rodzi się naturalne pytanie. Czy istnieje taki zbiór, którego moc dałoby się ulokować pomiędzy mocą zbioru liczb naturalnych a mocą continuum. Czyli, czy istnieje \( \displaystyle A \) takie, że

\( \displaystyle \mathbb N < _m A < _m \mathbb R \quad \mbox{(3.1)} \)

Cantor przypuszczał, że takiego zbioru (mocy) nie ma i że następnym w hierarchii mocy zbiorem po \( \displaystyle \mathbb N \) jest \( \displaystyle \mathbb R \). Przypuszczenie Cantora nazywa się hipotezą continuum. Hipoteza ta była intensywnie badana przez matematyków. W roku 1939 Kurt Gödel pokazał niesprzeczność tej hipotezy z aksjomatami teorii mnogości. Można zatem przyjąć, że taki zbiór jak w hipotezie kontinuum istnieje i nie doprowadzi to teorii mnogości do sprzeczności, o ile sama nie jest sprzeczna. W roku 1963 Paul Joseph Cohen pokazał niezależność hipotezy continuum od aksjomatów teorii mnogości. Oznacza to, że nie można hipotezy udowodnić na gruncie tej teorii, ale nie można też udowodnić jej zaprzeczenia.

Na koniec podamy jako ćwiczenie inną bardzo elegancką i nieodwołującą się do pojęcia liczb naturalnych definicję nieskończoności.

Definicja 3.10

(definicja nieskończoności Dedekinda) Zbiór \( \displaystyle X \) jest nieskończony w sensie Dedekinda, gdy istnieje podzbiór właściwy \( \displaystyle X_0 \) zbioru \( \displaystyle X \), który jest z nim równoliczny. Zbiór jest skończony, w sensie Dedekinda, jeśli nie jest nieskończony w sensie Dedekinda.

Ćwiczenie 3.11

Pokaż, że zbiór jest nieskończony wtedy i tylko wtedy, gdy jest nieskończony w sensie Dedekinda.