Równoliczność zbiorów, zbiory przeliczalne

Liczby naturalne $0,1,2,3\dots$ służą do liczenia elementów zbiorów skończonych. Zbiory skończone to właśnie zbiory, które mają $n$ elementów dla pewnej liczby naturalnej $n$. Pozostaje problem, jak określić liczbę elementów zbioru nieskończonego. Możemy to zrobić posługując się w pewnym sensie zasadą abstrakcji. Mianowicie, zamiast definiować, co to jest liczba elementów danego zbioru, najpierw definiujemy, co to znaczy, że dwa zbiory $A$ i $B$ mają tę samą liczbę elementów (tzn. są równoliczne).

Definicja 11..1   Mówimy, że zbiory $A$ i $B$ są równoliczne (symbolicznie: $A\sim B$), gdy istnieje bijekcja $f:A\to B$.

Uwaga 11..2   Dla dowolnych zbiorów $A,B,C$ mamy:
(1) (zwrotność) $A\sim A$
(2) (symetryczność) $A\sim B\Rightarrow B\sim A$
(3) (przechodniość) $A\sim B\land B\sim C\Rightarrow A\sim C$

Dowód. Funkcja identycznościowa $id_A$ świadczy o (1). Dla dowodu (2) zauważmy, że jeśli $f:A\to B$ jest bijekcją, to funkcja odwrotna $f^{-1}:B\to A$ istnieje i też jest bijekcją. (3) wynika z tego, że złożenie bijekcji jest bijekcją. $\Box$

Widzimy, że równoliczność zbiorów ma własności relacji równoważności. Czy jednak $\sim$ jest relacją równoważności ? W ścisłym sensie nie, gdyż jej dziedzina i obraz nie są zbiorami, nie istnieje bowiem zbiór wszystkich zbiorów. (Gdyby bowiem taki zbiór $X$ istniał, to funkcja zdaniowa $x\not\in x, x\in X$ zdefiniowałaby nam zbiór z antynomii Russella.)

Jeśli jednak ograniczymy zakresy zmiennych $X$ i $Y$ w funkcji zdaniowej $X\sim Y$ do zbioru podzbiorów pewnej ustalonej przestrzeni $U$, to wówczas $\sim$ staje się relacją równoważności na zbiorze ${\cal P}(U)$.

Intuicyjnie, liczba elementów zbioru $A$ (zwana inaczej mocą zbioru $A$) to wspólna własność wszystkich zbiorów równolicznych ze zbiorem $A$. Gdy ograniczamy $\sim$ do zbioru ${\cal P}(U)$, dla $A\in {\cal P}(U)$ moglibyśmy przyjąć (stosując zasadę abstrakcji), że moc $A$ to po prostu klasa abstrakcji relacji $\sim$. W ten sposób wykluczylibyśmy jednak z rozważań zbiory równoliczne z $A$, które nie zawierają się w przestrzeni $U$.

W teorii mnogości rozwiązuje się ten problem nieco sztucznie: tworzy się mianowicie dla wszystkich zbiorów $A$ pewne zbiory oznaczane przez $\vert A\vert$. Obiekty te mają następującą własność:

Dla dowolnych zbiorów $A,B$ mamy $A\sim B\Leftrightarrow \vert A\vert=\vert B\vert.$

W ten sposób grają one rolę ``nazw'' klas zbiorów równolicznych. $\vert A\vert$ nazywamy mocą zbioru $A$ lub liczbą kardynalną zbioru $A$.

Liczby naturalne to po prostu liczby kardynalne zbiorów skończonych. A więc na przykład, gdy zbiór $A$ jest trzyelementowy, to $\vert A\vert=3$. W przypadku liczb naturalnych można łatwo wyjaśnić, w jaki sposób są one konstruowane. Mianowicie w teorii mnogości przyjmuje się, że

$$0=\emptyset \mbox{ (jest to więc pewien zbiór $0$-elementowy)},$$

$$1=\{0\},\mbox{ to znaczy } 1=\{\emptyset\} \mbox{ (jest to więc pewien zbiór $1$-elementowy) },$$

