Jak to się dzieje, że zbiór wszystkich zbiorów nie istnieje?

Mając dwa zbiory skończone z łatwością możemy stwierdzić, który z nich ma więcej elementów. Wystarczy policzyć. A czy można porównywać liczność zbiorów nieskończonych? Czy ma to w ogóle sens? W końcu nieskończoność to nieskończoność. A może jednak nie? Cóż, okazuje się, że nieskończoność w matematyce to sprawa niezwykle ciekawa! W tym wpisie czeka nas wycieczka do świata nieskończoności gdzie poznamy liczby kardynalne i zaznajomimy się nieco z tym światem, który jest inny od znanego nam świata skończonego. Będzie to wycieczka długa, ale zaręczam, że warto ją odbyć!

Rozważmy cztery dobrze nam znane zbiory liczbowe, tzn. zbiór \(\mathbb N\) liczb naturalnych, \(\mathbb Z\) liczb całkowitych, zbiór \(\mathbb Q\) liczb wymiernych oraz zbiór \(\mathbb R\) liczb rzeczywistych. Który z tych zbiorów zawiera najwięcej, a który najmniej elementów? Możemy na tak postawiony problem spojrzeć dwojako. Po pierwsze nie da się nie zauważyć, że każda liczba naturalna jest całkowita, każda całkowita jest jednocześnie wymierna, a każda liczba wymierna jest rzeczywista. To znaczy mamy następujące zawierania: \[\mathbb N\subset\mathbb Z\subset\mathbb Q\subset\mathbb R.\] Do tego, nie mamy żadnego zawierania w stronę przeciwną gdyż istnieją liczby całkowite, które nie są naturalne (np. \(-1\)), wymierne, które nie są całkowite (np. \(\frac 13\)) oraz liczby rzeczywiste nie będące wymiernymi (np. \(\sqrt{7}\)). Możemy więc powiedzieć, że liczb rzeczywistych jest najwięcej, potem trochę mniej jest liczb wymiernych, dalej znowu trochę mniej całkowitych, a naturalnych jest najmniej spośród nich wszystkich.

Z drugiej jednak strony, gdybyśmy chcieli policzyć ile jest elementów w każdym z tych zbiorów, to nigdy nie skończylibyśmy liczyć bo wszystkie te zbiory są nieskończone. Możemy więc rozumować inaczej i powiedzieć, że wszystkie mają tyle samo elementów, tj. nieskończenie wiele. W końcu nieskończoność to nieskończoność.

No i które rozumowanie jest poprawne? Okazuje się, że oba są błędne. Bo mimo iż nigdy byśmy nie skończyli liczyć elementów zbiorów nieskończonych, to mając dwa zbiory nieskończone możemy, w prosty wbrew pozorom sposób, porównywać, który z nich ma więcej elementów i przypisywać im tzw. liczby kardynalne, mówiące ile dokładnie elementów ma dany zbiór. W jaki sposób? Zobaczymy, że idea jest bardzo prosta! Ideę tę odkrył niemiecki matematyk Georg Cantor w XIX wieku. Choć jego rozważania miały swój początek w zupełnie innym zagadnieniu, kompletnie nie związanym z porównywaniem liczby elementów zbiorów nieskończonych. Szcegóły jednak, to już materiał na zupełnie inny wpis.

Gdybyśmy mieli dwa duże worki ziemniaków i dostali zadanie stwierdzenia, w którym z nich jest więcej tychże ziemniaków, to można by to było zrobić bardzo łatwo. Wystarczyłoby policzyć ile jest ziemniaków w jednym worku, a ile w drugim. A może moglibyśmy sobie jakoś życie ułatwić? W końcu nie musimy wiedzieć ile jest ziemniaków w każdym z worków, tylko w którym jest więcej. Zerknijmy na inny przykład.

Wyobraźmy sobie, że przybyliśmy na pewne przyjęcie. Przybyliśmy jako pierwsi więc możemy zobaczyć puste miejsca zaproszonych gości. Przy każdym znajduje się talerz wraz z widelcem oraz nożem. Gdyby się okazało, że np. widelców jest za mało, to byśmy byli w stanie dostrzec to bardzo szybko. W takiej sytuacji byłby co najmniej jeden talerz jedynie z nożem, bez widelca. Przy założeniu naturalnie, że osoby odpowiedzialne za nakrywanie do stołów zawsze kładą przy talerzu nóż oraz widelec gdy oba są dostępne.

I to jest właśnie idea porównywania zbiorów nieskończonych! Zamiast liczyć elementy będziemy łączyć je w pary!! Jeżeli znajdziemy sposób na sparowanie wszystkich elementów obu zbiorów, to oznacza to, że mają one tyle po samo elementów. Prześledźmy tę ideę najpierw na przykładzie skończonym, tj. na przykładzie z naszymi ziemniakami. Później przejdziemy do nieskończoności. Choć w przypadku nieskończonym będziemy musieli być bardzo ostrożni. Świat nieskończony istotnie różni się od skończonego!

W przykładzie z ziemniakami mieliśmy dwa ogromne worki ziemniaków. Naszym celem jest stwierdzenie, w którym z nich znajduje się ich więcej. Możemy to zrobić bez liczenia. Wystarczy jednocześnie wyciągać z każdego worka po jednym ziemniaku. Czyli wkładamy lewą rękę do jednego worka, prawą do drugiego, łapiemy po ziemniaku, wyciągamy i odkładamy. Jeżeli liczba ziemniaków w workach się różni, to prędzej czy później dojdziemy do momentu, w którym jeden worek będzie pusty, a drugi nie. Ten, w którym został co najmniej jeden ziemniak jest tym, gdzie było więcej ziemniaków. Tym sposobem nie trzeba sobie zaprzątać głowy jakimkolwiek liczeniem. Należy jedynie pilnować aby w każdym kroku wyciągać jednocześnie po jednym ziemniaku z każdego worka.

