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

Zawartość wykładu: 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ęcie 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ła teorie mocy można patrzeć jak na teorie bijekcji i iniekcji (lub dualnie surjekcji - patrz wykład 11, ćwiczenie 3.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

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

Udowodnij własności 1, 2, 3. z twierdzenia Uzupelnic thm:rownolicznosc2|.

Rozwiązanie

1. Oczywiste. Identyczność $1_A$ jest tego świadkiem.
2. Funkcja odwrotna do bijekcji jest bijekcja.
3. Składanie bijekcji jest bijekcją

Twierdzenie

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 Uzupelnic thm:rownolicznosc| podamy jako ćwiczenia.

Ćwiczenie

Dowiedź Twierdzenia Uzupelnic thm:rownolicznosc|

Wskazówka

1. Suma mnogościowa bijekcji działających na zbiorach

rozłącznych i mających rozłączne przeciwdziedziny jest bijekcją.

1. 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ą.

1. 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ą.

1. 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ą.

1. 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ą.

1. Zbiorowi $A$ przyporządkowujemy jego funkcje

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.

1. 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ć.

1. 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ść.

1. 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.

1. 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.

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

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ę

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle f'(x) = \begincases f(x)&\text{ jeśli } x\neq n\\ m&\text{ jeśli } x = n. \endcases }

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 (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

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 indukcje (twierdzenie 6.1 wykład 7) zbudujmy bijekcje $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 (twierdzenie 5.2 wykład 7) posiada element najmniejszy.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned h(0) &= \hbox{najmniejszy element w } N_0 \\ h(n') &= \hbox{najmniejszy element, który w } N_0Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle jest istotnie większy niż } h(n)Parser nie mógł rozpoznać (nieznana funkcja „\endaligned”): {\displaystyle \displaystyle } \endaligned}

Ł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.

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

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

Twierdzenie

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 Uzupelnic thm:nieskonczonyprzeliczalny|, radziłbym zapoznać sie z wykładem 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

$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

Dowiedź Twierdzenie Uzupelnic thm:przelicz|.

Wskazówka

Gdy $X$ jest równoliczny ze skończonym zbiorem $N_0$ to jest skończony, w przeciwnym wypadku zastosuj Twierdzenie Uzupelnic thm:nieskonczonyprzeliczalny|.

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 Uzupelnic thm:nieskonczonyprzeliczalny| 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

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.

1. ${\mathbb{\mathbb{N}}}^k$ dla $k\ge 1$ jest przeliczalny.
2. Niech $x\in {𝒫}({𝒫}(X))$ będzie

skończoną rodziną zbiorów przeliczalnych. Wtedy $\prod x$ jest przeliczalny.

1. 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

Dowiedź Lematu Uzupelnic lem:przelicz|.

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.

$h(n)=\{\begin{array}{ll}f(n/2),& \text{dla parzystego }n,\\ g((n-1)/2),& \text{dla nieparzystego }n\end{array}$

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

1. Wykonaj obliczenia tak jak w ćwiczeniu 4.9 wykładu 6.
2. Prosta konsekwencja 3.
3. Dowód przy pomocy prostej indukcji na $n$ i obserwacji 3 oraz 4.
4. 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.

1. 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

$h(n)=\{\begin{array}{ll}f(n/2),& \text{dla parzystego }n,\\ g((n-1)/2),& \text{dla nieparzystego }n\end{array}$

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.

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

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle g(n) = \begincases (m,k)&\text{ jeśli }f(m,k)=n \\ (0,0)&\text{ jeśli } n\notin\overrightarrow{f} (\mathbb{N}^2) \endcases }

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

1. 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.

1. 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ą.

1. 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.

1. 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

Zbiory liczb całkowitych i wymiernych są przeliczalne.

Dowód

Jest to prosta konsekwencja punktu 7 lematu Uzupelnic lem:przelicz|. 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

(Cantora) Zbiór liczb rzeczywistych nie jest przeliczalny.

Dowód

Podany poniżej dowód pochodzi od 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 z poś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 Cauchyego 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ą przeprowadzona 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.

.

$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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (2) \hspace*{0.1mm} \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$.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (1) \hspace*{0.1mm} \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$.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (3) \hspace*{0.1mm} \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 uzasadnienie wielu faktów teorii mocy, co bez tego twierdzenia często pociągało by konieczność przeprowadzania długich i skomplikowanych dowodów.

Twierdzenie

(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 rozdział 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. Niech zatem $f:A\to B$ i $g:B\to A$ będą iniekcjami. Na mocy lematu Banacha 7.8 z rozdziału 7 wykładu 6 istnieją rozłączne zbiory $A_1,A_2$ wzajemnie się uzupełniające się do $A$ jak i rozłączne zbiory $B_1,B_2$ wzajemnie się 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, rozdział 10, 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

(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

(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

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 twierdzenie w wykładzie 11, rozdział 4, twierdzenie 4.1 oraz o zapoznanie się z innymi faktami tego rozdziału, które wymagają aksjomatu wyboru.

Zbiory mocy kontinuum

Zbiór nazywamy nieprzeliczalnym gdy nie jest przeliczalny.

Ćwiczenie

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 Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle g(n) = \begincases 0& } jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f(n)(n) = 1 \\ 1& } jeśli Parser nie mógł rozpoznać (nieznana funkcja „\endcases”): {\displaystyle \displaystyle f(n)(n) =0. \endcases }

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

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle g(n) = \begincases f(n)& } jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \overrightarrow{f(n)} (\mathbb{N})\subset 2\\ z& } w przeciwnym przypadku Parser nie mógł rozpoznać (nieznana funkcja „\endcases”): {\displaystyle \displaystyle \endcases }

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.

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

Lemat

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 funkcje liniową

pomiędzy dwoma zadanymi otwartymi przedziałami.)

Lemat

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

Dowód

Prosta konsekwencja twierdzenia Cantora- Bernsteina Uzupelnic thm:Cantor-Bernstein|

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

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 Uzupelnic thm:Rnieprzelicz| o nieprzeliczalności $\mathbb{ℝ}$. W takim razie $A\setminus B$ jest nieskończony. Można zatem odnaleźć w nim na mocy twierdzenia Uzupelnic thm:nieskonczony| (stosując aksjomat wyboru, zapoznaj się z dowodem tego twierdzenie w wykładzie 11, rozdział 4, 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ć bijekcje $h:A\to A\setminus B$ następująco:

$h(x)=\{\begin{array}{ll}f(x),& x\in B\cup B^{\prime }\\ x,& x\notin B\cup B^{\prime }\end{array}$

Lemat

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 rozdziału 3 wykładu 8. 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 wykładu 8.

Twierdzenie

$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 w 3.18 (wykład 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 kontinuum i przeliczalnego na mocy lematu Uzupelnic lem:nadzbiorprzeliczalny| jest mocy kontinuum.

Twierdzenie

$\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ą kontinuum. Czyli, czy istnieje $A$ takie, że

$\mathbb{\mathbb{N}}{<}_{m}A{<}_m\mathbb{ℝ}$

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ą kontinuum. Hipoteza ta była intensywnie badana przez matematyków. W roku 1939 Kurt G{o}del pokazał niesprzeczność tej hipotezy z aksjomatami teorii mnogości. Można zatem przyjąć, że taki zbiór jak w Uzupelnic hipotezaKontinuum| 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 kontinuum 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 nie odwołującą się do pojęcia liczb naturalnych definicję nieskończoności.

(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

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 Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle f(m)=\begincases m& } jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle m\neq n-1\\ k& } jeśli Parser nie mógł rozpoznać (nieznana funkcja „\endcases”): {\displaystyle \displaystyle m = n-1. \endcases }

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 Twierdzenie 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$

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle h(x)=\begincases x& } jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle x\notin Y\\ f(n+1)& } jeśli Parser nie mógł rozpoznać (nieznana funkcja „\endcases”): {\displaystyle \displaystyle x=f(n)\in Y. \endcases }

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

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 Uzupelnic thm:Cantor-Bernstein| wnioskujemy, że ${\mathbb{ℝ}}^{\mathbb{ℝ}}{\sim }_m{2}^{\mathbb{ℝ}}$.

Ćwiczenie

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 Twierdzenia Uzupelnic thm:Cantor-Bernstein| gwarantuje żądaną równoliczność.

Ćwiczenie

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

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ównoliczne 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}}$ $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 Cantor-Bernstein gwarantuje, że funkcji tych jest dokładnie continuum.

Ćwiczenie

Czy na płaszczyźnie istniej 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

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

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 operować na zbiorze $\mathbb{\mathbb{N}}$ operować będzie na zbiorze mu równolicznym $\mathbb{\mathbb{Q}}$. Zwróćmy uwagę, że zdefiniowane w Ćwiczeniu Uzupelnic cw:wypukle| 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

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 Uzupelnic cw:rosnace| 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

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

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ć.