$$2=\{0,1\}=\left\{\emptyset,\{\emptyset\}\right\},\ 3=\{0,1,2,\},\ 4=\{0,1,2,3\},\ 5=\{0,1,2,3,4\}$$

i tak dalej. Widzimy, że liczba naturalna $n$ jest pewnym zbiorem $n$-elementowym, a mianowicie $n=\{0,1,\dots,n-1\}$. Jest więc ona jakby wzorcowym zbiorem $n$-elementowym. Przyrównując zbiór skończony do jednego z takich wzorców stwierdzamy, ile ma elementów. Zauważmy, że formalnie liczba $n+1$ to zbiór $n\cup\{n\}$.

Niektóre inne liczby kardynalne mają specjalne nazwy i oznaczenia. Przykładowo liczbę kardynalną $\vert{\mathbb{N}}\vert$ oznacza się symbolem $\aleph_0$ (czytaj: alef zero), zaś moc zbioru liczb rzeczywistych nazywa się continuum i oznacza mała gotycką literą $\bf c$. Podamy teraz przykłady zbiorów równolicznych.

Przykład 1. Niech $A= {\mathbb{N}},\ B=\{2n:n\in{\mathbb{N}}\}$. $B$ jest zbiorem liczb parzystych. Są to zbiory równoliczne, świadczy o tym bijekcja $f:A\to B$ dana wzorem $f(x)=2x$.

Przykład 2. Dowolne dwa przedziały $(a,b),(c,d)\subseteq{\bf R}$ są równoliczne. świadczy o tym funkcja liniowa dana wzorem

$$f(x)={d-c\over b-a}(x-a)+c,$$

która przekształca przedział $(c,d)$ wzajemnie jednoznacznie na przedział $(a,b)$.

Przykład 3. Dowolny przedział $(a,b)\subseteq\mathbb{R}$ jest równoliczny z $\mathbb{R}$. Istotnie, funkcja $\tan:(-{1\over 2}\pi,{1\over 2}\pi)\to \mathbb{R}$ jest bijekcją, która świadczy o tym, że $(-{1\over 2}\pi,{1\over 2}\pi)\sim \mathbb{R}$. Z drugiej strony na mocy przykładu 2. mamy $(a,b)\sim(-{1\over 2}\pi,{1\over 2}\pi)$, więc z przechodniości $\sim$ również $(a,b)\sim\mathbb{R}$.

Przykład 4. $(a,b)\sim[a,b]$, czyli przedziały otwarty i domknięty są równoliczne. By to uzasadnić, znajdujemy bijekcję $f:[a,b]\to(a,b)$. Najpierw określamy pewien ciąg różnowartościowy $(a_n)$ liczb z przedziału $(a,b)$, na przykład niech

$$a_0=a+{b-a\over 2},\ a_1=a+{b-a\over 4},\ a_2=a+{b-a\over 8},\dots$$

Funkcję $f:[a,b]\to(a,b)$ określamy wzorem

$$f(b)=a_0,\ f(a)=a_1,\ f(a_n)=a_{n+2}\mbox{ dla }n\geq 0,$$

zaś dla $x\in[a,b]$ różnych od $a,b,a_0,a_1,a_2,\dots$ kładziemy $f(x)=x$.

Przykład 5. Przedział otwarty $(0,1)$ i ``kwadrat'' $T=((0,1]\times(0,1])\setminus\{\langle 1,1\rangle\}$ są równoliczne. By to uzasadnić, określamy bijekcję $f:(0,1)\to T$.

Niech $x\in(0,1)$. W rozwinięciu dziesiętnym liczba $x$ ma postać

$$0,c_1c_2c_3c_4\dots,$$

gdzie $0\leq c_i\leq 9$. W przypadku, gdy w zapisie tym od pewnego miejsca występują same zera, zastępujemy go zapisem, w którym od pewnego miejsca są same dziewiątki. Na przykład

$$0,2000\dots=0,1999\dots.$$