Może się wydawać, że w przypadku nieskończonym taki pomysł nie zadziała bo przecież również nigdy takiego wyciągania byśmy nie skończyli. Więc jak tu ta ponoć błyskotliwa idea miałaby zadziałać? Okazuje się, że często możemy jakimś bystrym sposobem sparować za jednym zamachem elementy dwu nieskończonych zbiorów. Zerknijmy na dwa przykłady.

Weźmy na początek zbiór \(\mathbb N\) liczb naturalnych oraz zbiór liczb naturalnych parzystych (oznaczmy go tutaj \(\mathbb P\)). Każdej liczbie naturalnej \(n\in\mathbb N\) możemy w łatwy sposób przypisać liczbę parzystą. Wystarczy pomnożyć ją przez 2.

Innymi słowy określiliśmy funkcję \(f:\mathbb N\to\mathbb P\) daną prostym wzorem \(f(n)=2n\). Przyjrzyjmy się nieco bliżej temu co się tutaj właśnie stało. A stało się wbrew pozorom sporo!

Zauważmy, że każda znajdująca się w górnym rzędzie liczba naturalna ma swoją parę na dole. I gwoli ścisłości, żadne dwie liczby naturalne nie mają dwu takich samych par! Podobnie, znajdujące się na dole liczby parzyste również mają swoje pary wśród liczb na górze i również każda liczba z dołu ma inną parę bo ani na górze żadne liczby się nie powtarzają ani na dole. Do tego na górze znajdują się wszystkie liczby naturalne, a na dole wszystkie parzyste.

Udało nam się więc liczby naturalne połączyć w pary z parzystymi. Czyżby więc wychodziło na to, że jest ich tyle samo? Że liczb naturalnych jest tyle samo i to mimo tego, że każda liczba ze zbioru \(\mathbb P\) jest naturalna oraz istnieją liczby naturalne nie będące parzystymi?? Okazuje się że tak, jest ich tyle samo! Połączyliśmy elementy dwu tych zbiorów w pary tak jak w pary połączone są noże i widelce przy nakryciach do stołu! I to w taki sposób, że nie zostało nic bez pary!

W tym miejscu po raz pierwszy uwidacznia się istotna różnica między zbiorami skończonymi, a tymi, które skończone nie są. Sparowaliśmy elementy dwu zbiorów gdzie jeden jest właściwym podzbiorem drugiego tzn. jest w nim zawarty (\(\mathbb P\subset\mathbb N\)) oraz istnieją elementy w \(\mathbb N\) niebędące w \(\mathbb P\). Czyli właściwa, różna od całości część zbioru ma dokładnie tyle samo elementów co cały zbiór. Coś co w świecie skończonym jest niemożliwe!!

Gdybyśmy mieli dwa takie zbiory skończone \(A, B\), że \(A\subset B\) oraz \(A\neq B\), to oznaczałoby to, że \(B\) ma więcej elementów i nigdy nie udałoby się nam ich wszystkich sparować z elementami zbioru \(A\) tak aby każdy miał inną parę. Trochę tak jakbyśmy mieli 15 widelców i 20 noży. Udałoby się nam stworzyć pełny zestaw sztućców co najwyżej dla 15 talerzy. W takiej sytuacji zawsze co najmniej 5 noży nie będzie miało swojego widelca.

Ponieważ jednak zbiory \(\mathbb N\) oraz \(\mathbb P\) są nieskończone, to… możemy wybierać z nich elementy w nieskończoność. I ta ,,drobna” różnica sprawia, że nawet mimo tego iż pozornie liczb naturalnych wydaje się więcej, to nigdy nie zabraknie w zbiorze \(\mathbb P\) liczb parzystych. Dlatego jesteśmy w stanie każdej liczbie naturalnej znaleźć parę wśród liczb parzystych z \(\mathbb P\). W przypadku zbiorów skończonych, tak jak w przypadku worków z ziemniakami, w końcu w którymś zabraknie elementów.

Jak widzimy świat skończony różni się od nieskończonego. A to dopiero początek niezwykle ciekawych rzeczy dziejących się w tym drugim! Swoją drogą zbiory skończone lub mające tyle samo elementów co \(\mathbb N\) nazywamy przeliczalnymi.

Reasumując, dotychczas znaleźliśmy przykład dwu różnych zbiorów nieskończonych o tej samej liczbie elementów. Dodatkowo mamy prosty sposób aby pokazać, że jakiś zbiór \(A\) ma tyle samo elementów co zbiór liczb naturalnych. Wystarczy elementy tego zbioru ustawić w ciąg nieskończony (bez żadnych powtórzeń) i zadbać o to, aby w tym ciągu pojawił się każdy element zbioru \(A\). Jeśli nam się to uda, oznacza to, że \(A\) ma tyle samo elementów co \(\mathbb N\). Zanim przekujemy tę ideę w konkretną matematykę, przejdziemy przez jeszcze kilka przykładów. Pokażemy m.in., że nie każdy zbiór da się ustawić w ciąg. Czyli istnieją zbiory nieprzeliczalne, a co za tym idzie, mniejsze i większe nieskończoności!! Późniejszy, ściślejszy matematyczny opis naszych rozumować pozwoli nie tylko zrobić porządek, ale również spojrzeć z szerszej perspektywy na rozważane przykłady.

Sposób rozumowania w ostatnim przykładzie możemy de facto zastosować do każdego nieskończonego podzbioru zbioru \(\mathbb N\) aby pokazać, że ma on tyle samo elementów co \(\mathbb N\). Nawet jeśli usuniemy z \(\mathbb N\) jakieś liczby w sposób bardzo fikuśny. Zawsze możemy to co zostanie ustawić w ciąg porządkując liczby np. rosnąco.

