Zbiory przeliczalne
Kapitoly: Zbiory, Działania na zbiorach, Zbiory przeliczalne, Paradoksy teorii mnogości
Przeliczalność zbioru to coś w rodzaju odpowiednika wielkości zbioru, bo w przypadku zbiorów nieskończonych nie da się posługiwać liczbą elementów – liczba elementów jest, niespodzianka… nieskończona. Wielkość zbioru nazywamy też jego mocą (dla zbioru skończonego to po prostu liczba elementów).
Wielkość zbioru nieskończonego
Określenie wielkości zbioru skończonego jest proste: liczymy jego elementy. Zbiór M = {a, b, c, d, e} ma więc 5 elementów (jego moc wynosi 5), co zapiszemy |M| = 5.
W przypadku zbiorów nieskończonych sytuacja jest wyraźnie bardziej skomplikowana. Jak moglibyśmy porównać wielkość zbiorów nieskończonych? Czy to w ogóle możliwe, czy może wszystkie zbiory nieskończone są „tak samo duże”?
Weźmy jako przykład zbiór liczb naturalnych i zbiór parzystych liczb naturalnych. Mamy więc zbiory ℕ = {1, 2, 3, 4, 5, 6, …} i S = {2, 4, 6, …}. Chciałoby się powiedzieć, że zbiór liczb naturalnych jest większy od zbioru liczb parzystych, bo liczby naturalne zawierają w sobie wszystkie liczby parzyste i do tego jeszcze jakieś dodatkowe elementy – liczby nieparzyste.
Moglibyśmy więc napisać, że zachodzi S ⊂ ℕ, czyli zbiór S jest podzbiorem właściwym zbioru ℕ. I moglibyśmy powiedzieć, że skoro S ⊂ ℕ, to zbiór ℕ jest większy – przecież zawiera więcej elementów niż zbiór S.
Jednym z powodów, dla których nie możemy mierzyć zbiorów relacją podzbioru, jest to, że zbiory mogą mieć różną wielkość, chociaż żaden z nich nie jest podzbiorem drugiego. Można to pokazać nawet na zbiorach skończonych: A = {1, 3, 4, 9} i B = {b, u, r, z, m}. Zachodzi: |A| = 4 i |B| = 5. Zbiór B jest większy od zbioru A, a przy tym nie zachodzi A ⊂ B. W przypadku zbiorów nieskończonych możemy to zobaczyć na liczbach parzystych i nieparzystych. Żaden z tych zbiorów nie jest podzbiorem drugiego.
Relacja podzbioru nie będzie więc idealnym kandydatem do rozstrzygania, czy jeden zbiór jest większy od drugiego.
Bijekcja
Spróbujmy innego podejścia. Mamy dwa zbiory, A i B. Możemy powiedzieć, że mają tę samą wielkość, jeśli istnieje między nimi odwzorowanie wzajemnie jednoznaczne, czyli bijekcja. Co to znaczy? Że weźmiemy element ze zbioru A, element ze zbioru B i utworzymy parę (a, b). Te elementy usuniemy ze zbiorów i działamy dalej. Jeśli uda nam się „opróżnić” oba zbiory, znaleźliśmy bijekcję.
Przykład na zbiorach skończonych: A = {a, b, c} i B = {1, 2, 3}. Pierwszą parą mogłaby być (a, 1), kolejną (b, 2), a na końcu (c, 3). Wyczerpaliśmy wszystkie elementy obu zbiorów, znaleźliśmy bijekcję. Ważne jest, że nie jest to jedyna bijekcja. Takie rozwiązanie też jest poprawne: (a, 3), (b, 1), (c, 2).
W przypadku zbiorów nieskończonych robi się już trochę ciekawiej. Spróbujmy z nieparzystymi i parzystymi liczbami naturalnymi. Intuicyjnie czujemy, że powinno ich być tyle samo. Sprawdźmy to. Weźmiemy pierwszą liczbę nieparzystą i przyporządkujemy jej pierwszą liczbę parzystą: (1, 2). Dalej drugą nieparzystą i drugą parzystą: (3, 4). I tak dalej. Dostajemy więc pary: (1, 2), (3, 4), (5, 6), (7, 8), … Moglibyśmy napisać, że każdej liczbie nieparzystej l odpowiada liczba parzysta l + 1, a każda liczba parzysta s jest obrazem liczby nieparzystej s − 1. Dla każdej liczby nieparzystej i dla każdej parzystej mamy więc jakąś parę, która tę liczbę zawiera. Zbiory liczb nieparzystych i parzystych są więc tak samo duże.
Liczby parzyste a naturalne
Teraz spróbujmy tego samego sposobu i porównajmy zbiór liczb naturalnych i parzystych. Mamy więc zbiory ℕ = {1, 2, 3, 4, 5, 6, …} i S = {2, 4, 6, …}. Intuicyjnie oczekujemy, że zbiór liczb naturalnych będzie większy.
Spróbujmy jednak znaleźć bijekcję. Możemy powiedzieć, że każdej liczbie naturalnej n przyporządkowujemy jej podwojenie, czyli 2n. W ten sposób dostaniemy pary (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Dla każdej liczby naturalnej n mamy więc parę (n, 2n), a dla każdej liczby parzystej s mamy parę (s/2, s). Znaleźliśmy bijekcję, zbiór liczb parzystych i zbiór liczb naturalnych są więc tak samo duże – mają tę samą moc.
Może się to wydawać dziwne, bo przecież liczby naturalne zawierają więcej elementów niż liczby parzyste. Liczby naturalne zawierają wszystkie liczby parzyste i do tego jeszcze wszystkie liczby nieparzyste. Mimo to potrafimy znaleźć bijekcję, więc oba zbiory są tak samo duże.
Porównanie z liczbami naturalnymi
Liczby naturalne tak naprawdę wyznaczają najmniejszą wielkość zbioru nieskończonego. To, czy jakiś inny zbiór ma tę samą wielkość co zbiór liczb naturalnych, często da się sprawdzić dość łatwo – wystarczy znaleźć bijekcję na liczby naturalne, co w praktyce oznacza, że wystarczy, gdy potrafimy elementy naszego zbioru M ponumerować, ustawić w kolejności.
Czyli jeśli potrafimy ustawić elementy zbioru tak, że wiemy, który element jest pierwszy, który drugi, trzeci, czwarty, dziesiąty itd., to zbiór jest tak samo duży jak ℕ. O takim zbiorze mówimy wtedy, że jest przeliczalny.
Łatwo zauważyć, że parzyste i nieparzyste liczby naturalne tworzą zbiory przeliczalne, bo umiemy wskazać pierwszą, drugą, trzecią itd. liczbę parzystą/nieparzystą. A co z parzystymi liczbami całkowitymi? Czyli zbiorem S = {…, −4, −2, 0, 2, 4, …}. Potrafimy je ustawić w kolejności? Potrafimy – wystarczy wziąć to samo uporządkowanie co poprzednio i zaraz za każdą dodatnią liczbą parzystą zapisać też jej ujemną wersję: S = {0, 2, −2, 4, −4, 6, −6, …}. Podobnie na przykład dla liczb całkowitych.
Ile jest liczb wymiernych
Ciekawszym przykładem są liczby wymierne, czyli ułamki. Potrafimy je ustawić w kolejności? Potrafimy, ale będzie to już trochę trudniejsze. Zbudujemy tabelę, która ma nieskończenie wiele wierszy i kolumn. W każdej komórce będzie ułamek. W n-tej kolumnie i m-tym wierszu będziemy mieli ułamek n/m. Czyli w 1. kolumnie i 2. wierszu mamy $\frac12$, a w trzeciej kolumnie i czwartym wierszu mamy 3/4.
$$\begin{array}{ccccc} 1/1&2/1&3/1&4/1&…\\ 1/2&2/2&3/2&4/2&…\\ 1/3&2/3&3/3&4/3&…\\ 1/4&2/4&3/4&4/4&…\\ …&…&…&…&… \end{array}$$
Jak teraz te liczby ustawić w kolejności, ponumerować? Nie możemy ich numerować wierszami ani kolumnami, bo od razu utonęlibyśmy w jednym wierszu/kolumnie. Zamiast tego weźmiemy liczby po przekątnych: (pierwsza przekątna:) 1/1, (druga przekątna:) 2/1, 1/2, (trzecia przekątna:) 3/1, 2/2, 1/3, (czwarta przekątna:) 4/1, 3/2, 2/3, 1/4, … Jest tam jeszcze mnóstwo powtarzających się ułamków, ale to nie przeszkadza. Bardziej przeszkadza to, że nie ma tam liczb ujemnych. To da się rozwiązać prosto: zawsze, gdy zapiszemy jakiś ułamek, umieścimy zaraz za nim jego ujemną wersję. A potem brakuje nam jeszcze na samym początku zera. I to już wszystko, mamy wszystkie liczby wymierne w ciągu.
Łącznie dostajemy więc ciąg: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …
Ile jest liczb rzeczywistych
Czy liczb rzeczywistych jest tyle samo co liczb naturalnych? Rozstrzygnięcie będzie jeszcze trudniejsze niż w przypadku liczb wymiernych. Przeprowadzimy dowód nie wprost. Załóżmy, że liczby rzeczywiste tworzą zbiór przeliczalny i że istnieje bijekcja na liczby naturalne. Załóżmy więc, że da się je ustawić w kolejności. I przyjmijmy, że to poniższe zestawienie jest tym uporządkowaniem:
$$\begin{array}{ccccccccc} 0,&3&5&2&2&4&6&0&\ldots\\ 0,&2&9&2&4&3&7&5&\ldots\\ 0,&7&2&3&0&8&4&5&\ldots\\ 0,&1&4&3&7&9&0&6&\ldots\\ 0,&0&8&6&5&7&5&8&\ldots\\ 0,&7&5&4&6&3&6&3&\ldots\\ 0,&3&4&1&9&7&0&0&\ldots\\ \ldots \end{array}$$
W tabeli jest pierwszych siedem liczb rzeczywistych w naszym uporządkowaniu. To uporządkowanie może być oczywiście dowolne, liczby nie muszą być ustawione według wielkości.
Zgodnie z założeniem w tej nieskończonej tabeli są ustawione wszystkie liczby rzeczywiste. (Tabela jest znowu nieskończona, tutaj jest tylko pierwszych siedem wierszy.) Teraz spróbujemy znaleźć/zbudować taką liczbę, która jest rzeczywista, ale nie ma jej w tej tabeli. Jeśli znajdziemy taką liczbę, otrzymamy sprzeczność z tym, że w tabeli są wszystkie liczby rzeczywiste, z czego możemy dalej wywnioskować, że zbiór liczb rzeczywistych nie jest przeliczalny.
Liczbę, której nie ma w tabeli, zbudujemy tak:
$$\begin{array}{ccccccccc} 0,&\fbox{3}&5&2&2&4&6&0&\ldots\\ 0,&2&\fbox{9}&2&4&3&7&5&\ldots\\ 0,&7&2&\fbox{3}&0&8&4&5&\ldots\\ 0,&1&4&3&\fbox{7}&9&0&6&\ldots\\ 0,&0&8&6&5&\fbox{7}&5&8&\ldots\\ 0,&7&5&4&6&3&\fbox{6}&3&\ldots\\ 0,&3&4&1&9&7&0&\fbox{0}&\ldots\\ \ldots \end{array}$$
Zaczniemy od tego, że napiszemy 0,… Tak będzie na początku wyglądać nasza nowa liczba rzeczywista. Na pierwszym miejscu po przecinku będzie taka cyfra, której nie ma na pierwszym miejscu w pierwszej liczbie rzeczywistej naszego uporządkowania (w tabeli jest to zaznaczone ramką). Jest tam cyfra 3, więc wybierzemy na przykład 1 i dostajemy liczbę 0,1…
Idziemy dalej. Na drugim miejscu będzie cyfra, której nie ma na drugim miejscu drugiej liczby rzeczywistej. Jest tam 9, więc na przykład 2. Dostaniemy liczbę 0,12… Na trzecim miejscu będzie cyfra, która różni się od trzeciej cyfry trzeciej liczby rzeczywistej. Jest tam 3, więc wybierzemy na przykład 7. Dostajemy 0, 127…
I tak dalej, i tak dalej. Zawsze na n-tej pozycji nowej liczby będzie cyfra, która różni się od cyfry na n-tej pozycji n-tej liczby w naszym uporządkowaniu.
Co w ten sposób uzyskamy? Uzyskamy liczbę, która różni się od wszystkich liczb w naszym uporządkowaniu co najmniej jedną cyfrą. Weźmy ostatni tymczasowy wynik: 0,127… Ta liczba na pewno różni się od pierwszej liczby w naszym uporządkowaniu co najmniej pierwszą cyfrą – bo tak ją zbudowaliśmy. Od drugiej liczby różni się co najmniej drugą cyfrą. Od trzeciej trzecią. Ogólnie ta nowa liczba różni się od liczby, która w uporządkowaniu stoi na n-tym miejscu, co najmniej cyfrą na n-tej pozycji.
Tej nowo zbudowanej liczby nie znajdziemy więc w tabeli, która miała przedstawiać bijekcję między liczbami naturalnymi a liczbami rzeczywistymi. Liczb rzeczywistych jest więc więcej niż liczb naturalnych. Liczby rzeczywiste nie tworzą zbioru przeliczalnego, tworzą zbiór nieprzeliczalny.