Zbiory przeliczalne

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

Definicja 2.1

Zbiór $\displaystyle X$ jest przeliczalny, gdy $\displaystyle X \sim_m N_0$ , dla pewnego $\displaystyle N_0 \subset \mathbb{N}$ .

Definicja 2.2

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

Twierdzenie 2.3

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

Dowód

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

Znowu, tak jak w przypadku Twierdzenia 1.8, radziłbym zapoznać sie z wykładem 11 "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady" 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 $\displaystyle X$ .

Twierdzenie 2.4

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

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

Ćwiczenie 2.5

Dowiedź Twierdzenia 2.4.

Wskazówka

Gdy

$\displaystyle X$ jest równoliczny ze skończonym zbiorem

$\displaystyle N_0$ to jest skończony, w przeciwnym wypadku zastosuj Twierdzenie 1.8.

Rozwiązanie

Jeśli zbiór

$\displaystyle X$ jest skończony (równoliczny z jakąś liczbą naturalną) lub równoliczny z

$\displaystyle \mathbb{N}$ , to niewątpliwie jest równoliczny z jakimś podzbiorem

$\displaystyle \mathbb{N}$ , czyli przeliczalny. Dla dowodu implikacji w drugą stronę załóżmy, że zbiór

$\displaystyle X$ jest przeliczalny, czyli, jak mówi definicja, równoliczny z jakimś podzbiorem

$\displaystyle \mathbb{N}$ . Jeśli ten podzbiór jest skończony, to na mocy przechodniości relacji równoliczności wnioskujemy, że zbiór

$\displaystyle X$ jest skończony. Jeśli ten podzbiór jest nieskończony, to Twierdzenie 1.8 gwarantuje, że jest on równoliczny z

$\displaystyle \mathbb{N}$ . Korzystając z przechodniości relacji równoliczności, wnioskujemy, że w tym przypadku

$\displaystyle X$ jest równoliczny z

$\displaystyle \mathbb{N}$ , co kończy dowód.

Lemat 2.6

Własności zbiorów przeliczalnych:

Podzbiór przeliczalnego zbioru jest przeliczalny.
Suma zbiorów przeliczalnych jest przeliczalna.
$\displaystyle \mathbb{N}^2$ jest przeliczalny.
Iloczyn kartezjański zbiorów przeliczalnych jest przeliczalny.
$\displaystyle \mathbb{N}^k$ dla $\displaystyle k\geq 1$ jest przeliczalny.
Niech $\displaystyle x \in \mathcal{P} ( \mathcal{P} (X))$ będzie skończoną rodziną zbiorów przeliczalnych. Wtedy $\displaystyle \prod x$ jest przeliczalny.
Jeżeli $\displaystyle X$ przeliczalny oraz $\displaystyle r \in \mathcal{P} ( \mathcal{P} (X))$ jest rozkładem, to $\displaystyle 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

$\displaystyle A$ i

$\displaystyle B$ są rozłączne. Mając dwie surjekcje

$\displaystyle f:\mathbb{N} \rightarrow A$ oraz

$\displaystyle g:\mathbb{N} \rightarrow B$ , zbuduj nową

$\displaystyle h: N \rightarrow A \cup B$ następująco:

$\displaystyle h(n) =\left\{\begin{array}{lll} f(n/2), & \textrm{ dla parzystego } \displaystyle n, \\ g((n-1)/2) , & \textrm{ dla nieparzystego } \displaystyle n. \end{array} \right.$

Dla zbiorów nierozłącznych rozważ

$\displaystyle A\cup B = A \cup (B \setminus A)$ .

3. Wykonaj obliczenia tak jak w ćwiczeniu 4.9 wykładu 6 (patrz wykład 6 "Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha", Ćwiczenie 4.9 ).

4. Prosta konsekwencja 3.

5. Dowód przy pomocy prostej indukcji na

$\displaystyle n$ i obserwacji 3 oraz 4.

6. Niech

$\displaystyle x = \{x_1, \ldots x_n\}$ , wtedy

$\displaystyle \prod x$ jest równoliczny z

$\displaystyle x_1 \times \ldots \times x_n$ , gdy zbiory

$\displaystyle 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 "Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha", Twierdzenie 6.2).

7. Ponieważ

$\displaystyle r$ jest rozkładem składa, się z niepustych

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

Rozwiązanie

Rozwiązania:

1. Ustalmy dowolny przeliczalny zbiór

$\displaystyle X$ i dowolny

$\displaystyle Y$ taki, że

$\displaystyle Y\subset X$ . Aby wykazać, że