Przyjrzyjmy się teraz zbiorowi \(\mathbb Z\) liczb całkowitych. Okazuje się, że zbiór ten również jest przeliczalny! Bardzo łatwo jesteśmy w stanie jego elementy ustawić w ciąg: \[0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ 4,\ -4,\ 5,\ -5,\ \ldots \] Idea jest chyba jest jasna. Najpierw 0, a potem liczba raz dodatnia, raz ujemna uszeregowane względem wzrastającej wartości bezwzględnej. Oczywiste jest, że w tym ciągu znajdzie się każda liczba całkowita. Warto to podkreślić aby nie ulec złudzeniu, że elementy każdego zbioru nieskończonego da się ustawić w ciąg! Czyli zbiór \(\mathbb Z\) również jest przeliczalny! Swoją drogą, możemy funkcję parującą elementy zbiorów \(\mathbb N\) oraz \(\mathbb Z\) zapisać przy pomocy jawnych wzorów.
\[
F(n)=\left\{\begin{array}{lll}
\frac n2 & \textrm{ gdy } & n\textrm{ jest parzyste,}\\
& & \\
-\frac{n-1}{2} & \textrm{ gdy } & n\textrm{ jest nieparzyste}\\
\end{array}\right.
\] Oznaczmy tę funkcję dużą literą \(F\). Jeszcze do niej wrócimy w dalszej części. Korzystając z funkcji podłoga, możemy posłużyć się jednym wzorem \[F(n)=(-1)^n \left\lfloor\frac n2\right\rfloor\]

Spójrzmy teraz na zbiór \(\mathbb Q\) liczb wymiernych. Jest to zbiór znacznie gęściej upakowany na osi liczbowej niż równomiernie rozłożone co 1 liczby całkowite. Między dowolne dwie liczby wymierne jesteśmy w stanie bez problemu wcisnąć nieskończenie wiele innych liczb wymiernych. Gdybyśmy chcieli je zaznaczyć na osi liczbowej, to byłoby zatrzęsienie tych liczb. Niemal cała oś byłaby nimi pokryta. Tak na marginesie, w topologii istnieje pojęcie zbioru gęstego. Mimo swej gęstości także i ten zbiór jest przeliczalny!!

Spróbujmy to udowodnić. Bez wątpienia liczb wymiernych jest co najmniej tyle co liczb naturalnych bo każda liczba naturalna jest także wymierna. Przypomnijmy, że wymierne to liczby postaci \(\frac ab\), gdzie \(a,b\in\mathbb Z\) oraz \(b\neq 0\). Przy czym, takie przedstawienie liczby wymiernej nie jest jednoznaczne. Każda liczba wymierna ma nieskończenie wiele przedstawień jako ułamek zwykły np. \[\frac 23=\frac 46=\frac 69=\frac{8}{12}=\cdots\] Zatem ułamków nie może być mniej niż liczb wymiernych. Każdy taki ułamek \(\frac ab\) możemy utożsamiać z parą uporządkowaną (tj. taką gdzie liczy się kolejność) liczb całkowitych, gdzie \(b\neq 0\). Dla przejrzystości dowodu ustawimy najpierw w ciąg ułamki gdzie \(a,b>0\).

Ustawmy ułamki (gdzie \(a,b>0\)) w ciąg następująco: \[\frac 11,\ \frac 12,\ \frac 21,\ \frac 13,\ \frac 22,\ \frac 31,\ \frac 14,\ \frac 23,\ \frac 32,\ \frac 41,\ \frac 15,\ \frac 24,\ \frac 33,\ldots\]

Idea być może nie jest tak oczywista do dostrzeżenia na pierwszy rzut oka, ale jest bardzo prosta. Najpierw bierzemy te ułamki \(\frac ab\), gdzie \(a+b=2\), w dalszej kolejności te gdzie \(a+b=3\), \(a+b=4\) itd. Natomiast w obrębie każdej z grup porządkujemy ułamki względem wzrastającego licznika.

Swoją drogą zbiór par uporządkowanych liczb naturalnych (tj. iloczyn kartezjański \(\mathbb N\times\mathbb N\)) możemy sparować ze zbiorem \(\mathbb N\) poprzez funkcję \(f:\mathbb N\times\mathbb N\to\mathbb N\) daną wzorem \[f(a,b)=2^{a-1}\cdot (2b-1)\]

Ale wróćmy do naszego ciągu ułamków. W ciągu tym znajdzie się każdy ułamek \(\frac ab\) bo suma \(a+b\) jest skończona dla każdego z nich i jest tylko skończenie wiele ułamków o sumie licznika i mianownika mniejszej niż lub równej \(a+b\). Co oczywiste, każdy dodatni ułamek pojawi się w tym ciągu dokładnie raz. Czyli zbiór ułamków dodatnich jest przeliczalny! W szczególności przeliczalny jest również zbiór liczb wymiernych dodatnich! Nietrudno już teraz pokazać, że jeżeli dorzucimy ułamki ujemne to nadal będziemy mieć zbiór przeliczalny. Wystarczy po każdym ułamku \(\frac ab\) wcisnąć ułamek \(-\frac ab\) otrzymując ciąg \[\frac 11,\ -\frac 11,\ \frac 12,\ -\frac 12,\ \frac 21,\ -\frac 21,\ \frac 13,\ -\frac 13,\ \frac 22,-\frac 22,\ \frac 31,\ -\frac 31,\ \frac 14,\ -\frac 14,\ \cdots \] Jeżeli następnie na początek dodamy jeszcze ułamek \(\frac 01\), to w tak otrzymanym ciągu ułamków znajdziemy wszystkie liczby wymierne co pokazuje, że jest to zbiór przeliczalny.

Dotychczasowe przykłady mogą powodować mylne wyobrażenie, że każdy zbiór nieskończony jest przeliczalny. Nie jest to prawda. Podamy teraz przykład zbioru nieprzeliczalnego, którym jest np. zbiór liczb rzeczywistych. Jego elementów nie się ustawić w ciąg! Ma on za dużo elementów aby to się udało!

Zrobimy to pokazując, że zbiór liczb rzeczywistych z przedziału \([0,1]\) jest nieprzeliczalny. Ponieważ \([0,1]\subset\mathbb R\), to wynika z tego, że i cały zbiór liczb rzeczywistych nie jest przeliczalny. Jak wiemy każdej liczbie \(a\in [0,1]\) możemy przyporządkować jej rozwinięcie w ułamek dziesiętny. Przy czym, dla pewnych liczb nie jest ono jednoznaczne. Wiemy ze szkoły, że każda liczba rzeczywista różna od 0 o skończonym rozwinięciu dziesiętnym, ma również rozwinięcie, w którym od pewnego momentu występują same dziewiątki. Przykładowo
\[
\begin{array}{lll}
0,3 & = & 0,299999\ldots\\
0,74 & = & 0,739999\ldots\\
1 & = & 0,999999\ldots
\end{array}
\] Jeżeli założymy, że wykluczymy wszystkie takie rozwinięcia dziesiętne, gdzie od pewnego miejsca występują same dziewiątki, to wtedy z każdą liczbą \(a\in [0,1]\) możemy w sposób jednoznaczny stowarzyszyć rozwinięcie dziesiętne. Przy czym, jeżeli rozwinięcie jest skończone, to traktujemy je jakby po ostatniej cyfrze były już tylko same zera. Załóżmy teraz, że udało nam się liczby z przedziału \([0,1]\) ustawić w nieskończony ciąg \(a_1,a_2,a_3,\ldots,a_n,\ldots\) Np. jakoś następująco:
\[
\begin{array}{lll}
a_1 & = & 0,2654645643\ldots\\
a_2 & = & 0,8132132121\ldots\\
a_3 & = & 0,5000000000\ldots\\
a_4 & = & 0,6654658882\ldots\\
a_5 & = & 0,7854932145\ldots\\
a_6 & = & 0,1111111111\ldots\\
… &&
\end{array}
\] Skonstruujemy teraz liczbę, która w tym ciągu się nie pojawia. Zrobimy to bardzo prosto. Z każdej liczby naszego ciągu wybieramy po jednej cyfrze jej rozwinięcia dziesiętnego. Dokładniej, z liczby \(a_n\) bierzemy cyfrę \(c_{n}\) znajdującą się na \(n\)-tej pozycji po przecinku. Teraz, jeżeli \(c_n\) jest mniejsze od 9, to zwiększamy ją o 1 otrzymując cyfrę \(d_n=c_n+1\). Natomiast, gdy \(c_n=9\), to przyjmujemy, że \(d_n=0\). korzystając z cyfr \(d_n\) możemy utworzyć liczbę \(x\in[0,1]\) przyjmując, że kolejne cyfry jej rozwinięcia dziesiętnego to \(d_1, d_2, d_3,\ldots\). Korzystając z naszego ciągu \((a_n)\) otrzymalibyśmy liczbę \[x=0,321502\ldots\]

I teraz wystarczy zauważyć, że liczba ta różni się od każdej liczby z ciągu \((a_n)\) bo ma inną cyfrę na \(n\)-tym miejscu swojego rozwinięcia od liczby \(a_n\)! Mamy więc sprzeczność z założeniem, że ciąg \((a_n)\) zawiera wszystkie liczby z przedziału \([0,1]\)! Choć tutaj jeszcze trzeba zauważyć, że liczba \(x\) na pewna nie ma w swym rozwinięciu od pewnego miejsca samych dziewiątek. Wynika to z tego, że jest nieskończenie wiele liczb w \([0,1]\), które nie mają ósemek w swoim rozwinięciu dziesiętnym.

Udało się nam pokazać, że liczb z przedziału \([0,1]\) jest nieprzeliczalnie wiele, jest ich więcej niż liczb naturalnych. Okazuje się więc, że mamy różne nieskończoności!

Ale przejdźmy już do konkretów i spróbujmy teraz te rozważania przekuć w matematykę. Pomysł parowania elementów dwu zbiorów polega na niczym innym jak na znalezieniu odpowiedniej funkcji z jednego do drugiego. Takie np. ustawienie elementów jakiegoś zbioru \(A\) w ciąg to nic innego jak określenie odpowiedniej funkcji \(\mathbb N\to A\). Aby w pełni zrozumieć tę ideę i zdefiniować ściśle w jaki sposób w ogóle porównywać liczby elementów zbiorów nieskończonych musimy wyróżnić pewne trzy rodzaje funkcji zwane dźwięcznie iniekcją, suriekcją oraz bijekcją.

Iniekcja, zwana inaczej funkcją różnowartościową lub funkcją 1-1, to taka funkcja, która dwóm różnym argumentom przypisuje różne wartości. Lub to samo inaczej: żadnym dwóm argumentom nie jest przypisana ta sama wartość. Mówiąc matematycznie, funkcję \(f:A\to B\) nazywamy iniekcją, o ile dla dowolnych \(x,y\in A\) spełniony jest warunek \[x\neq y\Rightarrow f(x)\neq f(y).\]

Gdybyśmy, tak jak czasami w szkole, narysowali funkcję jako graf ze strzałkami, to koniec każdej strzałki wylądowałby w innym miejscu.

Na rysunku powyżej, po lewej mamy przykład iniekcji. Każda strzałka kończy się w innym elemencie przeciwdziedziny \(B\). Tutaj warunek \(x\neq y\Rightarrow f(x)\neq f(y)\) jest spełniony dla wszystkich \(x,y\in A=\{a,b,c,d\}\). Po prawej zaś mamy przykład funkcji, która iniekcją nie jest. Dwie strzałki (zaznaczone na zielono) kończą się w elemencie \(c\in B\), tzn. wartość tej funkcji dla argumentu \(c\in A\) jest taka sama jak dla argumentu \(d\in A\). Czyli stosowny warunek nie jest spełniony i funkcja ta nie jest różnowartościowa.

Przykłady iniekcji już mieliśmy okazje zobaczyć w tym wpisie. Jednym z przykładów jest określona wcześniej funkcja \(F:\mathbb N\to\mathbb Z\). Również funkcja \(G: \mathbb N\to\mathbb Z\) taka, że \(G(n)=n\) jest przykładem funkcji różnowartościowej.

Drugim ważnym rodzajem funkcji jest tzw. suriekcja zwana również funkcją na. Jest to każda taka funkcja \(f:A\to B\), w której zbiór wartości \(f(A)\) pokrywa się ze zbiorem \(B\) (tj. \(f(A)=B\)). Tzn. dla każdego \(y\in B\) istnieje taki argument \(x\in A\), że \(f(x)=y\). Takich argumentów może być naturalnie więcej niż jeden dla danego \(y\in B\). Gdybyśmy spojrzeli na graf takiej funkcji, to dla każdego elementu przeciwdziedziny istniałaby co najmniej jedna strzałka, która w tym elemencie by się kończyła.

Powyżej mamy po prawej funkcję, która jest przykładem suriekcji (zauważmy, że zarazem nie jest to iniekcja). W każdym elemencie przeciwdziedziny kończy się co najmniej jedna strzałka. Natomiast po lewej, jak widzimy, są dwa elementy (zaznaczone na zielono), w których nie kończy się żadna strzałka.

Czasami w książkach matematycznych można spotkać sformułowanie, że funkcja \(f:A\to B\) odwzorowuje zbiór \(A\) na zbiór \(B\). Oznacza ono, ni mniej ni więcej, że funkcja \(f\) jest po prostu suriekcją.

Pojęcie suriekcji pozwala nam nieco ogólniej spojrzeć na zbiory przeliczalne. Otóż, zbiór \(A\) jest przeliczalny jeżeli istnieje suriekcja \(\mathbb N\to A\).

Zdefiniowana wcześniej funkcja \(F:\mathbb N\to\mathbb Z\) jest nie tylko iniekcją, lecz również suriekcją! Natomiast również wspominana wcześniej funkcja \(G\) już suriekcją nie jest. Ogólnie, funkcja może być iniekcją, suriekcją, jednym i drugim jednocześnie lub żadnym z tych rodzajów funkcji. Funkcje, które są zarówno iniekcją jak i suriekcją noszą specjalną nazwę bijekcji.

Bijekcja to właśnie nic innego jak funkcja, która pozwala elementy dwu zbiorów połączyć w pary. Aby funkcja \(f:A\to B\) była bijekcją, to muszą być spełnione następujące warunki:

• Każdemu argumentowi \(a\in A\) jest przyporządkowany dokładnie jeden element \(b\in B\). Co prawda ten warunek jest spełniony dla każdej funkcji, ale w kontekście łączenia w pary warto go uwypuklić.
• Różnym argumentom z \(A\) przyporządkowane są różne wartości w \(B\) (tzn. \(f\) jest 1-1).
• Dla każdego elementu \(b\in B\) istnieje argument \(a\in A\) taki, że \(f(a)=b\). Wobec warunku poprzedniego, jest dokładnie jeden taki argument.

W kontekście grafów i strzałek, bijekcja to taka funkcja, gdzie z każdego argumentu dziedziny wychodzi dokładnie jest strzałka (jak w przypadku każdej funkcji) oraz w każdym elemencie przeciwdziedziny kończy się dokładnie jedna strzałka. I nie ma elementu przeciwdziedziny, w którym żadna strzałka by się nie kończyła. Tak jak na poniższym rysunku funkcja po prawej jest właśnie przykładem bijekcji.

Nasza, zdefiniowana wcześniej, funkcja \(F\) jest właśnie bijekcją.

Wróćmy na chwilę do zbiorów skończonych. Gdy zbiór \(A\) ma inną liczbę elementów niż zbiór \(B\), to nie istnieje bijekcja między nimi. Gdy zbiór \(A\) ma więcej elementów, to nie istnieje iniekcja \(A\to B\), gdy zaś zbiór \(B\) ma elementów więcej, to nie istnieje suriekcja \(A\to B\). Innymi słowy bijekcja istnieje tylko wtedy, gdy zbiory \(A\) oraz \(B\) mają tę samą liczbę elementów.

I to jest właśnie idea parowania elementów przekuta w matematykę. Dokładniej, mówimy, że zbiory \(A\) oraz \(B\) są równoliczne gdy istnieje bijekcja \(A\to B\). Istnienie bijekcji między zbiorami oznacza, że mają one po tyle samo elementów. Fakt ten oznaczamy \(A\sim B\).

To co zrobiliśmy, to dosyć powszechny w matematyce sposób uogólniania pewnych idei. Pierwotnego pomysłu, czyli liczenia elementów zbiorów skończonych nie dało się przenieść do świata zbiorów nieskończonych. Zatem znaleźliśmy (lub raczej G. Cantor znalazł) inny, równoważny sposób określenia w znanym nam, skończonym świecie tego co oznacza, że dwa zbiory mają tyle samo elementów (tj. istnieje bijekcja między nimi). I okazało się, że ten nowy sposób da się już przenieść do świata nieskończonego.

Zwróćmy uwagę, że istnienie bijekcji \(A\to B\) oznacza, że istnieje również bijekcja \(B\to A\). Nietrudno się o tym przekonać. Niezbyt formalnie możemy to pokazać dosyć łatwo. Ponieważ bijekcja \(A\to B\), to nic innego jak sparowanie elementów dwu zbiorów, to wystarczyłoby na grafie takiej funkcji odwrócić strzałki w drugą stronę.

Istnienie naszej funkcji \(F\) mówi nam, że zbiory liczb naturalnych oraz całkowitych mają po tyle samo elementów! I to mimo iż każda liczba naturalna jest całkowita, lecz nie na odwrót! Coś co w świecie skończonym jest niemożliwe! A to dopiero początek rzeczy niezwykłych!

Każdemu zbiorowi skończonemu możemy przypisać liczbę naturalną będącą liczbą jego elementów. Liczby oznaczające liczbę elementów jakiegoś zbioru (niekoniecznie skończonego!) to tzw. liczby kardynalne. Każda liczba naturalna (oraz zero) jest więc, w szczególności, liczbą kardynalną. Nie będziemy tu przedstawiać formalnej definicji tych liczb bo nieco to już wykracza poza ramy tego wpisu.

Liczbę kardynalną oznaczającą liczbę elementów zbioru liczb naturalnych (a więc i całkowitych!!) oznaczamy \(\aleph_0\) i czytamy alef zero. Jest to najmniejsza liczba kardynalna nieskończona. Z kolei jeśli chodzi o liczbę kardynalną oznaczającą liczbę elementów zbioru \([0,1]\) (a także zbioru \(\mathbb R\) jak pokażemy!) to oznaczamy ją \(\mathfrak c\) i nazywamy continuum.

Liczbę elementów zbioru \(A\) nazywamy jego mocą. Czyli powiemy, że zbiór liczb naturalnych jest mocy \(\aleph_0\). Stosowane są różne oznaczenia mocy zbioru: \[|A|,\ \overline{\overline{A}},\ \# A,\ n(A).\] Najpopularniejszym jest obecnie oznaczenie \(|A|\), zaś oznaczenie \(\overline{\overline{A}}\) można spotkać już raczej w starszych podręcznikach. Pozostałe natomiast są raczej niszowe.

Znamy póki co jedynie dwie liczby kardynalne nieskończone. Pojawia się naturalne pytanie czy istnieją inne nieskończoności, większe od \(\mathfrak c\)? Okazuje się, że tak i do tego dojdziemy.

Innym pytaniem jest to czy istnieją liczby kardynalne pomiędzy \(\aleph_0\) a \(\mathfrak c\)? Wbrew pozorom jest to kwestia wielkiej wagi w matematyce i o niezwykłej historii. Zagadnienie to jest znane w matematyce jako tzw. hipoteza continuum. Zostało ono sformułowane w XIX wieku przez Georga Cantora, który razem z wieloma innymi matematykami sądził, że nie ma żadnej innej nieskończoności pomiędzy \(\aleph_0\) a \(\mathfrak c\). Dlatego mówimy o hipotezie. Było to o tyle ważne zagadnienie, że w roku 1900 David Hilbert umieścił ją na pierwszym miejscu swojej listy najważniejszych nierozwiązanych wg niego problemów matematyki tamtych czasów. Rozwiązanie jest jednak zaskakujące, jeśli nie powiedzieć szokujące, gdy się o tym słyszy po raz pierwszy. Nie wdając się w szczegóły (bo to już historia na inną opowieść), okazało się, że hipotezy continuum nie da się ani obalić ani udowodnić jej prawdziwości. Możemy założyć, że jest ona prawdziwa albo założyć, że nie. I to nawet możemy przyjąć każde (sensowne) jej zaprzeczenie! W żadnym przypadku nie popadniemy w sprzeczność!! Innym słowy, możemy mieć różne matematyki! Z prawdziwą hipotezą continuum albo nie!!! Teraz czas na nieco więcej przykładów zbiorów przeliczalnych, mocy \(\mathfrak c\) oraz o mocach jeszcze większych.

Zacznijmy od zbiorów przeliczalnych. Są to zbiory skończone lub mocy \(\aleph_0\). Można powiedzieć, że są takie zbiory, których elementy możemy ustawić w (skończony lub nie) ciąg. Oznacza to, że niepusty zbiór \(A\) jest przeliczalny dokładnie wtedy, gdy istnieje suriekcja \(\mathbb N\to A\). Korzystając z poprzednich przykładów nieco uporządkujemy naszą wiedzę podając kolejne przykłady.

Przypomnijmy sobie jak pokazaliśmy, że zbiór ułamków jest przeliczalny. Najpierw pokazaliśmy, że zbiór ułamków jest dodatni, a następnie po każdym ułamku wcisnęliśmy taki sam tylko, że ze zmienionym znakiem. Ogólnie prawdziwe jest następujące:

Twierdzenie

Suma dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.

Warto zwrócić uwagę, że z tego twierdzenia wynika np., że jeżeli od zbioru nieprzeliczalnego \(A\) odejmiemy zbiór przeliczalny \(B\), to różnica \(A\setminus B\) jest nieprzeliczalna. Możemy nawet powiedzieć więcej: \(|A\setminus B|=|A|\). W szczególności nieprzeliczalny jest zbiór liczb niewymiernych.

Korzystając z tego twierdzenia, bez problemu pokażemy, że i suma dowolnej skończonej liczby zbiorów przeliczalnych jest zbiorem przeliczalnym. Z kolei sposób w jaki w ogóle ustawiliśmy ułamki w ciąg, można zastosować aby udowodnić poniższe:

Twierdzenie

Iloczyn kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.

Z tego twierdzenia wynika w szczególności, że suma przeliczalnie wielu zbiorów przeliczalnych jest również zbiorem przeliczalnym. W końcu np. zbiór \(\mathbb N\times\mathbb N\) to nic innego jak suma \(\aleph_0\) zbiorów mocy \(\aleph_0\), tj. \[\mathbb N\times\mathbb N=\{1\}\times\mathbb N\cup\{2\}\times\mathbb N\cup\{3\}\times\mathbb N\cup\ldots\] Naturalnie, z tego twierdzenia wynika m.in., że również i iloczyn \(A_1\times A_2\times\ldots\times A_n\) jest przeliczalny, o ile przeliczalne są zbiory \(A_1,A_2,\ldots, A_n\). A z tego bezpośrednio dostajemy następujące:

Twierdzenie

Zbiór wszystkich skończonych ciągów o wyrazach należących do zbioru przeliczalnego \(A\) jest zbiorem przeliczalnym.

Wynika to z tego, że zbiór ten jest sumą \[A_1\cup A_2\cup\ldots\cup A_n\cup\ldots,\] gdzie \(A_n\) jest zbiorem ciągów długości \(n\), a zbiór \(A_n\) to nic innego jak \[\underbrace{A\times A\times\ldots\times A}_{n\textrm{ razy }}\] Z tego w szczególności wynika, że zbiór wielomianów o współczynnikach wymiernych jest zbiorem mocy \(\aleph_0\) bo każdy taki wielomian stopnia \(n\) możemy utożsamiać ze skończonym ciągiem liczb wymiernych długości \(n\) (tj. ciągiem jego współczynników przy kolejnych potęgach). A ponieważ każdy wielomian ma skończenie wiele pierwiastków, to dostajemy automatycznie poniższe

Twierdzenie

Zbiór liczb algebraicznych jest przeliczalny.

Liczby algebraiczne, to jeżeli ktoś nie wie, to dokładnie te liczby, które są właśnie pierwiastkami wielomianów o współczynnikach wymiernych. Więcej o tych liczbach można poczytać w tym wpisie. Liczbami algebraicznymi są niemal wszystkie konkretne liczby, które poznajemy w szkole takie jak liczby wymierne czy \(\sqrt{2}\). Liczbą algebraiczną natomiast nie jest np. słynna liczba \(\pi\). Liczby nie będące algebraicznymi nazywamy przestępnymi.

Ponieważ każda liczba rzeczywista jest albo algebraiczna albo przestępna, a liczb rzeczywistych jest \(\mathfrak c\), to z ostatniego twierdzenia dostajemy zaskakujące

Twierdzenie

Zbiór liczb przestępnych jest nieprzeliczalny.

Czyli liczb przestępnych jest więcej niż algebraicznych! Zaskakujące jest to głównie dlatego, że niemal wszystkie liczby jakie poznajemy w trakcie nauki szkolnej to liczby algebraiczne. Mimo iż niemal wszystkie liczby rzeczywiste są przestępne, to wbrew pozorom podanie przykładów liczb przestępnych było dosyć trudne. Zresztą, nadal nie jest łatwe. Mimo iż znamy już wiele przykładów takich liczb, to wciąż wiemy o nich relatywnie niewiele. Więcej o liczbach przestępnych można znaleźć w tym wpisie.

Warto wiedzieć, że pierwsza praca Cantora dotycząca mocy zbiorów była właśnie o liczbach przestępnych. Pokazał on w niej, że liczb tych jest więcej niż algebraicznych, że nie da się liczb przestępnych ustawić w ciąg. Ową pracę można znaleźć pod tym linkiem.

Przejdźmy teraz do zbiorów mocy \(\mathfrak c\). Póki co pokazaliśmy, że odcinek \([0,1]\) ma moc \(\mathfrak c\).

Twierdzenie

Wszystkie odcinki otwarte \((a,b)\subset\mathbb R\) mają moc \(\mathfrak c\).

Istotnie, funkcja \[f:(a,b)\to(c,d),\ \textrm{ gdzie } f(x)=\frac{d-c}{b-a}(x-a)+c\] jest jak nietrudno się przekonać bijekcją. A ponieważ odcinek \([0,1]\) jest, jak wiemy, mocy \(\mathfrak c\), to i mocy \(\mathfrak c\) jest przedział \((0,1)=[0,1]\setminus\{0,1\}\). Czyli każdy przedział jest mocy \(\mathfrak c\). A ponieważ funkcja \[f:\left(-\frac{\pi}{2},\frac{\pi}{2}\right)\to\mathbb R,\ \textrm{ gdzie } f(x)=\textrm{tg }x\] również jest bijekcją, to już oficjalnie możemy sformułować poniższe:

Twierdzenie

Zbiór liczb rzeczywistych jest mocy \(\mathfrak c\).

W szczególności mocy \(\mathfrak c\) są zbiory liczb niewymiernych oraz przestępnych. Zanim przejdziemy do zbiorów wyższych mocy jeszcze jeden ważny przykład.

Twierdzenie

Zbiór wszystkich funkcji \(\mathbb N\to \{0,1\}\) jest mocy \(\mathfrak c\).

Każda taka funkcja to nic innego jak nieskończony ciąg zero-jedynkowy. A każdy taki ciąg możemy utożsamiać (w sposób jednoznaczny!) z pewnym podzbiorem zbioru \(\mathbb N\). Tzn. dany ciąg utożsamiamy ze zbiorem składającym się z tych \(n\in\mathbb N\), dla których \(f(n)=1\). Czyli zbiór wszystkich podzbiorów \(\mathbb N\) ma moc \(\mathfrak c=|\mathbb R|\).

Zbiór funkcji \(A\to B\) oznacza się zwyczajowo \(B^A\). Gdy \(B=\{0,1\}\) to zamiast \(\{0,1\}^A\) stosuje się oznaczenie \(2^A\). Jeżeli \(A,B\) są skończone, to moc zbioru \(B^A\) jest równa \(|B|^{|A|}\). Gdy \(|B|=2\) otrzymujemy \(2^{|A|}\). Jest to liczba podzbiorów zbioru skończonego. To wszystko sugeruje definicję potęgowania liczb kardynalnych. Mianowicie jeżeli \(\mathfrak a=|A|\) oraz \(\mathfrak b=|B|\), to przyjmujemy \[\mathfrak a^{\mathfrak b}=|A^B|\] Dzięki temu otrzymujemy piękną zależność \[\mathfrak c=2^{\aleph_0}\] Swoją drogą mocy \(\mathfrak c\) są również zbiory \(A^{\mathbb N}\), gdzie \(A\) jest dowolnym zbiorem przeliczalnym!! Mamy więc \[\mathfrak c=2^{\aleph_0}=3^{\aleph_0}=\ldots=\aleph_0^{\aleph_0}\]

Jak widzimy arytmetyka liczb kardynalnych nieco się różni od tej w liczbach naturalnych. Choć namiastkę tego już mogliśmy dostrzec wcześniej. Skoro suma (rozłącznych) podzbiorów mocy \(\aleph_0\) jest nadal tej mocy, to możemy zapisać \[\aleph_0+\aleph_0=\aleph_0\] Podobnie mamy równości \[\aleph_0+\mathfrak c=\mathfrak c+\mathfrak c=\mathfrak c\]

Ale przejdźmy do zbiorów wyższych mocy. Kluczowe znaczenie będzie miało następujące twierdzenie:

Twierdzenie Cantora

Dla dowolnego zbioru \(A\) zachodzi \[|A|\lt \left|2^A\right|.\]

Wynika z tego m.in., że \(\mathfrak c\lt 2^{\mathfrak c}\lt 2^{2^{\mathfrak c}}\lt\ldots\) Czyli otrzymujemy nieskończony ciąg liczb kardynalnych!! Jest nieskończenie wiele nieskończoności! Choć jak zobaczymy, takie sformułowanie to eufemizm.

Twierdzenie Cantora jest na tyle ważne, że je udowodnimy. Dowód jest prosty i sam w sobie warty poznania. W piękny i elegancki sposób pokazuje (po raz kolejny) ideę łączenia w pary w akcji. Lub raczej niemożność takiego połączenia w tym przypadku. Przedstawimy go na końcu wpisu. Zanim to jednak uczynimy, pokażemy, że wynika z niego następujące:

Twierdzenie

Nie istnieje zbiór wszystkich zbiorów.

Gdyby taki zbiór \(X\) istniał, to miałby pewną moc \(\mathfrak m\). Do tego, dla każdego \(A\subseteq X\) musi być, że \(A\in X\). Więc w szczególności zbiór \(X\) musiałby mieć moc co najmniej \(\left|2^{X}\right|\) ale z twierdzenia Cantora mamy, że \[\mathfrak m\lt \left|2^{X}\right|.\] Otrzymana sprzeczność kończy dowód.

Wszystkich zbiorów jest za dużo aby dało się z nich utworzyć zbiór!!

Okazuje się, że również liczb kardynalnych jest za dużo aby można było utworzyć z nich zbiór. Może to się wydawać zaskakujące, bo udało nam się, korzystając z twierdzenia Cantora, stworzyć w zasadzie ciąg nieskończonych liczb kardynalnych. Ale tak naprawdę to dopiero wierzchołek góry lodowej! Warto wspomnieć, że oznaczenie \(\aleph_0\) jest nieprzypadkowe bo istnieje wśród liczb kardynalnych tzw. skala alefów. Liczba \(\aleph_1\) to druga po \(\aleph_0\) nieskończona liczba kardynalna. Zdanie, że \(\aleph_1=\mathfrak c\) to nic innego jak hipoteza continuum w nieco innej formie.

Na koniec trzeba jeszcze zaznaczyć, że w tym wpisie stosowaliśmy pewne uproszczenia, a o pewnych kwestiach nie wspominaliśmy. Takie kwestie jak np. to czy zawsze można, tam gdzie to robiliśmy, ustawiać elementy zbiorów nieskończonych w ciąg czy wręcz bardziej prozaiczne z pozoru typu czy zawsze dwie liczby kardynalne możemy porównywać, nie są wbrew pozorom takie oczywiste jak by się mogło wydawać. Dla przykładu warto wspomnieć to, że fakt iż z tego, że jeśli \[\mathfrak a\leqslant\mathfrak b\textrm{ oraz } \mathfrak b\leqslant\mathfrak a\] wynika, że \[\mathfrak a=\mathfrak b\] jest w matematyce twierdzeniem. Jest to tzw. twierdzenie Cantora-Bernsteina. Niby wynik ten wydaje się oczywisty, a prawda jest taka, że dowód wcale króciutki nie jest.

Uczciwość nakazuje by jeszcze wspomnieć, że tytuł tego wpisu jest cytatem, z (chyba) wiersza, który można było kiedyś znaleźć na humorystycznej stronie o matematyce, której autorem był niejaki Tomi Meteor. Niestety strona już chyba nie istnieje. Teraz przejdźmy do dowodu twierdzenia Cantora.

Dowód twierdzenia Cantora:

Jeżeli zbiór \(A\) jest skończony, to wiemy, że twierdzenie jest prawdziwe bo podzbiorów zbioru skończonego mocy \(n\in\mathbb N\cup\{0\}\) jest \(2^n\). Załóżmy teraz, że \(A\) jest nieskończony. Nietrudno pokazać, że zbiór \(2^A\) ma co najmniej tyle samo elementów co \(A\). Przykładową iniekcją może być taka funkcja \[f:A\to 2^A,\ \textrm{ gdzie } f(x)=\{x\}.\] Stąd otrzymujemy, że \[|A|\leqslant \left|2^A\right|.\] Teraz pokażemy, że równość nie zachodzi. W tym celu załóżmy, że istnieje bijekcja \(g:A\to 2^A\). Dla każdego \(x\in A\) wartość \(g(x)\) jest podzbiorem zbioru \(A\). Wobec tego, dla każdego \(x\in A\) albo \(x\in g(x)\) albo \(x\notin g(x)\) (pamiętajmy, że \(g(x)\) jest z definicji podzbiorem \(A\)). Niech \[Z=\{x\in A:x\notin g(x)\},\] tzn. \(x\in Z\) dokładnie wtedy, gdy \(x\notin g(x)\). Pamiętajmy, że z założenia funkcja \(g\) jest bijekcją. Stąd istnieje taki \(a\in A\), że \(g(a)=Z\). Są teraz dwie możliwości albo \(a\in Z\) albo \(a\notin Z\). Jeżeli \(a\in Z\), to z definicji \[a\notin g(a)=Z.\] Czyli nie może być, że \(a\in Z\). Z kolei, w przypadku gdy \(a\notin Z\), to \[a\in g(a)=Z.\] Zatem i również nie może być, że \(a\notin Z\). Otrzymana sprzeczność kończy dowód.

---

Literatura:

K. Kuratowski, A. Mostowski, Teoria Mnogości, PWN 1952
B. Miś, Tajemnicza liczba \(e\) i inne sekrety matematyki, PWN 1989.
H. Rasiowa, Wstęp do matematyki współczesnej, PWN 1973