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.

Wskazówka

Dowód należy poprowadzić niewprost, stosując metodę przekątniową. W pierwszym przypadku rozważyć bijekcje

$\displaystyle f: \mathbb N \rightarrow 2^\mathbb N$ . Przy jej pomocy zbudować ciąg

$\displaystyle g: \mathbb N \rightarrow \mathbb N$ zadany wzorem

$\displaystyle g(i) = 1- f(i)(i)$ . Drugi fakt wynika z pierwszego. Gdyby dowodzić go niezależnie, należy tak jak poprzednio dla bijekcji

$\displaystyle h:\mathbb N \rightarrow \mathbb N^\mathbb N$ rozważyć przykładowo funkcje

$\displaystyle n \rightarrow h(n)(n)+1$ .

Rozwiązanie

Dla dowodu niewprost ustalmy surjekcję

$\displaystyle f:\mathbb{N} \rightarrow 2^{\mathbb{N}}$ . Zdefiniujmy specjalny element zbioru

$\displaystyle 2^{\mathbb{N}}$ w następujący sposób:

$\displaystyle g(n) = \begin{cases} 0, & \mbox{ jeśli }\displaystyle f(n)(n) = 1, \\ 1, & \mbox{ jeśli }\displaystyle f(n)(n) =0.\end{cases}$

Funkcja $\displaystyle g$ różni się od obrazu liczby $\displaystyle n$ względem $\displaystyle f$ na $\displaystyle n$ -tym miejscu. Ponieważ $\displaystyle f$ jest bijekcją, to istnieje $\displaystyle n_0$ takie, że $\displaystyle f(n_0)=g$ , czyli $\displaystyle f(n_0)(n) = g(n)$ , dla każdego $\displaystyle n$ . Z definicji $\displaystyle g$ wynika, że $\displaystyle g(n_0)\neq f(n_0)(n_0)$ , co daje oczekiwaną sprzeczność.

Gdyby istniała surjekcja $\displaystyle f$ z $\displaystyle \mathbb{N}$ w $\displaystyle \mathbb{N}^{\mathbb{N}}$ , to możemy zdefiniować $\displaystyle g$ jako:

$\displaystyle g(n) = \begin{cases} f(n), & \mbox{ jeśli } \overrightarrow{f(n)} (\mathbb{N})\subset 2, \\ z, & \mbox { w przeciwnym przypadku, } \displaystyle \end{cases}$

gdzie $\displaystyle z:\mathbb{N} \rightarrow 2$ jest funkcją stale równą zero. Funkcja $\displaystyle g$ jest surjekcją z $\displaystyle \mathbb{N}$ na $\displaystyle 2^{\mathbb{N}}$ , co jest sprzecznością z poprzednim faktem.

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.

Wskazówka

Użyj aksjomatu wyboru.

Wskazówka

Skorzystaj z wykładu 11 "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady" Twierdzenie 4.1.

Rozwiązanie

Implikacja w jedną stronę jest prosta. Jeśli zbiór jest skończony, to jest również skończony w sensie Dedekinda. Wykażemy najpierw, że jeśli z różnej od zera liczby naturalnej

$\displaystyle n$ usuniemy dowolny element, to zbiór powstały będzie równoliczny z

$\displaystyle n-1$ . Usuńmy dowolny element z

$\displaystyle n$ . Jeśli usunęliśmy

$\displaystyle n-1$ , to otrzymujemy liczbę

$\displaystyle n-1$ . Jeśli usunęliśmy

$\displaystyle k\neq n-1$ , to możemy zdefiniować bijekcję pomiędzy

$\displaystyle n\setminus\{k\}$ a

$\displaystyle n-1$ poprzez:

$\displaystyle f(m)= \begin{cases} m, & \mbox{ jeśli }\displaystyle m\neq n-1, \\ k, & \mbox{ jeśli }\displaystyle m = n-1.\end{cases}$

Wybierzmy teraz najmniejszą liczbę $\displaystyle n$ równoliczną z inną liczbą naturalną $\displaystyle m$ . Niewątpliwie $\displaystyle n$ i $\displaystyle m$ są różne od zera i istnieje bijekcja $\displaystyle f:n \rightarrow m$ . Jeśli bijekcję $\displaystyle f$ zawężymy do $\displaystyle n-1$ , to obraz zawęzi się, na mocy udowodnionego wcześniej wniosku, do podzbioru $\displaystyle m$ równolicznego $\displaystyle m-1$ . Wykazaliśmy, że zbiór $\displaystyle n-1$ jest równoliczny $\displaystyle m-1$ , co jest sprzecznością z minimalnością $\displaystyle n$ . Wykazaliśmy, że żadne dwie różne liczby naturalne nie są równoliczne. Ustalmy teraz dowolny skończony zbiór $\displaystyle X$ . Istnieje bijekcja pomiędzy $\displaystyle X$ i $\displaystyle n$ , dla pewnej liczby naturalnej $\displaystyle n$ . Jeśli $\displaystyle X$ byłby bijektywny ze swoim istotnym podzbiorem, to również $\displaystyle n$ byłoby bijektywne ze swoim istotnym podzbiorem, czyli ze zbiorem równolicznym liczbie naturalnej mniejszej o co najmniej $\displaystyle 1$ -- jest to sprzecznością z wcześniej wykazanym faktem.

Dla dowodu implikacji w drugą stronę wykorzystamy "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady" Twierdzenia 4.1 z Wykładu 11. Mówi ono, że dla każdego nieskończonego zbioru istnieje iniekcja z $\displaystyle \mathbb{N}$ w ten zbiór. Ustalmy dowolny nieskończony zbiór $\displaystyle X$ i taką iniekcję $\displaystyle f:\mathbb{N} \rightarrow X$ . Niech $\displaystyle Y\subset X$ będzie obrazem $\displaystyle \mathbb{N}$ względem $\displaystyle f$ tak, że $\displaystyle f:\mathbb{N}\rightarrow Y$ jest bijekcją. Zdefiniujmy funkcję $\displaystyle g:X \rightarrow X$ :

$\displaystyle h(x) =\left\{\begin{array}{lll} x & \mbox{ jeśli }\displaystyle x\notin Y \\ f(n+1) & \mbox{ jeśli }\displaystyle x=f(n)\in Y. \end{array} \right.$

Jak łatwo sprawdzić funkcja $\displaystyle h:X \rightarrow X\setminus\{f(0)\}$ jest bijekcją, co dowodzi, że zbiór $\displaystyle X$ jest równoliczny ze swoim istotnym podzbiorem, czyli że jest nieskończony w sensie Dedekinda.

Wykazaliśmy, że zbiór skończony jest skończony w sensie Dedekinda i że zbiór nieskończony jest nieskończony w sensie Dedekinda co kończy ćwiczenie. Zwróćmy uwagę, że przy dowodzie tego faktu użyliśmy aksjomatu wyboru.