W ten sposob każdej liczbie $x$ przypisane jest jedyne rozwinięcie dziesiętne nieskończone, w którym dowolnie daleko pojawiają się cyfry niezerowe. Teraz dzielimy ciąg $c_1c_2c_3c_4\dots$ na kolejne skończone bloki cyfr $d_1,d_2,d_3,\dots$ w następujący sposób. Blok cyfr $d_i$ zaczyna się zaraz po bloku $d_{i-1}$ (blok $d_0$ zaczyna się od $c_0$) i kończy na $i$-tej kolejnej niezerowej cyfrze w ciągu $c_1c_2c_3\dots$. Wówczas tworzymy dwie nowe liczby rzeczywiste $\xi$ i $\eta$ określając ich rozwinięcia dziesiętne następująco:

$$\xi=0,d_1d_3d_5d_7\dots,\ \eta=0,d_2d_4d_6d_8\dots$$

Przykładowo, dla

$$x=0,317042000985016$$

mamy

$$\xi=0,372801...\mbox{, zaś }\eta=0,10400956\dots.$$

Definujemy $f(x)=\langle\xi,\eta\rangle$. Widzimy, że $f:(0,1)\to T$. Z dowolnej pary $\langle\xi,\eta\rangle\in T$ potrafimy odczytać $x\in(0,1)$ takie, że $f(x)=\langle\xi,\eta\rangle$. Na przykład, gdy

$$\xi=0,002980760523,\ \ \ \eta=0,999018002104...,$$

to widzimy, że istnieje dokładnie jeden ciąg bloków $d_1,d_2,d_3,d_4,\dots$ taki, że każdy blok składa się z pewnej liczby zer na początku (być może liczby zerowej) a następnie jednej cyfry niezerowej, i taki, że

$$\xi=0,d_1d_3d_5d_7\dots,\ \eta=0,d_2d_4d_6d_8\dots.$$

Mianowicie, z zapisu dziesiętnego liczby $\xi$ odczytujemy, że $d_1=002, d_3=9, d_5=8$ i tak dalej, podczas gdy z zapisu dziesiętnego liczby $\eta$ odczytujemy, że $d_2=9, d_4=9, d_6=9, d_8=01$ i tak dalej. Zatem istnieje jedyne $x$ takie, że $f(x)=\langle\xi,\eta\rangle$, a mianowicie

$$x=0,00299890701\dots.$$

Dlatego funkcja $f$ jest bijekcją.

Twierdzenie 11..3 (Cantor-Bernstein)   Jeśli $A\subseteq B\subseteq C$ i $A\sim C$, to $B\sim C$.

Dowód. Niech $f:C\to A$ będzie bijekcją. Skoro $A\subseteq C$, to $f[A]\subseteq f[C]$ i ogólniej $f^n[A]\subseteq f^n[C]$. Z drugiej strony $A=f[C]$, więc $f^n[A]=f^{n+1}[C]$. Dlatego mamy $f^{n+1}[C]\subseteq f^n[C]$ dla $n=0,1,2,3,\dots.$ Innymi słowy dostajemy malejący ciąg zbiorów:

$$(*)\ \ C\supseteq A=f[C]\supseteq f^2[C]\supseteq f^3[C]\supseteq\dots$$

Niech $Z=C\setminus B$. Widzimy, że $Z\subseteq C\setminus A$. Dlatego $f[Z]\subseteq f[C\setminus A]$ i ogólniej $f^n[Z]\subseteq f^n[C\setminus A]$. $f^n$ jest różnowartościowa, dlatego

$$f^n[C\setminus A]=f^n[C]\setminus f^n[A]=f^n[C]\setminus f^{n+1}[C],$$

zatem dla $n=0,1,2,\dots$ mamy

$$f^n[Z]\subseteq f^n[C]\setminus f^{n+1}[C].$$

Z $(*)$ dostajemy więc, że zbiory $Z,f[Z],f^2[Z],\dots$ są parami rozłączne. Ponadto $f\vert _{f^n[Z]}:f^n[Z]\to f^{n+1}[Z]$ jest bijekcją. Niech

