Logika i teoria mnogości/Wykład 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum

Teoria mocy

Zadaniem teorii mocy, do której wstęp znajdą państwo w tym wykładzie, będzie uogólnienie pojęcia ilości elementów zbioru. Dla zbiorów skończonych powołaliśmy do życia liczby naturalne (patrz Wykład 7), przy pomocy których możemy rachować i opisywać ilościowe własności innych zbiorów. Niestety to nam nie wystarcza. Są zbiory, których liczbę elementów nie sposób opisać żadną liczbą naturalną. Zgodziliśmy się wszak, przyjmując aksjomat nieskończoności, na istnienie takich niezwykłych zbiorów . Aksjomat ten wraz z innymi, na przykład, aksjomatem zbioru potęgowego, będzie miał dla nas wiele niespodzianek. Powołamy do życia zbiory nieskończone, a co więcej pokażemy, że istnieją różne rodzaje nieskończoności. Jedne zbiory nieskończone będą bardziej nieskończone od innych. Aby umieć porównywać liczby elementów zbiorów nieskończonych, wprowadzimy podstawowe definicje. Z punktu widzenia tych definicji na całą teorię mocy można patrzeć jak na teorie bijekcji i iniekcji (lub dualnie surjekcji - patrz wykład 11, ćwiczenie 3.1).

Definicja 1.1

Zbiory $A$ i $B$ nazywamy równolicznymi, gdy istnieje bijekcja $f:A\to B$. Równoliczność zbiorów oznaczamy przez $A{\sim }_{m}B$.

${\sim }_m$ ma podobne własności do relacji równoważności.

Twierdzenie 1.2

Równoliczność ma własności:

1. $A{\sim }_{m}A$.
2. jeżeli $A{\sim }_{m}B$, to $B{\sim }_{m}A$.
3. jeżeli $A{\sim }_{m}B$ i $B{\sim }_{m}C$, to $A{\sim }_{m}C$.

Trywialne dowody tych faktów pozostawimy jako ćwiczenia.

Ćwiczenie 1.3

Udowodnij własności 1, 2, 3. z Twierdzenia 1.2.

Rozwiązanie

1. Oczywiste. Identyczność $1_A$ jest tego świadkiem.
2. Funkcja odwrotna do bijekcji jest bijekcją.
3. Złożenie bijekcji jest bijekcją.

Twierdzenie 1.4

Podstawowe własności relacji równoliczności:

1. $A{\sim }_{m}B$ i $C{\sim }_{m}D$ oraz $A\cap C=B\cap D=\mathrm{\varnothing }$, to $A\cup C{\sim }_{m}B\cup D$.
2. $A{\sim }_{m}B$ i $C{\sim }_{m}D$, to $A^C{\sim }_m{B}^D$.
3. $(A^B{)}^C{\sim }_m{A}^{B\times C}$.
4. $(A\times B{)}^C{\sim }_m{A}^C\times B^C$.
5. Gdy $B\cap C=\mathrm{\varnothing }$, to $A^{B\cup C}{\sim }_m{A}^B\times A^C$.
6. $P(A){\sim }_m{2}^A$.

Znowu dowody twierdzeń z 1.4 podamy jako ćwiczenia.

Ćwiczenie 1.5

Dowiedź Twierdzenia 1.4.

Wskazówka

1. Suma mnogościowa bijekcji działających na zbiorach rozłącznych i mających rozłączne przeciwdziedziny jest bijekcją.
2. Niech $f:A\to B$ i $g:C\to D$ będą bijekcjami. Rozważ funkcje $\mathrm{\Phi }:A^C\to B^D$ zadaną następująco: niech $\alpha$ będzie pewną funkcją z $A^C$. $\mathrm{\Phi }(\alpha )=f\circ \alpha \circ g^{-1}$. Sprawdź, że $\mathrm{\Phi }$ jest bijekcją.
3. Definiujemy funkcje $\mathrm{{\rm Y}}:(A^B{)}^C\to A^{B\times C}$. Niech $x$ będzie dowolną funkcją ze zbioru $(A^B{)}^C$ oraz niech $b\in B$ i $c\in C$. $\mathrm{{\rm Y}}(x)(b,c)=x(c)(b)$. Sprawdź, że $\mathrm{{\rm Y}}$ jest bijekcją.
4. Definiujemy funkcje $\alpha :A^C\times B^C\to (A\times B{)}^C$. Niech $f,g$ będą funkcjami ze zbiorów odpowiednio $A^C$ i $B^C$ oraz niech $c\in C$. Definiujemy $\alpha (f,g)(c)=(f(c),g(c))$. Sprawdź, że $\alpha$ jest bijekcją.
5. Definiujemy funkcje $\kappa :A^{B\cup C}\to A^B\times A^C$. Niech $x$ będzie funkcją ze zbioru $A^{B\cup C}$. Definiujemy $\kappa (x)=(x{\mid }_B,x{\mid }_C)$, gdzie $x{\mid }_B,x{\mid }_C$ są odpowiednio zawężeniami funkcji $x$ do zbiorów $B$ lub $C$. Sprawdź, że $\kappa$ jest bijekcją.
6. Zbiorowi $A$ przyporządkowujemy jego funkcję charakterystyczną.

Rozwiązanie

Dowody poszczególnych punktów

1. Ustalmy zbiory $A,B,C$ i $D$ takie, że $A{\sim }_{m}B$ i $C{\sim }_{m}D$ oraz $A\cap C=B\cap D=\mathrm{\varnothing }$. Definicja równoliczności gwarantuje istnienie bijekcji $f:A\to B$ i $g:C\to D$. Zdefiniujmy relację $h=f\cup g$. Niewątpliwie $h\subset (A\cup C)\times (B\cup D)$, a ponieważ $A\cap C=\mathrm{\varnothing }$ wnioskujemy, że $h$ jest funkcją. Ponieważ $f$ i $g$ były surjekcjami, to również $h$ jest surjekcją na $B\cup D$. Ponieważ $B\cap D=\mathrm{\varnothing }$ i funkcje $f$ i $g$ były iniekcjami, wnioskujemy, że $h$ jest iniekcją, co kończy dowód.

2. Niech $f:A\to B$ i $g:C\to D$ będą bijekcjami. Rozważmy funkcję $\mathrm{\Phi }:A^C\to B^D$ zdefiniowaną, dla dowolnego $\alpha \in A^C$ jako

$\mathrm{\Phi }(\alpha )=f\circ \alpha \circ g^{-1}$

Wykażemy, że $\mathrm{\Phi }$ jest bijekcją. Dla surjektywności ustalmy dowolną funkcję $\beta \in B^D$, wtedy $f^{-1}\circ \beta \circ g\in A^C$ i oczywiście $\mathrm{\Phi }(f^{-1}\circ \beta \circ g)=f\circ f^{-1}\circ \beta \circ g\circ g^{-1}=\beta$, co należało wykazać. Pozostaje udowodnić, że $\mathrm{\Phi }$ jest iniekcją. Ustalmy $\alpha$ i ${\alpha }^{\prime }$ w $A^C$ takie, że $\mathrm{\Phi }(\alpha )=\mathrm{\Phi }({\alpha }^{\prime })$. Wtedy $f\circ \alpha \circ g^{-1}=f\circ {\alpha }^{\prime }\circ g^{-1}$ i obkładając obie strony równości przez $f^{-1}$ z lewej strony i $g$ z prawej otrzymujemy $\alpha ={\alpha }^{\prime }$, co dowodzi, że $\mathrm{\Phi }$ jest iniekcją. Dowód jest zakończony.

3. Definiujemy funkcje $\mathrm{{\rm Y}}:(A^B{)}^C\to A^{B\times C}$. Niech $x$ będzie dowolną funkcją ze zbioru $(A^B{)}^C$. Dla dowolnych $b\in B$ i $c\in C$ definiujemy $\mathrm{{\rm Y}}(x)(b,c)=x(c)(b)$. Pozostaje wykazać, że $\mathrm{{\rm Y}}$ jest bijekcją. Dla wykazania iniektywności wybierzmy dwie dowolne funkcje $x$ i $x^{\prime }$ z $(A^B{)}^C$. Wtedy, dla dowolnego $c\in C$ i $b\in B$ mamy $x(c)(b)=x^{\prime }(c)(b)$, czyli, dla dowolnego $c\in C$ funkcje $x(c)$ i $x^{\prime }(c)$ są równe. Wnioskujemy, że funkcje $x$ i $x^{\prime }$ są identyczne na każdym z argumentów, czyli $x=x^{\prime }$, co należało wykazać. Aby wykazać, że $\mathrm{{\rm Y}}$ jest surjekcją, ustalmy dowolny $y\in A^{B\times C}$ i zdefiniujmy funkcję $x$ taką, że $x(c)(b)=y(b,c)$. Oczywiście $x\in (A^B{)}^C$ i $\mathrm{{\rm Y}}(x)=y$, co należało wykazać.