$\displaystyle Y$ jest przeliczalny, wystarczy zawęzić bijekcję

$\displaystyle f:X \rightarrow N_0\subset \mathbb{N}$ do zbioru

$\displaystyle Y$ . Funkcja

$\displaystyle f \mid_Y$ jest bijekcją pomiędzy

$\displaystyle Y$ a pewnym podzbiorem

$\displaystyle N_0$ , świadcząc o przeliczalności

$\displaystyle Y$ .

2. Postępując jak w podpowiedzi, załóżmy, że zbiory

$\displaystyle A$ i

$\displaystyle B$ są rozłączne. Jeśli któryś ze zbiorów jest pusty, to teza jest trywialna. W przeciwnym przypadku mamy dwie surjekcje

$\displaystyle f:\mathbb{N} \rightarrow A$ oraz

$\displaystyle g:\mathbb{N} \rightarrow B$ . Definiujemy funkcję

$\displaystyle h: N \rightarrow A \cup B$ jako:

$\displaystyle h(n) = \left\{\begin{array}{lll} f(n/2), & \textrm{ dla parzystego } \displaystyle n, \\ g((n-1)/2) , & \textrm{ dla nieparzystego } \displaystyle n. \end {array} \right.$

Funkcja

$\displaystyle 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

$\displaystyle k$ i

$\displaystyle l$ mamy

$\displaystyle 2k\neq 2l+1$ ). Aby wykazać, że

$\displaystyle h$ jest surjekcją, ustalmy dowolny element

$\displaystyle a\in A$ . Ponieważ

$\displaystyle f$ jest surjekcją, istnieje

$\displaystyle n\in\mathbb{N}$ takie, że

$\displaystyle f(n)=a$ . Używając definicji

$\displaystyle h$ , dostajemy

$\displaystyle h(2n)=f(n)=a$ -- element

$\displaystyle a$ jest w obrazie funkcji

$\displaystyle h$ . Dla elementów zbioru

$\displaystyle B$ postępujemy podobnie, biorąc

$\displaystyle 2n+1$ zamiast

$\displaystyle 2n$ jako argument dla

$\displaystyle h$ . Wykazaliśmy, że funkcja

$\displaystyle h$ jest surjekcją, co kończy dowód.

Jeśli zbiory nie są rozłączne, to stosujemy powyższe rozumowanie do zbiorów

$\displaystyle A$ i

$\displaystyle B\setminus A$ . Zbiór

$\displaystyle A$ jest przeliczalny na mocy założenia, a zbiór

$\displaystyle B\setminus A$ na mocy założenia i poprzedniego podpunktu.

3. Ćwiczenie 4.9 z Wykładu 6: "Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha" gwarantuje istnienie iniekcji

$\displaystyle f$ z

$\displaystyle \mathbb{N}^2 \rightarrow \mathbb{N}$ . Funkcja

$\displaystyle g$ zdefiniowana jako:

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

jest poszukiwaną surjekcją. Funkcja

$\displaystyle g$ jest dobrze zdefiniowana, ponieważ

$\displaystyle f$ jest iniekcją i jest surjekcją, ponieważ

$\displaystyle f$ jest funkcją.

4. Dla dowodu kolejnego faktu ustalmy dwa niepuste (twierdzenie jest trywialne w przeciwnym przypadku) zbiory przeliczalne

$\displaystyle A$ i

$\displaystyle B$ i surjekcje

$\displaystyle f:\mathbb{N} \rightarrow A$ ,

$\displaystyle f':\mathbb{N} \rightarrow B$ . Niech

$\displaystyle g$ będzie funkcją zdefiniowaną w poprzednim podpunkcie, wtedy funkcja

$\displaystyle h:\mathbb{N} \rightarrow A\times B$ zdefiniowana jako :

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

jest poszukiwaną surjekcją. Funkcja

$\displaystyle h$ jest oczywiście dobrze zdefiniowana i jest surjekcją, ponieważ zarówno

$\displaystyle f,f'$ jak i

$\displaystyle g$ są surjekcjami.

5. Dowód jest indukcją na

$\displaystyle k$ :

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

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

jest surjekcją.

$\displaystyle h$ jest niewątpliwie dobrze zdefiniowaną funkcją. Aby wykazać surjektywność

$\displaystyle h$ , ustalmy dowolny element zbioru

$\displaystyle \mathbb{N}^{k+1}$ postaci

$\displaystyle (t,k)$ , gdzie

$\displaystyle k\in\mathbb{N}$ i

$\displaystyle t\in\mathbb{N}^k$ . Ponieważ