$$X=Z\cup f[Z]\cup f^2[Z]\cup f^3[Z]\cup\dots$$

Zatem $f$ ograniczone do $X$ jest bijekcją ze zbioru $X$ na zbior $Y=f[Z]\cup f^2[Z]\cup f^3[Z]\dots$ zawarty w $B$. Ponado $B\setminus X=B\setminus Y$. Możemy teraz określić funkcję $g:C\to B$ wzorem

$$g(x)=\left\{\begin{array}{cl}f(x)&\mbox{, gdy }x\in X \\ x&\mbox{, w przeciwnym razie}\end{array}\right.$$

Widzimy, że funkcja $g$ jest różnowartościowa i ``na''. Dlatego świadczy ona o równoliczności zbiorów $C$ i $B$. $\Box$

Przykład 6. Niech $C=[0,1]\times [0,1]$ (jest to więc ``pełny kwadrat''). Wtedy zbiory $C$ i $T$ (z przykładu 5.) są równoliczne. By to uzasadnić, rozważmy jednokładność $J$ płaszczyzny ${\mathbb{R}}^2$ o środku w punkcie $\langle {1\over 2},{1\over 2}\rangle$ i skali ${1\over 2}$. Jest to bijekcja płaszczyzny. Mamy

$$J[C]\subseteq T\subseteq C.$$

Skoro $J[C]\sim C$, to na mocy twierdzenia Cantora-Bernsteina dostajemy $C\sim T$.

Uwaga 11..4   Jeśli $X\sim X'$ i $Y\sim Y'$, to $X\times Y\sim X'\times Y'$.

Dowód. Dowód pozostawiamy jako ćwiczenie.$\Box$

Wniosek 11..5   ${\mathbb{R}}\sim {\mathbb{R}}\times{\mathbb{R}}$.

Dowód. Niech $I$ oznacza przedział domknięty $[0,1]$. Korzystając z powyższych przykładów i uwagi mamy więc

$${\mathbb{R}}\sim I\sim (0,1)\sim T\sim C=I\times I\sim{\mathbb{R}}\times{\bf R}.$$

$\Box$

Zbiory przeliczalne.

Definicja 11..6   Zbiór $X$ nazywamy przeliczalnym, gdy jest skończony lub równoliczny z $\mathbb{N}$.

Zatem zbiory przeliczalne to zbiór pusty, niepuste zbiory skończone i te zbiory nieskończone, które są równoliczne z $\mathbb{N}$.

Uwaga 11..7   Załóżmy, że $X\neq\emptyset$. Wtedy następujące warunki są równoważne.
(1) $X$ jest przeliczalny.
(2) Istnieje surjekcja $f:{\mathbb{N}}\to X$.
(3) Elementy zbioru $X$ można ustawić w ciąg (ewentualnie z powtórzeniami): $X=\{a_0,a_1,a_2,a_3,\dots,\}$.

Dowód. By udowodnić równoważność warunków (1)-(3), wystarczy pokazać implikacje $(1)\Rightarrow(2)$, $(2)\Rightarrow(3)$ i $(3)\Rightarrow(1)$.

$(1)\Rightarrow(2)$. Jeśli $X$ ma $k$ elementów ($k>0$), to $X=\{a_0,\dots,a_{k-1}\}$ dla pewnych $a_0,\dots,a_{k-1}$. Definiujemy wtedy surjekcję $f:{\mathbb{N}}\to X$ wzorem:

$$f(n)=\left\{\begin{array}{cc}a_n&\mbox{, gdy }n<k\\ a_0&\mbox{, gdy }n\geq k\end{array}\right.$$

Gdy $X$ jest równoliczny z $\mathbb{N}$, to istnieje nawet bijekcja $f:{\mathbb{N}}\to X$.

$(2)\Rightarrow(3)$. Załóżmy, że $f:{\mathbb{N}}\to X$ jest ``na''. Wtedy
$X=\{f(0),f(1),f(2),\dots\}$.

$(3)\Rightarrow(1)$. Załóżmy, że $X=\{a_0,a_1,a_2,a_3,\dots\}.$ Gdy $X$ jest skończony (wtedy ciąg $(a_n)$ musi mieć powtórzenia), to jest oczywiście przeliczalny. Załóżmy więc, że $X$ jest nieskończony. Wtedy w ciągu $(a_n)$ jest nieskończenie wiele wyrazów. Skreślając w ciągu $a_0,a_1,a_2,a_3,a_4,a_5,a_6,\dots$ te wyrazy, które wystąpiły już wcześniej, dostajemy nowy ciąg, tym razem już bez powtórzeń. Ten nowy ciąg jest więc bijekcją między $\mathbb{N}$ a $X$. $\Box$

Uwaga 11.7 tłumaczy nazwę zbioru przeliczalnego. Mianowicie, zbiór przeliczalny to taki zbiór, którego elementy możemy przeliczyć używając liczb naturalnych (być może wszystkich, gdy nasz zbiór jest nieskończony).

Przykład 1. Zbiór liczb całkowitych $\mathbb{Z}$ jest przeliczalny. Istotnie, ${\bf Z}=\{0,1,-1,2,-2,3,-3,4,-4,\dots\}$.

Przykład 2. Zbiór liczb wymiernych $\mathbb{Q}$ jest przeliczalny. Może to być zaskakujące, że jest tyle samo liczb wymiernych, co liczb naturalnych (tzn. że ${\mathbb{Q}}\sim{\mathbb{N}}$). By to uzasadnić, najpierw układamy dodatnie liczby wymierne w nieskończonej tablicy :

$$\begin{array}{cccccc}\medskip {1\over 1}&{1\over 2}&{1\over 3... ...\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\mbox{}\end{array}$$

Na kolejnych przekątnych leżą ułamki o stałej sumie licznika i mianownika, każda taka przekątna składa się ze skończenie wiele takich ułamków. Każdy ułamek leży na jakiejś przekątnej. Dlatego układając kolejno ułamki najpierw z pierwszej przekątnej, potem z drugiej, potem z trzeciej i tak dalej, ustawimy liczby wymierne dodatnie w ciąg (z powtórzeniami):

$${\mathbb{Q}}^+=\left\{{1\over 1},{2\over 1}.{1\over 2},{3\over 1},{2\over 2}, {1\over 3},{4\over 1},{3\over 2},\dots\right\}.$$

Następnie, podobnie jak w przykładzie 1., możemy ustawić w ciąg wszystkie liczby wymierne.

Uwaga 11..8 (1)   Jeśli $A$ i $B$ są przeliczalne, to $A\cup B$ też jest przeliczalny.
(2) Jeśli $(A_n)$ jest ciągiem zbiorów przeliczalnych, to zbiór $\bigcup_nA_n$ też jest przeliczalny.
(3) Jeśli $A$ i $B$ są przeliczalne, to $A\times B$ jest przeliczalny.

Dowód. (1) Możemy założyć, że $A$ i $B$ są niepuste. Załóżmy, że $A=\{a_0,a_1,a_2,\dots\}$ i $B=\{b_0,b_1,b_2,\dots\}$. Wtedy elementy zbiou $A\cup B$ ustawiamy w ciąg następująco:

$$a_0,b_0,a_1,b_1,a_2,b_2,a_3,b_3,\dots$$

(2) Możemy wykreślić z ciągu zbiorów $A_0,A_1,A_2,A_3,\dots$ zbiory puste (nie wpływają one na sumę tych zbiorów). Jeśli pozostanie tylko skończenie wiele zbiorów niewykreślonych, to ich suma będzie przeliczalna na mocy kilkukrotnego zastosowania (1). Dlatego możemy założyć, że pozostało nieskończenie wiele zbiorów niewykreślonych.

Zmieniając odpowiednio ich numerację możemy założyc, że wszystkie zbiory $A_n$ są niepuste. Możemy zatem elementy każdego zbioru $A_n$ ustawić w ciąg:

$$\begin{array}{ccccccc}\medskip A_0&=&\{a^0_0,&a^0_1,&a^0_2,&a... ...\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\end{array}$$

Następnie możemy ustawić w ciąg elementy zbioru $\bigcup_nA_n$ podobnie, jak zrobiliśmy to w przypadku liczb wymiernych dodatnich.

(3) Znów możemy założyć, że oba zbiory $A,B$ są niepuste oraz $A=\{a_0,a_1,a_2,a_3,\dots\}$ i $B=\{b_0,b_1,b_2,b_3,\dots\}$. Dla $n\in\mathbb{N}$ niech $B_n=\{a_n\}\times B$. Zatem zbiór $B_n$ składa się z tych par $\langle x,y\rangle\in A\times B$, dla których $x=a_n$. Widzimy, że $B_n=\{\langle a_n,b_0\rangle,\langle a_n,b_1\rangle,\langle a_n,b_2\rangle,\dots\}$, jest więc przeliczalny. Ponadto $A\times B=\bigcup_nB_n$, jest więc przeliczalny na mocy (2).$\Box$

Wniosek 11..9   Zbiór wszystkich skończonych ciągów o wyrazach ze zbioru przeliczalnego $X$ jest przeliczalny.

Dowód. Dla $n\in\mathbb{N}$ niech $X_n$ oznacza zbiór ciągów $n$-wyrazowych o wyrazach z $X$. Wtedy $X_0=\{\emptyset\}$ (jest więc jednoelementowy, składa się z ciągu pustego) oraz dla $n>0$ $X_n=\underbrace{X\times\cdots\times X}_n$, więc zawsze $X_n$ jest przeliczalny. Zatem również zbiór wszystkich ciągów skończonych o wyrazach z $X$, czyli zbiór $\bigcup_nX_n$, jest przeliczalny. $\Box.$

W szczególności jest przeliczalnie wiele wielomianów o współczynnikach wymiernych. Każdy z nich ma skończenie wiele pierwiastków. Pierwiastki takich wielomianów nazywamy liczbami algebraicznymi. Widzimy więc, że jest przeliczalnie wiele liczb algebraicznych. Istnieją również zbiory nieprzeliczalne.

Twierdzenie 11..10 (Cantor)   Zbiór liczb rzeczywistych jest nieprzeliczalny.

Dowód. ${\mathbb{R}}\sim(0,1)$, wystarczy więc pokazać, że przedział otwarty $(0,1)$ jest nieprzeliczalny.

Przypuśćmy nie wprost, że $(0,1)$ jest przeliczalny, tzn. jego elementy można ustawić w ciąg: $(0,1)=\{a_0,a_1,a_2,a_3,\dots\}$. Zatem $(a_n)$ to ciąg wszystkich liczb rzeczywistych z przedziału $(0,1)$. Sprzeczność osiągniemy wskazując liczbę rzeczywistą z przedziału $(0,1)$, która nie jest wyrazem tego ciągu.

Każdą z liczb $a_n$ możemy zapisać w postaci nieskończonego rozwiniecia dziesiętnego.

$$\begin{array}{cccccccccc} \medskip a_0&=&0,a^0_0a^0_1a^0_2a^0... ...^4_2a^4_3a^4_4\dots\\ \vdots&\mbox{}&\mbox{}\mbox{}\end{array}$$

Z łatwością znajdujemy teraz cyfry $b_0,b_1,b_2,b_3\dots$ takie, że $b_n\neq 0,9$ i $b_n\neq a^n_n$. Wówczas liczba

$$c=0,b_0b_1b_2b_3\dots$$

jest różna od każdej liczby $a_n$ (bo różni się od niej na $n+1$-wszym miejscu po przecinku: $b_n\neq a^n_n$), co kończy dowód. $\Box$

Skoro $\mathbb{R}$ jest nieprzeliczalny, a liczb algebraicznych jest przeliczalnie wiele, to liczb niealgebraicznych (zwanych inaczej przestępnymi) jest nieprzeliczalnie wiele.