4. Definiujemy funkcje $\alpha :A^C\times B^C\to (A\times B{)}^C$. Niech $f,g$ będą funkcjami ze zbiorów odpowiednio $A^C$ i $B^C$ oraz niech $c\in C$. Definiujemy $\alpha (f,g)(c)=(f(c),g(c))$. Ustalmy dwie pary funkcji $(f,g)$ oraz $(f^{\prime },g^{\prime })$ z $A^C\times B^C$ i załóżmy, że $\alpha (f,g)=\alpha (f^{\prime },g^{\prime })$, czyli $(f(c),g(c))=(f^{\prime }(c),g^{\prime }(c))$, dla każdego $c$. To implikuje, że $f=f^{\prime }$ oraz $g=g^{\prime }$, czyli $\alpha$ jest iniekcją. Dla wykazania surjektywności ustalmy dowolną funkcję $h\in (A\times B{)}^C$ i niech $h_1:C\to A$ i $h_2:C\to B$ będą funkcjami takimi, że $h(c)=(h_1(c),h_2(c))$. Wtedy oczywiście $\alpha (h_1,h_2)=h$, czyli $\alpha$ jest surjekcją, czego należało dowieść.

5. Definiujemy funkcje $\kappa :A^{B\cup C}\to A^B\times A^C$. Dla dowolnego $x$ elementu zbioru $A^{B\cup C}$ definiujemy $\kappa (x)=(x{\mid }_B,x{\mid }_C)$, gdzie $x{\mid }_B,x{\mid }_C$ są odpowiednio zawężeniami funkcji $x$ do zbiorów $B$ i $C$. Załóżmy, niewprost, że $\kappa$ nie jest iniekcją. Istnieją wtedy dwie różne funkcje $x$ i $x^{\prime }$ elementy $A^{B\cup C}$ takie, że $\kappa (x)=\kappa (x^{\prime })$, czyli $x{\mid }_B=x^{\prime }{\mid }_B$ oraz $x{\mid }_C=x^{\prime }{\mid }_C$, co jest oczywistą sprzecznością. Dla dowodu surjektywności ustalmy dwie funkcje $y_1\in A^B$ i $y_2\in A^C$, wtedy $y_1\cup y_2\in B\cup C\times A$, a ponieważ $A\cap B=\mathrm{\varnothing }$, wnioskujemy, że $y_1\cup y_2$ jest funkcją. Oczywiście $\kappa (y_1\cup y_2)=(y_1,y_2)$ co dowodzi surjektywności.

6. Ustalmy dowolny zbiór $A$. Zdefiniujmy funkcję $\alpha :2^A\to {𝒫}(A)$, kładąc $\alpha (f)=\stackrel{-1}{\overrightarrow{f}}(1)$. Wtedy, jeśli $\alpha (f)=\alpha (f^{\prime })$, to $\stackrel{-1}{\overrightarrow{f}}(1)=\stackrel{-1}{\overrightarrow{f^{\prime }}}(1)$ i, co za tym idzie, $\stackrel{-1}{\overrightarrow{f}}(0)=A\setminus \stackrel{-1}{\overrightarrow{f}}(1)=A\setminus \stackrel{-1}{\overrightarrow{f^{\prime }}}(1)=\stackrel{-1}{\overrightarrow{f^{\prime }}}(0)$, czyli $f=f^{\prime }$, co dowodzi iniektywności. Dla dowodu surjektywności ustalmy dowolny zbiór $B\subset A$ i zdefiniujmy jego funkcję charakterystyczną jako $f$ takie, że $f(x)=1$, jeśli $x\in B$ i $f(x)=0$, jeśli $x\notin B$. Otrzymujemy $\alpha (f)=B$, co dowodzi surjektywności.

Definicja 1.6

Zbiór $A$ nazywamy skończonym, gdy $A{\sim }_{m}n$, dla pewnej liczby naturalnej $n$.

Zbiór $A$ nazywamy nieskończonym, gdy $A$ nie jest skończony.

Jako zadania podamy dwa następujące proste fakty:

Ćwiczenie 1.7

Podzbiór zbioru skończonego jest skończony. Obraz przez funkcje zbioru skończonego jest skończony.

Wskazówka

Pokaż indukcją na $n$ prawdziwość następującego zdania: każdy podzbiór zbioru $n$ jest skończony. Pokaż indukcją na $n$ prawdziwość następującego zdania: obraz każdego podzbioru $n$ jest skończony.

Rozwiązanie

Wykażemy przez indukcję, że każdy podzbiór liczby naturalnej jest bijektywny z jakąś liczbą naturalną. Indukcja przebiega ze względu na zmienną $n$.

• Jeśli $n=0=\mathrm{\varnothing }$, to jedynym podzbiorem zbioru pustego jest on sam. Zbiór pusty jest równoliczny ze sobą samym poprzez funkcję pustą.
• Załóżmy, że każdy podzbiór $n$ jest równoliczny z jakąś liczbą naturalną. Rozważmy $n+1$ i dowolne $B\subset n+1$. Jeśli $n\notin B$, to $B$ jest równoliczny z jakąś liczbą naturalną na mocy założenia indukcyjnego. Jeśli $n\in B$, rozważmy $B\setminus \{n\}$ -- jest to zbiór, do którego można zastosować założenie indukcyjne i otrzymać liczbę naturalną $m$ oraz bijekcję $f$ pomiędzy $B\setminus \{n\}$ a $m$. Wtedy zbiór $B$ jest równoliczny z $m+1$ poprzez bijekcję:

$f^{\prime }(x)=\{\begin{array}{ll}f(x),& \text{ jeśli }x\ne n,\\ m,& \text{ jeśli }x=n.\end{array}$

Istnienie tej bijekcji dowodzi prawdziwości kroku indukcyjnego.

Pierwsza część ćwiczenia została dowiedziona.

Wykażemy teraz, że obraz zbioru skończonego poprzez funkcję jest skończony. Ustalmy w tym celu dowolny zbiór skończony $A$ i funkcję $f:A\to B$. Ponieważ $A$ jest skończony, istnieje liczba naturalna $n$ i bijekcja $g$ pomiędzy $n$ i $A$. Możemy założyć, że $\overrightarrow{f}(A)=B$. Definiujemy funkcję $h:B\to A$ jako $h(b)=\bigcap \stackrel{-1}{\overrightarrow{(f\circ g)}}(\{b\})$ -- funkcję, która dla dowolnego elementu $b\in B$ zwraca najmniejszą liczbę naturalną w $n$, która jest przekształcana przez $g$ w $\stackrel{-1}{\overrightarrow{f}}(\{b\})$. Otrzymaliśmy bijekcję pomiędzy $B$ a pewnym podzbiorem liczby naturalnej. Korzystając z poprzedniego punktu i z przechodniości relacji równoliczności, wnioskujemy, że $B$ jest skończony.

Podamy twierdzenie, podobne do twierdzenia, które zobaczą państwo w wykładzie 11 (patrz Wykład 11, Twierdzenie 4.1). Wersja ogólniejsza będzie dotyczyła sytuacji, kiedy zbiór $N_0$ jest nieskończony, ale niekoniecznie jest podzbiorem $\mathbb{\mathbb{N}}$. W takim wypadku do dowodu tego twierdzenia będzie potrzebny aksjomat wyboru. W uproszczonej wersji, która podana jest poniżej, aksjomat ten nie będzie nam potrzebny.

Twierdzenie 1.8

Jeżeli $N_0$ jest nieskończonym podzbiorem $\mathbb{\mathbb{N}}$, to $N_0{\sim }_m\mathbb{\mathbb{N}}$.

Dowód

Przy pomocy definiowania przez indukcję (patrz Wykład 7, Twierdzenie 6.1), zbudujmy bijekcję $h$ pomiędzy zbiorem $\mathbb{\mathbb{N}}$ a $N_0$. Zbiór $N_0$ będąc nieskończonym jest niepusty, więc z zasady minimum (patrz Wykład 7, Twierdzenie 5.2) posiada element najmniejszy. Niech:

$h(0)=$ najmniejszy element w $N_0$,

$h(n^{\prime })=$ najmniejszy element, który w $N_0$ jest istotnie większy niż $h(n)$.

Łatwo zauważyć, że dla obraz, dowolnej liczby naturalnej $\overrightarrow{h}(n)$ jest odcinkiem początkowym $N_0$. Równocześnie, na mocy poprzedniego ćwiczenia, wiemy, że obraz ten jest skończony. Ponieważ zbiór $N_0$ jest nieskończony, więc zawsze istnieją w nim elementy poza $\overrightarrow{h}(n)$. Elementy te muszą być większe od $h(n)$, co gwarantuje, że funkcja $h$ jest zdefiniowana dla całego $\mathbb{\mathbb{N}}$. Funkcja $h$ jest oczywiście iniekcją, ponieważ dla $n<m$ mamy $h(n)<h(m)$. Funkcja $h$ jest bijekcją, ponieważ łatwo możemy pokazać, że jeśli $n\in N_0$, to $n\in \overrightarrow{h}(n^{\prime })$.

Zbiory przeliczalne

Podamy poniżej dwie równoważne, jak się okaże, definicje przeliczalności.

Definicja 2.1

Zbiór $X$ jest przeliczalny, gdy $X{\sim }_m{N}_0$, dla pewnego $N_0\subset \mathbb{\mathbb{N}}$.

Definicja 2.2

Zbiór $X$ daje się ustawić w ciąg, gdy istnieje surjekcja $f:\mathbb{\mathbb{N}}\to X$.

Twierdzenie 2.3

Niepusty zbiór $X$ daje się ustawić w ciąg wtedy i tylko wtedy, gdy jest przeliczalny.

Dowód

Jeśli $X$ jest przeliczalny przy bijekcji $f:N_0\to X$, to niewątpliwie daje się ustawić w ciąg - uzupełniamy bijekcje jednym elementem wyjętym z niepustego $X$. Jeśli $X$ daje sie ustawić w ciąg przy użyciu funkcji $f:\mathbb{\mathbb{N}}\to X$ , to z surjektywności mamy, że $\stackrel{-1}{\overrightarrow{f}}(\left\{x\right\})$ jest niepusty dla każdego $x$. Zdefiniujmy funkcje $g:X\to \mathbb{\mathbb{N}}$ jako $g(x)=\bigcap \stackrel{-1}{\overrightarrow{f}}(\{x\})$. Funkcja ta wybiera najmniejsze elementy z przeciwobrazów elementów $X$, jest zatem iniekcją, a więc bijekcja pomiędzy $X$ a podzbiorem $\mathbb{\mathbb{N}}$.

Znowu, tak jak w przypadku Twierdzenia 1.8, radziłbym zapoznać sie z wykładem 11 (patrz Wykład 11) dotyczącym aksjomatu wyboru i jego konsekwencji. W szczególności pożyteczne byłoby przeczytanie podrozdziału 3.1 Twierdzenia dotyczące zbiorów i zawartego w nim Ćwiczenia 3.1. Znajdą tam państwo uogólnienie poprzedniego twierdzenia na sytuacje, gdzie nie zakłada się przeliczalności zbioru $X$.

Twierdzenie 2.4

$X$ jest przeliczalny wtedy i tylko wtedy, gdy $X$ jest skończony lub równoliczny z $\mathbb{\mathbb{N}}$.

Proponuję dowód wykonać jako proste ćwiczenie.

Ćwiczenie 2.5

Dowiedź Twierdzenia 2.4.

Wskazówka

Gdy $X$ jest równoliczny ze skończonym zbiorem $N_0$ to jest skończony, w przeciwnym wypadku zastosuj Twierdzenie 1.8.

Rozwiązanie

Jeśli zbiór $X$ jest skończony (równoliczny z jakąś liczbą naturalną) lub równoliczny z $\mathbb{\mathbb{N}}$, to niewątpliwie jest równoliczny z jakimś podzbiorem $\mathbb{\mathbb{N}}$, czyli przeliczalny. Dla dowodu implikacji w drugą stronę załóżmy, że zbiór $X$ jest przeliczalny, czyli, jak mówi definicja, równoliczny z jakimś podzbiorem $\mathbb{\mathbb{N}}$. Jeśli ten podzbiór jest skończony, to na mocy przechodniości relacji równoliczności wnioskujemy, że zbiór $X$ jest skończony. Jeśli ten podzbiór jest nieskończony, to Twierdzenie 1.8 gwarantuje, że jest on równoliczny z $\mathbb{\mathbb{N}}$. Korzystając z przechodniości relacji równoliczności, wnioskujemy, że w tym przypadku $X$ jest równoliczny z $\mathbb{\mathbb{N}}$, co kończy dowód.

Lemat 2.6

Własności zbiorów przeliczalnych:

1. Podzbiór przeliczalnego zbioru jest przeliczalny.
2. Suma zbiorów przeliczalnych jest przeliczalna.
3. ${\mathbb{\mathbb{N}}}^2$ jest przeliczalny.
4. Iloczyn kartezjański zbiorów przeliczalnych jest przeliczalny.
5. ${\mathbb{\mathbb{N}}}^k$ dla $k\ge 1$ jest przeliczalny.
6. Niech $x\in {𝒫}({𝒫}(X))$ będzie skończoną rodziną zbiorów przeliczalnych. Wtedy $\prod x$ jest przeliczalny.
7. Jeżeli $X$ przeliczalny oraz $r\in {𝒫}({𝒫}(X))$jest rozkładem, to $r$ jest przeliczalny.

Twierdzenie jest proste i dlatego proponuję wykonać dowody samodzielnie jako ćwiczenie.

Ćwiczenie 2.7

Dowiedź Lematu 2.6.

Wskazówka

1. Zacieśnij funkcje ustalającą równoliczność do podzbioru.

2. Załóżmy dodatkowo, że oba zbiory $A$ i $B$ są rozłączne. Mając dwie surjekcje $f:\mathbb{\mathbb{N}}\to A$ oraz $g:\mathbb{\mathbb{N}}\to B$, zbuduj nową $h:N\to A\cup B$ następująco:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle h(n) = \left\{ \begin{array} {ll} f(n/2), & \text{ dla parzystego } n, \\ g((n-1)/2) , & \text{ dla nieparzystego } n. \end{array} \right} .

Dla zbiorów nierozłącznych rozważ $A\cup B=A\cup (B\setminus A)$.

3. Wykonaj obliczenia tak jak w ćwiczeniu 4.9 wykładu 6 (patrz Wykład 6, Ćwiczenie 4.9 ).

4. Prosta konsekwencja 3.

5. Dowód przy pomocy prostej indukcji na $n$ i obserwacji 3 oraz 4.

6. Niech $x=\{x_1,\dots x_n\}$, wtedy $\prod x$ jest równoliczny z $x_1\times \dots \times x_n$, gdy zbiory $x_i$ są różne. Gdy nie są, produkt jest jeszcze mniejszy. Zapoznaj się z Twierdzeniem 6.2 Wykładu 6 (patrz Wykład 6, Twierdzenie 6.2).

7. Ponieważ $r$ jest rozkładem składa, się z niepustych

podzbiorów przeliczalnego $X$. Gwarantuje to istnienie iniekcji $g:r\to X$, przyporządkowującej zbiorowi jeden jego element. Istnieje $f:X\to N_0$ bijekcja. Zatem $f\circ g:r\to N_0$ jest iniekcją.

Rozwiązanie

Rozwiązania:

1. Ustalmy dowolny przeliczalny zbiór $X$ i dowolny $Y$ taki, że $Y\subset X$. Aby wykazać, że $Y$ jest przeliczalny, wystarczy zawęzić bijekcję $f:X\to N_0\subset \mathbb{\mathbb{N}}$ do zbioru $Y$. Funkcja $f{\mid }_Y$ jest bijekcją pomiędzy $Y$ a pewnym podzbiorem $N_0$, świadcząc o przeliczalności $Y$.

2. Postępując jak w podpowiedzi, załóżmy, że zbiory $A$ i $B$ są rozłączne. Jeśli któryś ze zbiorów jest pusty, to teza jest trywialna. W przeciwnym przypadku mamy dwie surjekcje $f:\mathbb{\mathbb{N}}\to A$ oraz $g:\mathbb{\mathbb{N}}\to B$. Definiujemy funkcję $h:N\to A\cup B$ jako:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle h(n) = \left\{ \begin{array} {ll} f(n/2), & \text{ dla parzystego } n, \\ g((n-1)/2) , & \text{ dla nieparzystego } n. \end{array} \right}

Funkcja $h$ jest dobrze określona, ponieważ żadna liczba naturalna nie może być równocześnie parzysta i nieparzysta (Wykaż, że dla dowolnych liczb naturalnych $k$ i $l$ mamy $2k\ne 2l+1$). Aby wykazać, że $h$ jest surjekcją, ustalmy dowolny element $a\in A$. Ponieważ $f$ jest surjekcją, istnieje $n\in \mathbb{\mathbb{N}}$ takie, że $f(n)=a$. Używając definicji $h$, dostajemy $h(2n)=f(n)=a$ -- element $a$ jest w obrazie funkcji $h$. Dla elementów zbioru $B$ postępujemy podobnie, biorąc $2n+1$ zamiast $2n$ jako argument dla $h$. Wykazaliśmy, że funkcja $h$ jest surjekcją, co kończy dowód.

Jeśli zbiory nie są rozłączne, to stosujemy powyższe rozumowanie do zbiorów $A$ i $B\setminus A$. Zbiór $A$ jest przeliczalny na mocy założenia, a zbiór $B\setminus A$ na mocy założenia i poprzedniego podpunktu.

3. Ćwiczenie 4.9 z Wykładu 6 gwarantuje istnienie iniekcji $f$ z ${\mathbb{\mathbb{N}}}^2\to \mathbb{\mathbb{N}}$. Funkcja $g$ zdefiniowana jako:

$g(n)=\{\begin{array}{ll}(m,k),& \text{ jeśli }f(m,k)=n,\\ (0,0),& \text{ jeśli }n\notin \overrightarrow{f}({\mathbb{\mathbb{N}}}^2),\end{array}$

jest poszukiwaną surjekcją. Funkcja $g$ jest dobrze zdefiniowana, ponieważ $f$ jest iniekcją i jest surjekcją, ponieważ $f$ jest funkcją.

4. Dla dowodu kolejnego faktu ustalmy dwa niepuste (twierdzenie jest trywialne w przeciwnym przypadku) zbiory przeliczalne $A$ i $B$ i surjekcje $f:\mathbb{\mathbb{N}}\to A$, $f^{\prime }:\mathbb{\mathbb{N}}\to B$. Niech $g$ będzie funkcją zdefiniowaną w poprzednim podpunkcie, wtedy funkcja $h:\mathbb{\mathbb{N}}\to A\times B$ zdefiniowana jako :

$h(n)=(f(m),f^{\prime }(k))\text{ jeśli }g(n)=(m,k)$

jest poszukiwaną surjekcją. Funkcja $h$ jest oczywiście dobrze zdefiniowana i jest surjekcją, ponieważ zarówno $f,f^{\prime }$ jak i $g$ są surjekcjami.

5. Dowód jest indukcją na $k$:

• Jeśli $k=0$, to ${\mathbb{\mathbb{N}}}^k$ jest równe $\{\mathrm{\varnothing }\}$, czyli przeliczalne.
• Jeśli $k=1$, to poszukiwana surjekcja $\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ jest funkcją identycznościową.
• Niech $f:\mathbb{\mathbb{N}}\to {\mathbb{\mathbb{N}}}^k$ będzie surjekcją istniejącą na mocy założenia indukcyjnego. Niech $g:\mathbb{\mathbb{N}}\to {\mathbb{\mathbb{N}}}^2$ będzie surjekcją istniejącą na podstawie ćwiczeń powyżej, wtedy funkcja $h:\mathbb{\mathbb{N}}\to {\mathbb{\mathbb{N}}}^{k+1}$ zdefiniowana jako:

$h(n)=(f(m),k)\text{ jeśli }g(n)=(m,k)$

jest surjekcją. $h$ jest niewątpliwie dobrze zdefiniowaną funkcją. Aby wykazać surjektywność $h$, ustalmy dowolny element zbioru ${\mathbb{\mathbb{N}}}^{k+1}$ postaci $(t,k)$, gdzie $k\in \mathbb{\mathbb{N}}$ i $t\in {\mathbb{\mathbb{N}}}^k$. Ponieważ $f$ jest surjekcją istnieje $m$ takie, że $f(m)=k$. Ponieważ $g$ jest surjekcją, istnieje $n$ takie, że $g(n)=(m,k)$. Trywialnie wtedy $h(n)=(t,k)$, co dowodzi, że $h$ jest surjekcją.

6. Dowód przebiega indukcyjnie. Wykażemy, że dla każdej liczby naturalnej $n$, jeśli $x\in {𝒫}({𝒫}(X))$ i $x{\sim }_{m}n$ i każdy element $x$ jest przeliczalny, to $\prod x$ jest przeliczalny:

• Jeśli $n=0$, to $\prod x=\{\mathrm{\varnothing }\}$ jest przeliczalny.
• Jeśli $n=1$, to $\prod x$ jest równoliczny z jedynym elementem $x$, który jest przeliczalny na mocy założenia.
• Weźmy dowolny $x$ równoliczny z $n+1$. Jeśli któryś z elementów $x$ jest pusty, to $\prod x=\mathrm{\varnothing }$ jest oczywiście przeliczalny. W przeciwnym przypadku niech $x^{\prime }\subset x$ będzie podzbiorem $x$ równolicznym z $n$ - wtedy $x=x^{\prime }\cup \{y\}$, dla pewnego $y$. Na mocy założenia indukcyjnego istnieje surjekcja $f:\mathbb{\mathbb{N}}\to \prod x^{\prime }$. Ponieważ każdy element $x$ jest przeliczalny, to istnieje surjekcja z $f^{\prime }:\mathbb{\mathbb{N}}\to y$ i na mocy wcześniejszych ćwiczeń istnieje surjekcja $g:\mathbb{\mathbb{N}}\to {\mathbb{\mathbb{N}}}^2$ definiujemy funkcję $h:\mathbb{\mathbb{N}}\to \prod x$ jako:

$h(n)=(f(m),f^{\prime }(k))$ jeśli $g(n)=(m,k)$

Rozumując podobnie jak w punkcie poprzednim, wykazujemy, że $h$ jest surjekcją, co kończy dowód.

Ponieważ produkt zbioru składającego się ze zbiorów przeliczalnych i równolicznego z dowolną liczbą naturalną jest przeliczalny, więc produkt dowolnego skończonego zbioru zbiorów przeliczalnych jest przeliczalny.

7. Ustalmy dowolny, przeliczalny zbiór $X$ i surjekcję $f:\mathbb{\mathbb{N}}\to X$. Ustalmy $r$, dowolny podział $X$. Funkcja $g:\mathbb{\mathbb{N}}\to r$ zdefiniowana jako:

$g(n)=s$ jeśli $f(n)\in s,$

będzie oczekiwaną surjekcją. Funkcja $g$ jest dobrze zdefiniowana, ponieważ $r$ jest podziałem i jest surjekcją, ponieważ każdy element $r$ jest niepusty i $f$ jest surjekcją.

Twierdzenie 2.8

Zbiory liczb całkowitych i wymiernych są przeliczalne.

Dowód

Jest to prosta konsekwencja punktu 7 Lematu 2.6. Zbiór $\mathbb{\mathbb{Z}}=\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}/\approx$ oraz zbiór $\mathbb{\mathbb{Q}}=\mathbb{\mathbb{Z}}\times {\mathbb{\mathbb{Z}}}^{*}/\sim$ są rozkładami zbiorów przeliczalnych.

Dla kontrastu udowodnimy, że zbiór liczb rzeczywistych przeliczalny nie jest.

Twierdzenie 2.9 [Cantora]

Zbiór liczb rzeczywistych nie jest przeliczalny.

Dowód

Podany poniżej dowód pochodzi od Georga Cantora. Pokażemy, że odcinek liczb rzeczywistych $[0,1]$ nie jest przeliczalny. Cały zbiór $\mathbb{ℝ}$ jako większy też nie może być przeliczalny. Dla dowodu niewprost przypuśćmy, że jest przeciwnie. Załóżmy zatem, że istnieje surjektywny ciąg $f:\mathbb{\mathbb{N}}\to [0,1]$. Zdefiniujemy indukcyjnie dwa ciągi punktów $a:\mathbb{\mathbb{N}}\to [0,1]$ i $b:\mathbb{\mathbb{N}}\to [0,1]$ odcinka $[0,1]$ o własności $a_i<b_i$ tak, aby $i$-ty element ciągu $f$ nie należał do odcinka domkniętego $[a_{i+1},b_{i+1}]$. Tak więc kładziemy początkowo $a_0=0$ i $b_0=1$. Przypuśćmy, że zdefiniowane są już obydwa ciągi, dla $i\le n$. Odcinek $[a_i,b_i]$ dzielimy na trzy równe części i za $a_{i+1}$ i $b_{i+1}$ wybieramy końce tego spośród nich, do którego nie należy element $f_i$ ciągu $f$.

Jako ćwiczenie podamy sprawdzenie następujących własności ciągów $a_i$ i $b_i$:

1. Ciąg $a$ jest słabo rosnący, czyli $a_i\le a_{i+1}$.
2. Ciąg $b$ jest słabo malejący, czyli $b_i\ge b_{i+1}$.
3. $b_i-a_i=\frac{1}{3^i}$.
4. $|b_{i+1}-b_i|\le {\left(\frac{2}{3}\right)}^i$.
5. $|a_{i+1}-a_i|\le {\left(\frac{2}{3}\right)}^i$.

Własności te implikują fakt, że zarówno $a_i$ jak i $b_i$ są ciągami Cauchy'ego; jak i to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba rzeczywista $x$ zadana jednocześnie przez aproksymacje $a$ i $b$, czyli $x=[a]=[b]$. Ze względu na na 1. i 2. $a_i\le x\le b_i$, dla każdego $i$. To przeczy samej definicji wybierania odcinków, którą przeprowadzono tak, by elementy ciągu $f$ nie leżały w żadnym z nich. Zatem $f$ nie mógł być surjekcją.

Podamy poniżej definicje nierówności na mocach zbiorów.

Definicja 2.10

$A{\le }_{m}B$ wtw istnieje iniekcja $f:A\to B$.

$A{<}_{m}B$ wtw $A{\le }_{m}B$ i nieprawda, że $A{\sim }_{m}B$.

Twierdzenie 2.11

Następujące warunki są równoważne:

1. Dla dowolnych zbiorów $A,B$ zachodzi $A{\le }_{m}B$ i $B{\le }_{m}A$, to $A{\sim }_{m}B$.
2. Dla dowolnych zbiorów $A,B$ zachodzi $A{\le }_{m}B$ i $B\subset A$, to $A{\sim }_{m}B$.
3. Dla dowolnych zbiorów $A,B,C$ zachodzi $A{<}_{m}B$ i $B{<}_{m}C$, to $A{<}_{m}C$.

Dowód

$(2)\Rightarrow (1)$. Niech $A{\le }_{m}B$ i $B{\le }_{m}A$. Niech $f:B\to A$ iniekcja oraz niech $B_0=\overrightarrow{f}(B)$. Mamy więc $A{\sim }_m{B}_0$ oraz $B_0\subset A$. Stosując $(2)$ do $A,B_0$, otrzymujemy $A{\sim }_m{B}_0$, co wobec $B{\sim }_m{B}_0$ daje $A{\sim }_{m}B$.

$(1)\Rightarrow (3)$. Z założeń (3) mamy, że $A{<}_{m}B$ i $B{<}_{m}C$. Można je osłabić, otrzymując $A{\le }_{m}B$ i $B{\le }_{m}C$. Z przechodniości ${\le }_m$ (co odpowiada składaniu iniekcji) otrzymujemy $A{\le }_{m}C$. Pozostaje dowieść, że nieprawdą jest $A{\sim }_{m}C$. Gdyby $A{\sim }_{m}C$, to mielibyśmy $B{\le }_{m}A$. Stosując $(1)$ dla $A,B$, mielibyśmy $A{\sim }_{m}B$, co przeczy $A{<}_{m}B$.

$(3)\Rightarrow (2)$. Niech $A{\le }_{m}B$ i $B\subset A$, co daje też $B{\le }_{m}A$. Gdyby nieprawdą było, że $A{\sim }_{m}B$, to mielibyśmy zarówno $A{<}_{m}B$ jak i $B{<}_{m}A$, co na mocy $(3)$ dawałoby sprzeczność $A{<}_{m}A$.

W twierdzeniu powyżej pokazaliśmy równoważność trzech warunków, nie pokazując, czy którykolwiek z nich jest prawdziwy. Teraz pokażemy $(1)$. Twierdzenie to znane jest pod nazwą twierdzenia Cantora-Bernsteina. Zatem twierdzenie to wyraża słabą antysymetrię relacji porządku na mocach zbiorów. Zobaczymy, że jest ono niezwykle przydatne do uzasadnienia wielu faktów teorii mocy, co bez tego twierdzenia często pociągałoby konieczność przeprowadzania długich i skomplikowanych dowodów.

Twierdzenie 2.12 [Cantora - Bernsteina]

Jeżeli $A{\le }_{m}B$ i $B{\le }_{m}A$ to $A{\sim }_{m}B$.

Dowód

Przygotowania do tego dowodu zostały podjęte wcześniej. Służył do tego Wykład 6 poświęcony między innymi obrazom zbiorów przez funkcje. Nietrywialnym było dowiedzenie twierdzenia Knastera-Tarskiego, a przy jego pomocy lematu Banacha. Ten wysiłek zwróci się nam teraz (patrz Wykład 6). Niech zatem $f:A\to B$ i $g:B\to A$ będą iniekcjami. Na mocy lematu Banacha (patrz Wykład 6, Lemat Banacha), istnieją rozłączne zbiory $A_1,A_2$ wzajemnie uzupełniające się do $A$ jak i rozłączne zbiory $B_1,B_2$ wzajemnie uzupełniające się do $B$ takie, że $\overrightarrow{f}(A_1)=B_1$ i symetrycznie $\overrightarrow{g}(B_2)=A_2$. Możemy zatem na rozłącznych zbiorach $A_1,A_2$ skleić dwie iniekcje $f{|}_{A_1}$ i $g^{-1}{|}_{A_2}$ będące zawężeniami oryginalnych funkcji. Otrzymane sklejenie $f{|}_{A_1}\cup g^{-1}{|}_{A_2}$ jest bijekcją.

Poniżej poznamy twierdzenie pochodzące od Cantora, pokazujące, że można budować zbiory o dowolnie wielkiej mocy. Z niego i z twierdzenia Cantora-Bernstaina pokażemy, że zbiorów jest tak dużo, że same nie tworzą zbioru. Fakt ten jest już nam znany $x\notin x$ (patrz Wykład 4, Fakt 10.1) i jest konsekwencja aksjomatu regularności. Niemniej przeprowadzimy prosty dowód, odwołujący się do faktów z teorii mocy. Dowód poniższy jest dowodem przekątniowym. W wykładach dotyczących teorii obliczeń i logiki znajdą państwo wiele takich dowodów.

Twierdzenie 2.13 [Cantora]

$A{<}_m{𝒫}(A)$.

Dowód

Łatwo zauważyć, że istnieje iniekcja wkładająca $A$ w ${𝒫}(A)$. Przykładowo możemy wziąć funkcje przypisującą elementowi $x$ zbioru $A$ singleton $\left\{x\right\}$. Załóżmy, że istnieje bijekcja $f:A\to {𝒫}(A)$. Obrazami elementów ze zbioru $A$ są podzbiory $A$. Utwórzmy zbiór $C=\{z\in A:z\notin f(z)\}$. Ze względu na surjektywność $f$ musi istnieć taki element $z_0\in A$, że $f(z_0)=C$. Rozstrzygnijmy problem, czy $z_0\in f(z_0)$. Jeżeli tak, to $z_0\in C$, a zatem $z_0\notin f(z_0)$ sprzeczność. Jeżeli nie to, $z_0\notin f(z_0)$, a zatem $z_0\in C$, czyli $z_0\in f(z_0)$ sprzeczność.

Twierdzenie 2.14 [Cantora]

Nie istnieje zbiór wszystkich zbiorów.

Dowód

Gdyby taki zbiór istniał, mielibyśmy trudności z przypisaniem mu mocy. Mianowicie, niech ten zbiór nazywa się $A$. W takim razie ${𝒫}(A)\subset A$, bo każdy podzbiór $A$ jest zbiorem. Trywialnie mamy w drugą stronę $A{\le }_m{𝒫}(A)$. Zatem z twierdzenia Cantora-Bernsteina otrzymujemy $A{\sim }_m{𝒫}(A)$, co jest sprzeczne z twierdzeniem Cantora.

Twierdzenie 2.15

Każdy zbiór nieskończony zawiera podzbiór przeliczalny równoliczny z $\mathbb{\mathbb{N}}$.

Dowód

Dowód tego bardzo intuicyjnego faktu odwołuje się do aksjomatu wyboru. Proszę o zapoznanie się z dowodem tego twierdzenia w wykładzie 11, Twierdzenie 4.1, oraz o zapoznanie się z innymi faktami tego rozdziału, które wymagają aksjomatu wyboru (patrz Wykład 11, Twierdzenie 4.1).

Zbiory mocy continuum

Definicja 3.1

Zbiór nazywamy nieprzeliczalnym, gdy nie jest przeliczalny.

Ćwiczenie 3.2

Zbiory $2^{\mathbb{\mathbb{N}}}$ oraz ${\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}$ nie są przeliczalne.

Wskazówka

Dowód należy poprowadzić niewprost, stosując metodę przekątniową. W pierwszym przypadku rozważyć bijekcje $f:\mathbb{\mathbb{N}}\to 2^{\mathbb{\mathbb{N}}}$. Przy jej pomocy zbudować ciąg $g:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ zadany wzorem $g(i)=1-f(i)(i)$. Drugi fakt wynika z pierwszego. Gdyby dowodzić go niezależnie, należy tak jak poprzednio dla bijekcji $h:\mathbb{\mathbb{N}}\to {\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}$ rozważyć przykładowo funkcje $n\to h(n)(n)+1$.

Rozwiązanie

Dla dowodu niewprost ustalmy surjekcję $f:\mathbb{\mathbb{N}}\to 2^{\mathbb{\mathbb{N}}}$. Zdefiniujmy specjalny element zbioru $2^{\mathbb{\mathbb{N}}}$ w następujący sposób:

$g(n)=\{\begin{array}{ll}0,& \text{ jeśli }f(n)(n)=1,\\ 1,& \text{ jeśli }f(n)(n)=0.\end{array}$

Funkcja $g$ różni się od obrazu liczby $n$ względem $f$ na $n$-tym miejscu. Ponieważ $f$ jest bijekcją, to istnieje $n_0$ takie, że $f(n_0)=g$, czyli $f(n_0)(n)=g(n)$, dla każdego $n$. Z definicji $g$ wynika, że $g(n_0)\ne f(n_0)(n_0)$, co daje oczekiwaną sprzeczność.

Gdyby istniała surjekcja $f$ z $\mathbb{\mathbb{N}}$ w ${\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}$, to możemy zdefiniować $g$ jako:

$g(n)=\{\begin{array}{ll}f(n),& \text{ jeśli }\overrightarrow{f(n)}(\mathbb{\mathbb{N}})\subset 2,\\ z,& \text{ w przeciwnym przypadku, }\end{array}$

gdzie $z:\mathbb{\mathbb{N}}\to 2$ jest funkcją stale równą zero. Funkcja $g$ jest surjekcją z $\mathbb{\mathbb{N}}$ na $2^{\mathbb{\mathbb{N}}}$, co jest sprzecznością z poprzednim faktem.

Definicja 3.3

Mówimy, że zbiór jest mocy continuum, gdy jest równoliczny z $\mathbb{ℝ}$.

Lemat 3.4

Każdy przedział obustronnie otwarty jest mocy continuum.

Dowód

Na początku pokażemy, że istnieje bijekcja pomiędzy przedziałem otwartym liczb rzeczywistych $(-1,1)$ a $\mathbb{ℝ}$. Bijekcją taką jest $x\to \frac{x}{1-x^2}$. (Jako ćwiczenie spróbuj narysować wykres tej funkcji.) Następnie łatwo zauważyć, że każde dwa przedziały otwarte są równoliczne. (Jako ćwiczenie napisz wzór na funkcję liniową pomiędzy dwoma zadanymi otwartymi przedziałami.)

Lemat 3.5

Jeżeli $A\subset \mathbb{ℝ}$ i $A$ zawiera pewien przedział otwarty, to $A$ jest mocy continuum.

Dowód

Prosta konsekwencja Twierdzenia 2.12 Cantora-Bernsteina.

Następne dwa lematy pokazują, że zbiory mocy kontinuum są odporne na dodawanie i ujmowanie zbiorów przeliczalnych. Po każdej takiej operacji moc zbioru jest taka, jak była. Proszę o zapoznanie się z prostymi dowodami tych lematów. Może to być pomocne w rozwiązywaniu zadań.

Lemat 3.6

Jeżeli $B\subset A$ jest przeliczalnym podzbiorem zbioru $A$ mocy continuum, to

$A\setminus B$ jest mocy continuum.

Dowód

Załóżmy bez straty ogólności, że $B\subset A$. Zauważmy, że $A\setminus B$ jest nieprzeliczalny. Inaczej przeczyłoby to Twierdzeniu 2.9 o nieprzeliczalności $\mathbb{ℝ}$. W takim razie $A\setminus B$ jest nieskończony. Można zatem odnaleźć w nim na mocy Twierdzenia 2.15 (stosując aksjomat wyboru, zapoznaj się z dowodem tego twierdzenie w wykładzie 11, patrz Wykład 11, Twierdzenie 4.1) nieskończony zbiór przeliczalny $B^{\prime }$. Mamy więc $B\cup B^{\prime }$ jest nieskończonym zbiorem przeliczalnym. Istnieje zatem bijekcja $f:B\cup B^{\prime }\to B^{\prime }$. Mając ją, możemy określić bijekcję $h:A\to A\setminus B$ następująco:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle h(x) = \left\{ \begin{array} {ll} f(x) , & x \in B\cup B', \\ x, & x \notin B\cup B'. \end{array} \right}

Lemat 3.7

Jeżeli $B$ jest przeliczalnym, a $A$ jest mocy continuum, to $A\cup B$ jest mocy continuum.

Dowód

Opiszmy słowami dowód podobny do poprzedniego. Na początku należy odnaleźć w $A$ zbiór nieskończony przeliczalny $B_0$. Zbiór ten musi być równoliczny z $B\cup B_0$. W takim razie można bijektywnie schować zbiór $B\cup B_0$ w zbiorze $B_0$. Następnie należy zdefiniować bijekcję między $A\cup B$ a $A$ tak, aby na fragmencie z poza $B_0$ była identycznością, a na $B\cup B_0$ była poprzednią bijekcją. Sklejenie takich bijekcji na zbiorach rozłącznych jest bijekcją.

Twierdzenie poniższe będzie mieć dla nas fundamentalne znaczenie. Porównuje ono moc dwóch podstawowych dla nas zbiorów $\mathbb{\mathbb{N}}$ i $\mathbb{ℝ}$. Do dowodu posłużymy się konstrukcją rozwinięcia dwójkowego przeprowadzonego w Twierdzeniu 3.15 z Wykładu 8 (patrz Wykład 8, Twierdzenie 3.15 ). Twierdzenie 3.18 tego rozdziału pokazuje bijekcje pomiędzy pewnymi specjalnymi ciągami ze zbioru $2^{\mathbb{\mathbb{N}}}$ a przedziałem $[0,1)$. Przed przeczytaniem tego dowodu zapoznaj sie z Twierdzeniami 3.15, 3.17, 3.18 z Wykładu 8 (patrz Wykład 8).

Twierdzenie 3.8

$2^{\mathbb{\mathbb{N}}}$ jest mocy continuum.

Dowód

Zbiór $2^{\mathbb{\mathbb{N}}}$ rozbijmy na dwa rozłączne podzbiory. Zbiór $X$ taki, jak w Twierdzeniu 3.18 wykładu 8 to znaczy $X=\{a\in 2^{\mathbb{\mathbb{N}}}:{\mathrm{\forall }}_k{\mathrm{\exists }}_{n>k}{a}_n=0\}$ oraz zbiór $X^{\prime }=\{a\in 2^{\mathbb{\mathbb{N}}}:{\mathrm{\exists }}_k{\mathrm{\forall }}_{n>k}{a}_n=1\}$ będący jego uzupełnieniem. Łatwo zauważyć, że $X^{\prime }$ jest przeliczalny, bo można go przedstawić jako przeliczalną sumę zbiorów skończonych. $X^{\prime }$ składa się z ciągów, które od pewnego miejsca są stale równe $1$. Zauważmy, że jest jedynie $2^{k_0}$ takich ciągów, które od $k_0+1$ miejsca są stale równe $1$. Zbiór $X$, jak pokazaliśmy w Twierdzeniu 3.18 w wykładzie 8, jest równoliczny z przedziałem $[0,1)$, a więc przeliczalny. Nasz zbiór $2^{\mathbb{\mathbb{N}}}=X\cup X^{\prime }$ jako suma zbioru continuum i przeliczalnego na mocy Lematu 3.7 jest mocy continuum.

Twierdzenie 3.9

$\mathbb{\mathbb{N}}{<}_m{𝒫}(\mathbb{\mathbb{N}}){\sim }_m{2}^{\mathbb{\mathbb{N}}}{\sim }_m\mathbb{ℝ}$.

Rodzi się naturalne pytanie. Czy istnieje taki zbiór, którego moc dałoby się ulokować pomiędzy mocą zbioru liczb naturalnych a mocą continuum. Czyli, czy istnieje $A$ takie, że

$\mathbb{\mathbb{N}}{<}_{m}A{<}_m\mathbb{ℝ}\text{(3.1)}$

Cantor przypuszczał, że takiego zbioru (mocy) nie ma i że następnym w hierarchii mocy zbiorem po $\mathbb{\mathbb{N}}$ jest $\mathbb{ℝ}$. Przypuszczenie Cantora nazywa się hipotezą continuum. Hipoteza ta była intensywnie badana przez matematyków. W roku 1939 Kurt Gödel pokazał niesprzeczność tej hipotezy z aksjomatami teorii mnogości. Można zatem przyjąć, że taki zbiór jak w hipotezie kontinuum istnieje i nie doprowadzi to teorii mnogości do sprzeczności, o ile sama nie jest sprzeczna. W roku 1963 Paul Joseph Cohen pokazał niezależność hipotezy continuum od aksjomatów teorii mnogości. Oznacza to, że nie można hipotezy udowodnić na gruncie tej teorii, ale nie można też udowodnić jej zaprzeczenia.

Na koniec podamy jako ćwiczenie inną bardzo elegancką i nieodwołującą się do pojęcia liczb naturalnych definicję nieskończoności.

Definicja 3.10

(definicja nieskończoności Dedekinda) Zbiór $X$ jest nieskończony w sensie Dedekinda, gdy istnieje podzbiór właściwy $X_0$ zbioru $X$, który jest z nim równoliczny. Zbiór jest skończony, w sensie Dedekinda, jeśli nie jest nieskończony w sensie Dedekinda.

Ćwiczenie 3.11

Pokaż, że zbiór jest nieskończony wtedy i tylko wtedy, gdy jest nieskończony w sensie Dedekinda.

Wskazówka

Użyj aksjomatu wyboru.

Wskazówka

Skorzystaj z Twierdzenia 4.1 z Wykładu 11.

Rozwiązanie

Implikacja w jedną stronę jest prosta. Jeśli zbiór jest skończony, to jest również skończony w sensie Dedekinda. Wykażemy najpierw, że jeśli z różnej od zera liczby naturalnej $n$ usuniemy dowolny element, to zbiór powstały będzie równoliczny z $n-1$. Usuńmy dowolny element z $n$. Jeśli usunęliśmy $n-1$, to otrzymujemy liczbę $n-1$. Jeśli usunęliśmy $k\ne n-1$, to możemy zdefiniować bijekcję pomiędzy $n\setminus \{k\}$ a $n-1$ poprzez:

$f(m)=\{\begin{array}{ll}m,& \text{ jeśli }m\ne n-1,\\ k,& \text{ jeśli }m=n-1.\end{array}$

Wybierzmy teraz najmniejszą liczbę $n$ równoliczną z inną liczbą naturalną $m$. Niewątpliwie $n$ i $m$ są różne od zera i istnieje bijekcja $f:n\to m$. Jeśli bijekcję $f$ zawężymy do $n-1$, to obraz zawęzi się, na mocy udowodnionego wcześniej wniosku, do podzbioru $m$ równolicznego $m-1$. Wykazaliśmy, że zbiór $n-1$ jest równoliczny $m-1$, co jest sprzecznością z minimalnością $n$. Wykazaliśmy, że żadne dwie różne liczby naturalne nie są równoliczne. Ustalmy teraz dowolny skończony zbiór $X$. Istnieje bijekcja pomiędzy $X$ i $n$, dla pewnej liczby naturalnej $n$. Jeśli $X$ byłby bijektywny ze swoim istotnym podzbiorem, to również $n$ byłoby bijektywne ze swoim istotnym podzbiorem, czyli ze zbiorem równolicznym liczbie naturalnej mniejszej o co najmniej $1$ -- jest to sprzecznością z wcześniej wykazanym faktem.

Dla dowodu implikacji w drugą stronę wykorzystamy Twierdzenia 4.1 z Wykładu 11. Mówi ono, że dla każdego nieskończonego zbioru istnieje iniekcja z $\mathbb{\mathbb{N}}$ w ten zbiór. Ustalmy dowolny nieskończony zbiór $X$ i taką iniekcję $f:\mathbb{\mathbb{N}}\to X$. Niech $Y\subset X$ będzie obrazem $\mathbb{\mathbb{N}}$ względem $f$ tak, że $f:\mathbb{\mathbb{N}}\to Y$ jest bijekcją. Zdefiniujmy funkcję $g:X\to X$:

$h(x)=\{\begin{array}{ll}x& \text{ jeśli }x\notin Y\\ f(n+1)& \text{ jeśli }x=f(n)\in Y.\end{array}$

Jak łatwo sprawdzić funkcja $h:X\to X\setminus \{f(0)\}$ jest bijekcją, co dowodzi, że zbiór $X$ jest równoliczny ze swoim istotnym podzbiorem, czyli że jest nieskończony w sensie Dedekinda.

Wykazaliśmy, że zbiór skończony jest skończony w sensie Dedekinda i że zbiór nieskończony jest nieskończony w sensie Dedekinda co kończy ćwiczenie. Zwróćmy uwagę, że przy dowodzie tego faktu użyliśmy aksjomatu wyboru.

Ćwiczenia

Ćwiczenie 4.1

Wykaż, że ${\mathbb{ℝ}}^{\mathbb{ℝ}}$ jest równoliczne z $2^{\mathbb{ℝ}}$.

Rozwiązanie

Niewątpliwie $2^{\mathbb{ℝ}}{\le }_m{\mathbb{ℝ}}^{\mathbb{ℝ}}$, ponieważ $\{a,b{\}}^{\mathbb{ℝ}}\subset {\mathbb{ℝ}}^{\mathbb{ℝ}}$, gdzie $a$ jest liczbą rzeczywistą $0$, a $b$ liczbą rzeczywistą $1$. Równocześnie ${\mathbb{ℝ}}^{\mathbb{ℝ}}{\sim }_m{2^{\mathbb{\mathbb{N}}}}^{\mathbb{ℝ}}{\sim }_m{2}^{\mathbb{\mathbb{N}}\times \mathbb{ℝ}}{\le }_m{2}^{\mathbb{ℝ}\times \mathbb{ℝ}}{\sim }_m{2}^{2^{\mathbb{\mathbb{N}}}\times 2^{\mathbb{\mathbb{N}}}}{\sim }_m{2}^{2^{\mathbb{\mathbb{N}}}}{\sim }_m{2}^{\mathbb{ℝ}}$, gdzie każde z przejść jest prostą konsekwencją faktów dowiedzionych na wykładzie. Korzystając z Twierdzenia 2.12 Cantora-Bernsteina, wnioskujemy, że ${\mathbb{ℝ}}^{\mathbb{ℝ}}{\sim }_m{2}^{\mathbb{ℝ}}$.

Ćwiczenie 4.2

Wykaż, że ${\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}{\sim }_m{2}^{\mathbb{\mathbb{N}}}$

Rozwiązanie

Podobnie jak poprzednio $2^{\mathbb{\mathbb{N}}}{\le }_m{\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}$. Aby uzyskać nierówność w drugą stronę rozumujemy ${\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}{\le }_m{2^{\mathbb{\mathbb{N}}}}^{\mathbb{\mathbb{N}}}{\sim }_m{2}^{\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}}{\sim }_m{2}^{\mathbb{\mathbb{N}}}$ i Twierdzenie 2.12 Cantora-Bernsteina gwarantuje żądaną równoliczność.

Ćwiczenie 4.3

Jakiej mocy może być zbiór punktów nieciągłości silnie rosnącej funkcji z $\mathbb{ℝ}$ do $\mathbb{ℝ}$?

Wskazówka

Wybierz liczbę wymierną dla każdego z punktów nieciągłości.

Rozwiązanie

Przykłady funkcji silnie rosnących ze skończoną lub równoliczną $\mathbb{\mathbb{N}}$ liczbą punktów nieciągłości są trywialne. Aby wykazać, że dowolna, silnie rosnąca funkcja $f:\mathbb{ℝ}\to \mathbb{ℝ}$ nie może mieć więcej niż przeliczalnie wiele punktów nieciągłości, stworzymy iniekcję, która każdemu punktowi nieciągłości przyporządkowuje jakiś element $\mathbb{\mathbb{Q}}$. Ustalmy punkt nieciągłości $a$. Wtedy $\underset{x\to a^{-}}{\lim }f(x)$ istnieje, ponieważ funkcja jest rosnąca i ograniczona z góry (przez np. $f(a+1)$). Podobnie istnieje $\underset{x\to a^{+}}{\lim }f(x)$. Ponieważ $a$ jest punktem nieciągłości mamy $\underset{x\to a^{-}}{\lim }f(x)<\underset{x\to a^{+}}{\lim }f(x)$. Ponieważ $\mathbb{\mathbb{Q}}$ jest gęste w $\mathbb{ℝ}$ istnieje $r_a\in \mathbb{\mathbb{Q}}$ takie, że $\underset{x\to a^{-}}{\lim }f(x)<r_a<\underset{x\to a^{+}}{\lim }f(x)$. Pozostaje wykazać, że dla dwóch punktów nieciągłości $a$ i $b$, jeśli $a\ne b$, to $r_a\ne r_b$. Ponieważ porządek na $\mathbb{ℝ}$ jest porządkiem liniowym, mamy $a<b$ lub $b<a$. Możemy, bez straty ogólności, założyć ten pierwszy przypadek i znaleźć $c\in \mathbb{ℝ}$ takie, że $a<c<b$. Wtedy $r_a<\underset{x\to a^{+}}{\lim }f(x)<f(c)<\underset{x\to b^{-}}{\lim }f(x)<r_b$, co dowodzi, że funkcja $a\mapsto r_a$ jest iniekcją, jak twierdziliśmy.

Ćwiczenie 4.4

Jaka jest moc zbioru wszystkich silnie rosnących funkcji z $\mathbb{\mathbb{N}}$ w $\mathbb{\mathbb{N}}$?

Rozwiązanie

Każda taka funkcja to podzbiór $\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}$, a więc zbiór wszystkich takich funkcji jest podzbiorem ${𝒫}(\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}})$, który jest równoliczny z ${𝒫}(\mathbb{\mathbb{N}}){\sim }_m{2}^{\mathbb{\mathbb{N}}}$. Wykażemy, że tych funkcji jest dokładnie tyle, co $2^{\mathbb{\mathbb{N}}}$ poprzez zdefiniowanie iniekcji z $2^{\mathbb{\mathbb{N}}}$ w nasz zbiór. Dla dowolnego $f\in 2^{\mathbb{\mathbb{N}}}$ definiujemy $f^{\prime }:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ następująco:

$f^{\prime }(n)=2n+f(n)$

Zwróćmy uwagę, że funkcja $f^{\prime }$ jest silnie rosnąca, ponieważ dla $n<m$ mamy $f^{\prime }(n)=2n+f(n)\le 2n+1<2n+2=2(n+1)\le 2m\le f^{\prime }(m)$. Równocześnie, jeśli $f,g\in 2^{\mathbb{\mathbb{N}}}$ i $f\ne g$, to również $f^{\prime }\ne g^{\prime }$, ponieważ jeśli $f(n)\ne g(n)$, dla pewnego $n\in \mathbb{\mathbb{N}}$, to$f^{\prime }(n)=2n+f(n)\ne 2n+g(n)=g^{\prime }(n)$. Zdefiniowane przekształcenie przyporządkowuje elementom $2^{\mathbb{\mathbb{N}}}$ silnie rosnące funkcje z $\mathbb{\mathbb{N}}$ do $\mathbb{\mathbb{N}}$, dowodząc, że nasz zbiór jest większy na moc niż $2^{\mathbb{\mathbb{N}}}$. Twierdzenie Cantora-Bernsteina gwarantuje, że funkcji tych jest dokładnie continuum.

Ćwiczenie 4.5

Czy na płaszczyźnie istnieje okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną?

Rozwiązanie

Zakładamy, niewprost, że okrąg taki nie istnieje. Wtedy, każdy okrąg ma przynajmniej jeden punkt posiadający obie współrzędne wymierne. Rozważmy wszystkie okręgi o środku w $(0,0)$ -- jest ich continuum wiele i każde dwa mają puste przecięcie. Jeśli każdy z nich miałby punkt o obu współrzędnych wymiernych, to moglibyśmy stworzyć iniekcję z $\mathbb{ℝ}$ w $\mathbb{\mathbb{Q}}\times \mathbb{\mathbb{Q}}$, dowodząc, że $\mathbb{ℝ}$ jest przeliczalny. Sprzeczność ta dowodzi, że na płaszczyźnie istnieje okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną.

Ćwiczenie 4.6

Zbiór $A\subset \mathbb{\mathbb{Q}}$ nazywamy wypukłym, jeśli dla dowolnych $a,b\in A$, jeśli $c\in \mathbb{\mathbb{Q}}$ i $a<c<b$, to $c\in A$. Ile jest zbiorów wypukłych w $\mathbb{\mathbb{Q}}$?

Rozwiązanie

Zbiorów wypukłych w $\mathbb{\mathbb{Q}}$ jest continuum. Oczywiście nie może ich być więcej niż continuum, ponieważ tyle jest wszystkich podzbiorów $\mathbb{\mathbb{Q}}$. Aby wykazać, że nie ma ich mniej, ustalmy iniekcję z przedziału $[0,1]$ w liczbach rzeczywistych w zbiór wypukłych podzbiorów $\mathbb{\mathbb{Q}}$. Dla dowolnej liczby rzeczywistej $r\in [0,1]$ zdefiniujmy:

$I_r=[0,r]\cap \mathbb{\mathbb{Q}}$

Niewątpliwie każdy zbiór $I_r$ jest wypukły, ponieważ jeśli $a<b\in I_r$, to $0\le a$ i $b\le r$, a więc dla każdego $c$ takiego, że $a<c<b$ zachodzi $0\le c\le r$, czyli $c\in I_r$. Pozostaje wykazać, że funkcja $r\mapsto I_r$ jest iniekcją. Ustalmy dwie liczby rzeczywiste $r\ne s$. Bez straty ogólności możemy założyć, że $r<s$. Istnieje wtedy liczba wymierna $t$ taka, że $r<t<s$ i mamy $t\in I_s$ oraz $t\notin I_r$, dowodząc, że $I_r\ne I_s$. Na mocy Twierdzenia Cantora-Bernsteina zbiorów wypukłych w $\mathbb{\mathbb{Q}}$ jest continuum.

Ćwiczenie 4.7

Ile elementów posiada największy, pod względem mocy, łańcuch w $({𝒫}(\mathbb{\mathbb{N}}),\subset )$?

Rozwiązanie

Łańcuch taki nie może posiadać więcej niż continuum elementów, ponieważ moc całego zbioru ${𝒫}(\mathbb{\mathbb{N}})$ jest continuum. Wykażemy, że istnieje w tym zbiorze częściowo uporządkowanym łańcuch o mocy continuum. Zamiast pracować na zbiorze $\mathbb{\mathbb{N}}$ będziemy pracować na zbiorze mu równolicznym $\mathbb{\mathbb{Q}}$. Zwróćmy uwagę, że zdefiniowane w Ćwiczeniu 4.6 zbiory $I_r$ są uporządkowane liniowo przez inkluzję, są podzbiorami $\mathbb{\mathbb{Q}}$ i jest ich continuum wiele. Zbiory te tworzą żądany łańcuch.

Ćwiczenie 4.8

Jaka jest moc zbioru bijekcji z $\mathbb{\mathbb{N}}$ do $\mathbb{\mathbb{N}}$?

Rozwiązanie

Bijekcji tych, podobnie jak funkcji ściśle rosnących w Ćwiczeniu 4.4, nie może być więcej niż continuum. Aby wykazać, że jest ich dokładnie tyle zdefiniujemy iniekcję, która każdemy elementowi $2^{\mathbb{\mathbb{N}}}$ przyporządkowuje pewną bijekcję. Jeśli $f\in 2^{\mathbb{\mathbb{N}}}$, to bijekcja $f^{\prime }$ działa następująco:

$f^{\prime }(2n)=2n$ oraz $f^{\prime }(2n+1)=2n+1$ wtedy i tylko wtedy, kiedy $f(n)=0$

oraz

$f^{\prime }(2n)=2n+1$ oraz $f^{\prime }(2n+1)=2n$ wtedy i tylko wtedy, kiedy $f(n)=1$

Oczywiście $f$ jest bijekcją i bardzo prosto jest wykazać, że dla dwóch różnych funkcji otrzymujemy różne bijekcje, co dowodzi, że bijekcji tych jest continuum.

Ćwiczenie 4.9

Jakiej mocy jest zbiór porządków na $\mathbb{\mathbb{N}}$, które są równocześnie funkcjami $\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$?

Rozwiązanie

Zbiór ten jest jednoelementowy. Niewątpliwie funkcja identycznościowa jest porządkiem -- antyłańcuchem. Ustalmy dowolny, nieidentycznościowy porządek na $\mathbb{\mathbb{N}}$. Założenie gwarantuje, że porządek ten zawiera parę $(n,m)$, dla pewnego $n\ne m$. Równocześnie zwrotność gwarantuje, że zawiera on również parę $(n,n)$, co przeczy definicji funkcji.

Ćwiczenie 4.10

Dowolna rodzina $X\subset {𝒫}(\mathbb{\mathbb{N}})$ taka, że dla dowolnych dwóch różnych elementów $X$ ich przecięcie jest co najwyżej jednoelementowe, jest przeliczalna.

Rozwiązanie

Aby to wykazać, dzielimy rodzinę $X$ na dwie części: $X_1$ i $X^{\prime }$. Niech zbiór $X_1$ zawiera wszystkie zero i jednoelementowe elementy $X$ -- jest ich przeliczalnie wiele, bo każdy z nich jest podzbiorem $\mathbb{\mathbb{N}}$. Pozostaje wykazać, że $X^{\prime }$ jest przeliczalny i wtedy $X$ jako unia dwóch zbiorów przeliczalnych będzie również przeliczalny. Aby wykazać, że $X^{\prime }$ jest przeliczalny, ustawmy funkcję $f:X^{\prime }\to \mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}$ taką, że:

$f(x)=(n,m)$ jeśli $n$ jest najmniejszym elementem $x$, a $m$ jest najmniejszym w $x\setminus \{n\}$

Funkcja $f$ jest dobrze zdefiniowana i prowadzi w zbiór przeliczalny. Pozostaje wykazać, że $f$ jest iniekcją. Jeśli $f(x)=(n,m)=f(x^{\prime })$, to $x\cap x^{\prime }\supset \{n,m\}$, gdzie $n\ne m$. Wnioskujemy, że przecięcie $x$ i $x^{\prime }$ jest co najmniej dwuelementowe, czyli, że $x=x^{\prime }$ i funkcja $f$ jest iniekcją, co należało wykazać.