Twierdzenie Cantora i metoda przekątniowa

Q: Czy nieskończoność może być większa od innej nieskończoności?

Tak - w sensie mocy zbiorów. Nie da się sparować liczb rzeczywistych z naturalnymi, więc tych pierwszych jest „istotnie więcej", choć obu jest nieskończenie wiele.

Q: Dlaczego liczb wymiernych jest tyle samo co naturalnych?

Bo da się je ustawić w ciąg: wypisujemy ułamki w tabeli (licznik razy mianownik) i przechodzimy ją po przekątnych, pomijając powtórzenia. Każdy ułamek dostaje swój numer.

Q: Czy metoda przekątniowa działa też dla liczb wymiernych?

Nie - i to ważne. Zbudowana przekątną liczba ma zwykle rozwinięcie nieokresowe, więc nie jest wymierna. Nie powstaje więc żadna sprzeczność z przeliczalnością zbioru Q.

Q: Co to jest alef zero?

Symbol aleph_0 oznacza moc zbioru liczb naturalnych - najmniejszą nieskończoność. Moc zbioru liczb rzeczywistych to 2^aleph_0, czyli continuum.

Q: Czy hipoteza continuum jest prawdziwa?

Pytanie nie ma odpowiedzi w ramach standardowych aksjomatów - jest od nich niezależna. To jeden z najbardziej znanych przykładów problemu nierozstrzygalnego.

Twierdzenie Cantora

Dla każdego zbioru $X$ moc zbioru wszystkich jego podzbiorów jest większa od mocy samego $X$ :

$|X| < |\mathcal{P}(X)|.$

Wniosek (metoda przekątniowa): zbiór liczb rzeczywistych jest nieprzeliczalny - nie da się go ustawić w ciąg $x_1, x_2, x_3, \ldots$

Co znaczy „więcej” dla zbiorów nieskończonych

Dla zbiorów skończonych porównywanie liczności jest proste - wystarczy policzyć elementy. Dla nieskończonych Cantor zaproponował inne kryterium: dwa zbiory mają tę samą moc, jeśli da się je sparować element w element (istnieje bijekcja).

Ta definicja prowadzi do zaskakujących wniosków:

liczb parzystych jest tyle samo co wszystkich naturalnych (parujemy $n \leftrightarrow 2n$ ), choć parzyste są „połową” naturalnych;
liczb wymiernych też jest tyle samo co naturalnych, mimo że między dowolnymi dwiema liczbami wymiernymi leży nieskończenie wiele innych.

Zbiór, który da się ustawić w ciąg (sparować z liczbami naturalnymi), nazywamy przeliczalnym. Naturalne pytanie brzmi: czy każdy nieskończony zbiór jest przeliczalny? Cantor pokazał, że nie.

Dowód - metoda przekątniowa

Pokaż dowódUkryj dowód

Pokażemy, że liczb rzeczywistych z przedziału $(0, 1)$ nie da się ustawić w ciąg.

Krok 1. Zakładamy nie wprost, że się da. Istnieje więc ciąg $x_1, x_2, x_3, \ldots$ zawierający wszystkie liczby z przedziału $(0,1)$ . Zapisujemy je w postaci rozwinięć dziesiętnych:

$x_1 = 0{,}a_{11} a_{12} a_{13} \ldots$

$x_2 = 0{,}a_{21} a_{22} a_{23} \ldots$

$x_3 = 0{,}a_{31} a_{32} a_{33} \ldots$

gdzie $a_{ij}$ to $j$ -ta cyfra po przecinku $i$ -tej liczby.

Krok 2. Budujemy nową liczbę $y$ , patrząc na przekątną tej tabeli. Jej $n$ -tą cyfrę definiujemy tak, żeby różniła się od $a_{nn}$ :

$b_n = \begin{cases} 5, & \text{gdy } a_{nn} \neq 5, \\ 4, & \text{gdy } a_{nn} = 5. \end{cases}$

Otrzymujemy liczbę $y = 0{,}b_1 b_2 b_3 \ldots$ należącą do przedziału $(0,1)$ . Używamy tylko cyfr $4$ i $5$ , co z góry wyklucza kłopot z rozwinięciami typu $0{,}4999\ldots = 0{,}5000\ldots$

Krok 3. Sprawdzamy, gdzie jest $y$ na liście. Gdyby $y = x_n$ dla pewnego $n$ , to obie liczby musiałyby mieć identyczne rozwinięcia - w szczególności na $n$ -tym miejscu po przecinku. Ale z konstrukcji $b_n \neq a_{nn}$ , więc różnią się dokładnie na tym miejscu.

Krok 4. Sprzeczność. Liczba $y$ należy do przedziału $(0,1)$ , a nie występuje w ciągu, który miał zawierać wszystkie takie liczby. Założenie z kroku 1 jest fałszywe.

$\text{Zbiór } (0,1) \text{ jest nieprzeliczalny.} \qquad \blacksquare$

Dowód ogólny - zbiór potęgowy

Pokaż dowódUkryj dowód

Ta sama sztuczka działa dla dowolnego zbioru $X$ i jego rodziny podzbiorów $\mathcal{P}(X)$ .

Krok 1. Zakładamy nie wprost, że istnieje funkcja $f$ przyporządkowująca każdemu elementowi $x \in X$ pewien podzbiór $f(x) \subseteq X$ i obejmująca wszystkie podzbiory.

Krok 2. Budujemy podzbiór przekątniowy:

$D = \{ x \in X : x \notin f(x) \}.$

Do $D$ wrzucamy dokładnie te elementy, które nie należą do przypisanego im zbioru.

