Na tym wykładzie omówimy pojęcie nieprzeliczalności, pokażemy nieprzeliczalność funkcji z \(\mathbb {N}\) w \(\{0,1\}\) i nieprzeliczalność \(\mathbb {R}\), powiemy co to są liczby przestępne. Wykażemy twierdzenie Cantora1 o mocy zbioru podzbiorów, wspomnimy o hipotezie Continuum i na końcu krótko powiemy o podobieństwie porządkowym.
Zacznijmy od definicji:
Poniższe twierdzenie pokazuje pierwszy przykład zbioru nieprzeliczalnego, dając zarazem odpowiedź na pytanie czy takie zbiory w ogóle istnieją.
Dowód. Przypuśćmy, dla dowodu nie wprost, że zbiór \(C\) jest przeliczalny. Możemy zatem wszystkie jego wyrazy ustawić w ciąg: \((c_1),(c_2),(c_3),\ldots \). Rozważmy teraz ciąg \((d)\) ze zbioru \(C\) utworzony w ten sposób, że
\[d_j=\begin {cases} 0 \text { jeÅŻli ciÄĚg $(c_j)$ ma na pozycji $j$ jedynkÄŹ}\\ 1 \text { jeÅŻli ciÄĚg $(c_j)$ ma na pozycji $j$ zero}\\ \end {cases} \]
Przykładowo, jeśli nasz ciąg \((c_1),(c_2),(c_3),\ldots \) jest następujący
\[ \begin {array}{ccccccc} (c_1)=& \underline {1}&0&1&1&0&\ldots \\ (c_3)=& 1&\underline {1}&1&0&0&\ldots \\ (c_3)=& 0&0&\underline {0}&1&0&\ldots \\ \dots &&&&&& \end {array} \]
to
\[(d)=0\ 0\ 1\ \ldots \]
Zauważmy teraz, że ciąg \((d)\) nie może być na żadnej pozycji w naszym ciągu ciągów \((c_1),(c_2), (c_3),\ldots \), bo skonstruowany ciąg różni się od każdego ciągu \((c_k)\) na \(k\)-tej pozycji.
□
Fakt, że zbiór ciągów zero-jedynkowych jest zbiorem nieprzeliczalnym pozwala nam wykazać kolejne twierdzenie.
Dowód. Skonstruujemy injekcję \(\iota \) z \(C\) w \(\R \). Ciągowi \((c)=(a_1,a_2,a_3,\dots )\), gdzie \(a_i\in \{0,1\}\) przyporządkujemy liczbę rzeczywistą \(0,a_1a_2a_3\dots \) (w zapisie dziesiętnym). Jeśli \(0,a_1a_2a_3\dots =0,b_1b_2b_3\dots \) to znaczy, że
\[\sum _{i=1}^{\infty }a_i10^{-i}=\sum _{i=1}^{\infty }b_i10^{-i}.\]
Jeśli \(a_i=b_i \) dla każdego \(i\), to nasze przyporządkowanie jest injekcją. Przypuśćmy, że tak nie jest. Niech zatem \(k\) będzie najmniejszym wskaźnikiem \(i\), dla którego \(a_i\neq b_i\) Niech na przykład \(a_k=1\) i \(b_k=0\). Wtedy \(\sum _{i=k}^{\infty }a_i10^{-i}\geq \frac {1}{10^k}\) oraz \(\sum _{i=k}^{\infty }b_i10^{-i}=\sum _{i=k+1}^{\infty }b_i10^{-i}<\frac {1}{10^k}\), a zatem \(\sum _{i=1}^{\infty }a_i10^{-i}-\sum _{i=1}^{\infty }b_i10^{-i}>0\), sprzeczność.
Mamy zatem injekcję \(\iota : C\hookrightarrow \R \), czyli zbiór \(C\) jest równoliczny z podzbiorem \(\iota (C)\) zbioru \(\R \) (obraz zbioru przez injekcję jest równoliczny z tym zbiorem.) Skoro tak, to zbiór \(\R \) nie jest ani skończony (oczywiście), ani przeliczalny – bo zawiera zbiór nieprzeliczalny \(\iota (C)\). □
W poprzednim twierdzeniu skonstruowaliśmy injekcję z \(C\) w \(\R \). Kolejne twierdzenie pokaże jak skonstruować injekcję z podzbioru \((0,1)\subset \R \) w zbiór \(C\), a Stwierdzenie 194 pokaże równoliczność \((0,1)\) i \(\R \). Dostaniemy zatem, po złożeniu odwzorowań, injekcję z \(\R \) w \(C\). W takim razie dostaniemy dwie injekcje: z \(\R \) w \(C\) i z \(C\) w \(\R \). W następnym wykładzie poznamy twierdzenie, zwane twierdzeniem Cantora–Bernsteina pozwoli nam stwierdzić, że istnieje bijekcja pomiędzy \(C\) i \(\R \).
Dowód. Każdy punkt z przedziału \((0,1)\) zapiszmy w systemie dwójkowym, np
\[0{,}3_{10}=0{,}01001100110\dots _{2}.\]
Ten zapis może być niejednoznaczny, w tym sensie, że np. \(0{,}011111\dots _{2}=0{,}1_{2}=0{,}5_{10}\). Przyjmujemy zatem umowę, że jeśli w zapisie od pewnego miejsca \(k+1\) jest nieskończenie wiele jedynek (a na miejscu \(k\) zero) to zapisujemy je jako jedynkę na miejscu \(k\). Zauważmy, że liczba \(0{,}1111111111\dots _{2}\) jest równa \(1_{10}\), a zatem nie należy do naszego przedziału. Mając teraz jednoznaczność zapisu, definiujemy nasze odwzorowanie następująco. Liczbie \(c\) z przedziału \((0,1)\) zapisanej w systemie dwójkowym jako \(0{,}c_1c_2c_3\dots \) przyporządkowujemy ciąg
\[c=c_1c_2c_3\dots \in C.\]
To przyporządkowanie jest oczywiście injektywne, co kończy dowód. □
Wiemy już, że zbiór \(\R \) jest nieprzeliczalny. Zbiór, który jest równoliczny ze zbiorem liczb rzeczywistych (czyli istnieje bijekcja z tego zbiory w \(\R \)) nazwiemy zbiorem mocy continuum.
Definicja 193. Mówimy, że zbiór \(A\) ma moc continuum, jeśli \(A\sim \R \).
Wykażemy teraz zapowiedziane wyżej stwierdzenie:
Dowód. Dowód tego faktu jest elementarny. Konstruujemy najpierw bijekcję z przedziału \((0,1)\) w przedział \((-\frac {\pi }{2},\frac {\pi }{2})\), na przykład jako
\[f_1(x)=\pi x-\frac {\pi }{2}.\]
Następnie bierzemy
\[f_2(x)=\tg (x),\]
\(f_2\) jest bijekcją z \((-\frac {\pi }{2},\frac {\pi }{2})\) w \(\R \). Składając te funkcje, dostajemy bijekcję \(f=f_2\circ f_1\) z \((0,1)\) w \(\R \). □
Uwaga 195. Dociekliwy czytelnik może zapytać o bijektywność funkcji \(\tg : (-\frac {\pi }{2},\frac {\pi }{2})\to \R \). Sprawdzenie injektywności jest prostym ćwiczeniem z trygonometrii, sprawdzenie surjektywności zostawiamy czytelnikowi jako ćwiczenie z analizy (należy wykazać ciągłość funkcji tangens, policzyć granice na końcach przedziału \((-\frac {\pi }{2},\frac {\pi }{2})\) i skorzystać z własności Darboux).
Zauważyliśmy już wcześniej, że relacja równoliczności zbiorów jest zwrotna, symetryczna i przechodnia. Ma zatem sens następująca definicja:
Mamy następujące własności i oznaczenia.
1 \(\# \emptyset =0.\)
2 \(\# X=n \iff X\sim \{1,2,\dots n\}.\)
3 \(\# \N =\aleph _0\)
4 \(\# \R =\mathfrak {c}.\)
Definicja 198. Niech teraz \(\# A=\mathfrak {a}\), \(\# B=\mathfrak {b}\). Mówimy, że \(\mathfrak {a}\leq \mathfrak {b}\) jeśli istnieje zbiór \(C\subset B\) taki, że \(A\sim C\) (czyli \(A\) jest równoliczny z podzbiorem \(B\)).
Jeśli \(\mathfrak {a}\leq \mathfrak {b}\) ale \(\mathfrak {a}\neq \mathfrak {b}\) (czyli zbiory \(A\) i \(B\) nie są równoliczne), to piszemy \(\mathfrak {a}<\mathfrak {b}\).
Zauważmy, że dla zbioru skończonego \(X\), zbiór podzbiorów tego zbioru \({\cal P}(X)\) ma zawsze więcej elementów niż zbiór \(X\),
\[{\cal P}(\emptyset )=\{\emptyset \},\]
\[{\cal P}\{a\}=\{ \emptyset , \{a\} \},\]
\[{\cal P}\{a,b\}=\{ \emptyset , \{a\}, \{b\}, \{a,b\} \}.\]
(Łatwo zauważyć, że jeśli zbiór \(X\) ma \(n\) elementów, to zbiór \({\cal P}(X)\) ma \(2^n\) elementów, co wyjaśnia występujące czasem oznaczenie zbioru podzbiorów \(X\) jako \(2^X\)).
Okazuje się, że dla wszystkich zbiorów moc zbioru jest silnie mniejsza niż moc zbioru jego podzbiorów. Twierdzenie to zostało odkryte i udowodnione przez Georga Cantora (1845–1918).
Dowód. Dla zbioru pustego twierdzenie jest prawdziwe, jak zauważyliśmy powyżej.
Weźmy zatem niepusty zbiór \(X\). Zauważmy, że
\[\# X\leq \# {\cal P}(X).\]
Faktycznie, funkcja \(g: X\ni x\to \{x\}\in {\cal P}(X)\) jest bijekcją z \(X\) na podzbiór \({\cal P}(X)\),
\[g: X\bij \{ \{x\} | x\in X \}.\]
Pozostaje wykazać, że \(\# X\neq \# {\cal P}(X)\).
Przypuśćmy zatem, że dla jakiegoś zbioru niepustego \(X\) mamy \(X\sim {\cal P}(X)\), czyli istnieje bijekcja
\[f: X\bij {\cal P}(X)\]
zatem \(f(x)\) jest pewnym podzbiorem \({\cal P}(X)\). Zdefiniujmy pewien podzbiór \(Z\) zbioru \(X\).
\[Z=\{ x\in X \mid x\notin f(x)\},\]
czyli \(Z\) jest podzbiorem złożonym z tych elementów zbioru \(x\), które nie należą do podzbioru danego przez \(f(x)\).
Skoro \(f\) jest bijekcją, to istnieje \(z\in X\) takie, że
\[Z=f(z).\]
Są dwie możliwości, albo \(z\in Z\) albo \(z\notin Z\). Jeśli \(z\in Z \) to, z definicji \(Z\), \(z\notin f(z)=Z\), co jest niemożliwe. Zatem, \(z\notin Z\), ale wtedy, znowu z definicji \(Z\) mamy \(z\in f(z)=Z\), znowu sprzeczność. Zatem, niemożliwe jest by była bijekcja między \(X\) a \({\cal P}(X)\). Zatem
\[\# X<\# {\cal P}(X).\]
□
Z tego twierdzenia wynikają od razu dwa wnioski.
Faktycznie:
\[\# \N <\# {\cal P}(\N ) < \# {\cal P}({\cal P}(\N ))<\ldots \]
Mamy zatem nieskończenie wiele różnych liczb kardynalnych, większych od danej liczby kardynalnej.
Drugi z wniosków mówi, że nie istnieje zbiór wszystkich zbiorów. Odkrycie tego faktu było sporym zaskoczeniem dla matematyków zajmujących się teorią mnogości w drugiej połowie XIX wieku, zwłaszcza dla Georga Cantora.
Wniosek 201. Nie istnieje zbiór wszystkich zbiorów.
Dowód. Przypuśćmy, że istnieje zbiór wszystkich zbiorów, \(Z\). Wtedy, zbiór jego podzbiorów jest zawarty w \(Z\). Jako podzbiór \(Z\) ma moc mniejszą lub równą mocy \(Z\), czyli jest
\[\# {\cal P}(Z)\leq \# Z,\]
a Twierdzenie 199 mówi, że jest to niemożliwe, bo zawsze
\[\# Z<\# {\cal P}(Z).\]
□
Zauważmy teraz, że zachodzi następujący fakt:
Dowód. Faktycznie, odwzorowanie, które ciągowi \(c\in C\) przyporządkowuje podzbiór \(\N \) złożony z takich i tylko takich elementów \(n\in \N \), że \(c_n=1\) jest w oczywisty sposób bijekcją. □
Uwaga 203. Wspomnieliśmy wyżej, że na przyszłym wykładzie wykażemy, że \(\R \sim C\). Widzimy zatem, że \(\R \sim {\cal P}(\N )\).
Przez dłuższy czas matematycy, przede wszystkim Georg Cantor, próbowali znaleźć odpowiedź na pytanie: czy jest jakiś zbiór \(H\), taki, że
\[\# \N <\# H<\# R=\# {\cal P}(\N ).\]
Cantor wysunął hipotezę (zwaną Hipotezą Continuum), która mówi, że takiego zbioru \(h\) nie ma, nie potrafił jednak tego udowodnić. I nic dziwnego, w połowie XX wieku okazało się, że ta hipoteza jest niezależna od aksjomatów teorii mnogości, to znaczy można przyjąć zarówno istnienie, jak i nieistnienie zbioru \(H\), nie dostając sprzeczności z aksjomatykę teorii mnogości. Zainteresowany czytelnik o pracach Gödla2 (1940), który wykazał niesprzeczność Hipotezy Continuum z aksjomatami teorii mnogości i Cohena3 (1963), który wykazał niezależność Hipotezy Continuum od tych aksjomatów, może poczytać np. w [9].
2 Kurt Gödel (1906–1978), austriacki logik i matematyk.
3 Paul Cohen (1934–2007), amerykański matematyk.