$\displaystyle f$ jest surjekcją istnieje

$\displaystyle m$ takie, że

$\displaystyle f(m) =k$ . Ponieważ

$\displaystyle g$ jest surjekcją, istnieje

$\displaystyle n$ takie, że

$\displaystyle g(n) = (m,k)$ . Trywialnie wtedy

$\displaystyle h(n) = (t,k)$ , co dowodzi, że

$\displaystyle h$ jest surjekcją.

6. Dowód przebiega indukcyjnie. Wykażemy, że dla każdej liczby naturalnej

$\displaystyle n$ , jeśli

$\displaystyle x\in\mathcal{P}(\mathcal{P}(X))$ i

$\displaystyle x \sim_m n$ i każdy element

$\displaystyle x$ jest przeliczalny, to

$\displaystyle \prod x$ jest przeliczalny:

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

$\displaystyle h(n) = (f(m),f'(k)),$ jeśli

$\displaystyle g(n) = (m,k).$

Rozumując podobnie jak w punkcie poprzednim, wykazujemy, że

$\displaystyle 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

$\displaystyle X$ i surjekcję

$\displaystyle f:\mathbb{N} \rightarrow X$ . Ustalmy

$\displaystyle r$ , dowolny podział

$\displaystyle X$ . Funkcja

$\displaystyle g:\mathbb{N} \rightarrow r$ zdefiniowana jako:

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

$\displaystyle f(n)\in s,$

będzie oczekiwaną surjekcją. Funkcja

$\displaystyle g$ jest dobrze zdefiniowana, ponieważ

$\displaystyle r$ jest podziałem i jest surjekcją, ponieważ każdy element

$\displaystyle r$ jest niepusty i

$\displaystyle 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 $\displaystyle \mathbb{Z} = \mathbb{N} \times \mathbb{N} / \approx$ oraz zbiór $\displaystyle \mathbb{Q} = \mathbb{Z} \times\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 $\displaystyle [0,1]$ nie jest przeliczalny. Cały zbiór $\displaystyle \mathbb{R}$ 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 $\displaystyle f: \mathbb{N} \rightarrow [0,1]$ . Zdefiniujemy indukcyjnie dwa ciągi punktów $\displaystyle a: \mathbb{N} \rightarrow [0,1]$ i $\displaystyle b: \mathbb{N} \rightarrow [0,1]$ odcinka $\displaystyle [0,1]$ o własności $\displaystyle a_i < b_i$ tak, aby $\displaystyle i$ -ty element ciągu $\displaystyle f$ nie należał do odcinka domkniętego $\displaystyle [a_{i+1} , b_{i+1}]$ . Tak więc kładziemy początkowo $\displaystyle a_0 =0$ i $\displaystyle b_0 =1$ . Przypuśćmy, że zdefiniowane są już obydwa ciągi, dla $\displaystyle i\leq n$ . Odcinek $\displaystyle [a_i,b_i]$ dzielimy na trzy równe części i za $\displaystyle a_{i+1}$ i $\displaystyle b_{i+1}$ wybieramy końce tego spośród nich, do którego nie należy element $\displaystyle f_i$ ciągu $\displaystyle f$ .

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

Ciąg $\displaystyle a$ jest słabo rosnący, czyli $\displaystyle a_i \leq a_{i+1}$ .
Ciąg $\displaystyle b$ jest słabo malejący, czyli $\displaystyle b_i \geq b_{i+1}$ .
$\displaystyle b_i - a_i = \frac{1}{3^i}$ .
$\displaystyle | b_{i+1} - b_i | \leq ( \frac{2}{3} )^i$ .
$\displaystyle | a_{i+1} - a_i | \leq ( \frac{2}{3} )^i$ .

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

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

Definicja 2.10

$\displaystyle A \leq_m B$ wtw istnieje iniekcja $\displaystyle f:A \to B$ .

$\displaystyle A < _m B$ wtw $\displaystyle A \leq_m B$ i nieprawda, że $\displaystyle A \sim_m B$ .

Twierdzenie 2.11

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

Dla dowolnych zbiorów $\displaystyle A,B$ zachodzi $\displaystyle A \leq_m B$ i $\displaystyle B \leq_m A$ , to $\displaystyle A \sim_m B$ .
Dla dowolnych zbiorów $\displaystyle A,B$ zachodzi $\displaystyle A \leq_m B$ i $\displaystyle B \subset A$ , to $\displaystyle A \sim_m B$ .
Dla dowolnych zbiorów $\displaystyle A,B,C$ zachodzi $\displaystyle A < _m B$ i $\displaystyle B < _m C$ , to $\displaystyle A < _m C$ .

Dowód

$\displaystyle (2) \hspace {0.1mm} \Rightarrow (1)$ . Niech $\displaystyle A \leq_m B$ i $\displaystyle B \leq_m A$ . Niech $\displaystyle f: B \to A$ iniekcja oraz niech $\displaystyle B_0 = \overrightarrow{f} (B)$ . Mamy więc $\displaystyle A \sim_m B_0$ oraz $\displaystyle B_0 \subset A$ . Stosując $\displaystyle (2)$ do $\displaystyle A, B_0$ , otrzymujemy $\displaystyle A \sim_m B_0$ , co wobec $\displaystyle B \sim_m B_0$ daje $\displaystyle A \sim_m B$ .

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

$\displaystyle (3) \hspace {0.1mm} \Rightarrow (2)$ . Niech $\displaystyle A \leq_m B$ i $\displaystyle B \subset A$ , co daje też $\displaystyle B \leq_m A$ . Gdyby nieprawdą było, że $\displaystyle A \sim_m B$ , to mielibyśmy zarówno $\displaystyle A < _m B$ jak i $\displaystyle B < _m A$ , co na mocy $\displaystyle (3)$ dawałoby sprzeczność $\displaystyle 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 $\displaystyle (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 $\displaystyle A \leq_m B$ i $\displaystyle B \leq_m A$ to $\displaystyle 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: "Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha"). Niech zatem $\displaystyle f:A\to B$ i $\displaystyle g: B\to A$ będą iniekcjami. Na mocy lematu Banacha (patrz wykład 6: "Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha", Lemat Banacha), istnieją rozłączne zbiory $\displaystyle A_1 ,A_2$ wzajemnie uzupełniające się do $\displaystyle A$ jak i rozłączne zbiory $\displaystyle B_1 ,B_2$ wzajemnie uzupełniające się do $\displaystyle B$ takie, że $\displaystyle \overrightarrow{f} (A_1) = B_1$ i symetrycznie $\displaystyle \overrightarrow{g} (B_2) = A_2$ . Możemy zatem na rozłącznych zbiorach $\displaystyle A_1, A_2$ skleić dwie iniekcje $\displaystyle f|_{A_1}$ i $\displaystyle g^{-1}|_{A_2}$ będące zawężeniami oryginalnych funkcji. Otrzymane sklejenie $\displaystyle 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 $\displaystyle x \notin x$ (patrz wykład 4: "Teoria mnogości ZFC. Operacje na zbiorach", 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]

$\displaystyle A < _m \mathcal{P} (A)$ .

Dowód

Łatwo zauważyć, że istnieje iniekcja wkładająca $\displaystyle A$ w $\displaystyle \mathcal{P} (A)$ . Przykładowo możemy wziąć funkcje przypisującą elementowi $\displaystyle x$ zbioru $\displaystyle A$ singleton $\displaystyle \{x\}$ . Załóżmy, że istnieje bijekcja $\displaystyle f: A \rightarrow \mathcal{P} (A)$ . Obrazami elementów ze zbioru $\displaystyle A$ są podzbiory $\displaystyle A$ . Utwórzmy zbiór $\displaystyle C= \{z\in A: z \notin f(z)\}$ . Ze względu na surjektywność $\displaystyle f$ musi istnieć taki element $\displaystyle z_0 \in A$ , że $\displaystyle f(z_0) = C$ . Rozstrzygnijmy problem, czy $\displaystyle z_0 \in f(z_0)$ . Jeżeli tak, to $\displaystyle z_0 \in C$ , a zatem $\displaystyle z_0 \notin f(z_0)$ sprzeczność. Jeżeli nie to, $\displaystyle z_0 \notin f(z_0)$ , a zatem $\displaystyle z_0 \in C$ , czyli $\displaystyle 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ę $\displaystyle A$ . W takim razie $\displaystyle \mathcal{P} (A) \subset A$ , bo każdy podzbiór $\displaystyle A$ jest zbiorem. Trywialnie mamy w drugą stronę $\displaystyle A \leq_m \mathcal{P} (A)$ . Zatem z twierdzenia Cantora-Bernsteina otrzymujemy $\displaystyle A \sim_m \mathcal{P} (A)$ , co jest sprzeczne z twierdzeniem Cantora.

Twierdzenie 2.15

Każdy zbiór nieskończony zawiera podzbiór przeliczalny równoliczny z $\displaystyle \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: "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady", Twierdzenie 4.1>).