Krok 3. Pytamy, skąd bierze się $D$ . Skoro $f$ obejmuje wszystkie podzbiory, istnieje $d$ takie, że $f(d) = D$ . Pytamy teraz: czy $d \in D$ ?

gdyby $d \in D$ , to z definicji $D$ mielibyśmy $d \notin f(d) = D$ - sprzeczność;
gdyby $d \notin D = f(d)$ , to warunek z definicji $D$ jest spełniony, więc $d \in D$ - znów sprzeczność.

Krok 4. Wniosek. Funkcja obejmująca wszystkie podzbiory nie istnieje, czyli podzbiorów jest istotnie więcej niż elementów. $\blacksquare$

Ten sam schemat („zbiór tych, które nie zawierają samych siebie”) stoi za paradoksem Russella i - w wersji arytmetycznej - za twierdzeniami Gödla.

Konsekwencja: wieża nieskończoności

Twierdzenie Cantora można stosować w kółko:

$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \ldots$

Nie ma więc „największej nieskończoności” - jest ich nieskończenie wiele, ułożonych w rosnącą wieżę. Moc zbioru liczb naturalnych oznaczamy $\aleph_0$ (alef zero), a moc zbioru liczb rzeczywistych - continuum $\mathfrak{c} = 2^{\aleph_0}$ .

Hipoteza continuum

Skoro $|\mathbb{N}| < |\mathbb{R}|$ , powstaje pytanie: czy istnieje zbiór o mocy pośredniej? Cantor przypuszczał, że nie - to hipoteza continuum. Historia jej rozstrzygnięcia jest zdumiewająca:

w 1940 roku Kurt Gödel pokazał, że hipotezy nie da się obalić na gruncie standardowych aksjomatów teorii mnogości;
w 1963 roku Paul Cohen pokazał, że nie da się jej też udowodnić.

Hipoteza continuum jest więc niezależna od aksjomatów - można przyjąć ją albo jej zaprzeczenie i w obu przypadkach otrzymać spójną matematykę. Za ten wynik Cohen dostał medal Fieldsa.

Po co to komu

Informatyka teoretyczna. Programów jest przeliczalnie wiele (każdy to skończony napis), a funkcji z liczb naturalnych w naturalne - nieprzeliczalnie wiele. Wniosek: istnieją funkcje, których żaden program nie policzy. To pierwszy krok do problemu stopu i nierozstrzygalności.
Analiza matematyczna. Liczby algebraiczne (pierwiastki wielomianów o współczynnikach całkowitych) są przeliczalne, więc liczb przestępnych - jak $\pi$ czy $e$ - musi być nieprzeliczalnie wiele. Cantor udowodnił ich istnienie, nie wskazując ani jednej.
Metoda dowodu. Argument przekątniowy stał się osobnym narzędziem, używanym przez Gödla, Turinga i całą współczesną logikę.

Kto i kiedy

Georg Cantor opublikował pierwszy dowód nieprzeliczalności liczb rzeczywistych w 1874 roku, a słynny argument przekątniowy - w 1891. Teoria mnogości spotkała się z ostrą krytyką; Leopold Kronecker nazywał ją „matematyczną szarlatanerią” i blokował Cantorowi karierę.

Z czasem oceny się odwróciły. David Hilbert podsumował to zdaniem: „Nikt nas nie wypędzi z raju, który stworzył nam Cantor”. Dziś teoria mnogości jest fundamentem, na którym buduje się resztę matematyki. Zobacz też encyklopedyczne zestawienie: Twierdzenia Cantora.

Najczęstsze pytania

Czy nieskończoność może być większa od innej nieskończoności? Tak - w sensie mocy zbiorów. Nie da się sparować liczb rzeczywistych z naturalnymi, więc tych pierwszych jest „istotnie więcej”, choć obu jest nieskończenie wiele.

Dlaczego liczb wymiernych jest tyle samo co naturalnych? Bo da się je ustawić w ciąg: wypisujemy ułamki w tabeli (licznik razy mianownik) i przechodzimy ją po przekątnych, pomijając powtórzenia. Każdy ułamek dostaje swój numer.

Czy metoda przekątniowa działa też dla liczb wymiernych? Nie - i to ważne. Zbudowana przekątną liczba ma zwykle rozwinięcie nieokresowe, więc nie jest wymierna. Nie powstaje więc żadna sprzeczność z przeliczalnością zbioru $\mathbb{Q}$ .

Co to jest alef zero? Symbol $\aleph_0$ oznacza moc zbioru liczb naturalnych - najmniejszą nieskończoność. Moc zbioru liczb rzeczywistych to $2^{\aleph_0}$ , czyli continuum.

Czy hipoteza continuum jest prawdziwa? Pytanie nie ma odpowiedzi w ramach standardowych aksjomatów - jest od nich niezależna. To jeden z najbardziej znanych przykładów problemu nierozstrzygalnego.

Podsumowanie

Twierdzenie Cantora: zbiór podzbiorów jest zawsze istotnie większy od zbioru wyjściowego.
Metoda przekątniowa pokazuje, że liczb rzeczywistych nie da się ustawić w ciąg - są nieprzeliczalne.
Nie istnieje największa nieskończoność; moce zbiorów tworzą nieskończoną wieżę.
Hipoteza continuum (brak mocy pośredniej między $\mathbb{N}$ a $\mathbb{R}$ ) jest niezależna od aksjomatów teorii mnogości - Gödel i Cohen.
Ten sam argument przekątniowy stoi za paradoksem Russella, twierdzeniami Gödla i dowodem nierozstrzygalności problemu stopu.