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

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

Dowody poszczególnych punktów

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

2. Niech \( \displaystyle f:A \rightarrow B \) i \( \displaystyle g: C \rightarrow D \) będą bijekcjami. Rozważmy funkcję \( \displaystyle \Phi: A^C \rightarrow B^D \) zdefiniowaną, dla dowolnego \( \displaystyle \alpha\in A^C \) jako

\( \displaystyle \Phi ( \alpha ) = f \circ \alpha \circ g^{-1}. \)

Wykażemy, że \( \displaystyle \Phi \) jest bijekcją. Dla surjektywności ustalmy dowolną funkcję \( \displaystyle \beta\in B^D \), wtedy \( \displaystyle f^{-1} \circ \beta \circ g\in A^C \) i oczywiście \( \displaystyle \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 \( \displaystyle \Phi \) jest iniekcją. Ustalmy \( \displaystyle \alpha \) i \( \displaystyle \alpha' \) w \( \displaystyle A^C \) takie, że \( \displaystyle \Phi(\alpha) = \Phi(\alpha') \). Wtedy \( \displaystyle f \circ \alpha \circ g^{-1} =f \circ \alpha' \circ g^{-1} \) i obkładając obie strony równości przez \( \displaystyle f^{-1} \) z lewej strony i \( \displaystyle g \) z prawej otrzymujemy \( \displaystyle \alpha = \alpha' \), co dowodzi, że \( \displaystyle \Phi \) jest iniekcją. Dowód jest zakończony.

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

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

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

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

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

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

• Jeśli \( \displaystyle n=0=\emptyset \), 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 \( \displaystyle n \) jest równoliczny z jakąś liczbą naturalną. Rozważmy \( \displaystyle n+1 \) i dowolne \( \displaystyle B\subset n+1 \). Jeśli \( \displaystyle n\notin B \), to \( \displaystyle B \) jest równoliczny z jakąś liczbą naturalną na mocy założenia indukcyjnego. Jeśli \( \displaystyle n\in B \), rozważmy \( \displaystyle B\setminus\{n\} \) -- jest to zbiór, do którego można zastosować założenie indukcyjne i otrzymać liczbę naturalną \( \displaystyle m \) oraz bijekcję \( \displaystyle f \) pomiędzy \( \displaystyle B\setminus\{n\} \) a \( \displaystyle m \). Wtedy zbiór \( \displaystyle B \) jest równoliczny z \( \displaystyle m+1 \) poprzez bijekcję:

\( \displaystyle f'(x) = \begin{cases} f(x), & \mbox{ jeśli } x\neq n, \\ m, & \mbox{ jeśli } x = n.\end{cases} \) 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 \( \displaystyle A \) i funkcję \( \displaystyle f:A \rightarrow B \). Ponieważ \( \displaystyle A \) jest skończony, istnieje liczba naturalna \( \displaystyle n \) i bijekcja \( \displaystyle g \) pomiędzy \( \displaystyle n \) i \( \displaystyle A \). Możemy założyć, że \( \displaystyle \overrightarrow{f} (A)=B \). Definiujemy funkcję \( \displaystyle h:B \rightarrow A \) jako \( \displaystyle h(b) =\bigcap \overrightarrow{(f\circ g)}^{-1} (\{b\}) \) -- funkcję, która dla dowolnego elementu \( \displaystyle b\in B \) zwraca najmniejszą liczbę naturalną w \( \displaystyle n \), która jest przekształcana przez \( \displaystyle g \) w \( \displaystyle \overrightarrow{f}^{-1} (\{b\}) \). Otrzymaliśmy bijekcję pomiędzy \( \displaystyle B \) a pewnym podzbiorem liczby naturalnej. Korzystając z poprzedniego punktu i z przechodniości relacji równoliczności, wnioskujemy, że \( \displaystyle B \) jest skończony.

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

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.

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

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

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

\( \displaystyle g(n) = \begin{cases} 0, & \mbox{ jeśli }\displaystyle f(n)(n) = 1, \\ 1, & \mbox{ jeśli }\displaystyle f(n)(n) =0.\end{cases} \)

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

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

\( \displaystyle g(n) = \begin{cases} f(n), & \mbox{ jeśli } \overrightarrow{f(n)} (\mathbb{N})\subset 2, \\ z, & \mbox { w przeciwnym przypadku, } \displaystyle \end{cases} \)

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

Użyj aksjomatu wyboru.

Skorzystaj z wykładu 11 "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady" Twierdzenie 4.1.

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 \( \displaystyle n \) usuniemy dowolny element, to zbiór powstały będzie równoliczny z \( \displaystyle n-1 \). Usuńmy dowolny element z \( \displaystyle n \). Jeśli usunęliśmy \( \displaystyle n-1 \), to otrzymujemy liczbę \( \displaystyle n-1 \). Jeśli usunęliśmy \( \displaystyle k\neq n-1 \), to możemy zdefiniować bijekcję pomiędzy \( \displaystyle n\setminus\{k\} \) a \( \displaystyle n-1 \) poprzez:

\( \displaystyle f(m)= \begin{cases} m, & \mbox{ jeśli }\displaystyle m\neq n-1, \\ k, & \mbox{ jeśli }\displaystyle m = n-1.\end{cases} \)

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

Dla dowodu implikacji w drugą stronę wykorzystamy "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady" Twierdzenia 4.1 z Wykładu 11. Mówi ono, że dla każdego nieskończonego zbioru istnieje iniekcja z \( \displaystyle \mathbb{N} \) w ten zbiór. Ustalmy dowolny nieskończony zbiór \( \displaystyle X \) i taką iniekcję \( \displaystyle f:\mathbb{N} \rightarrow X \). Niech \( \displaystyle Y\subset X \) będzie obrazem \( \displaystyle \mathbb{N} \) względem \( \displaystyle f \) tak, że \( \displaystyle f:\mathbb{N}\rightarrow Y \) jest bijekcją. Zdefiniujmy funkcję \( \displaystyle g:X \rightarrow X \):

\( \displaystyle h(x) =\left\{\begin{array}{lll} x & \mbox{ jeśli }\displaystyle x\notin Y \\ f(n+1) & \mbox{ jeśli }\displaystyle x=f(n)\in Y. \end{array} \right. \)

Jak łatwo sprawdzić funkcja \( \displaystyle h:X \rightarrow X\setminus\{f(0)\} \) jest bijekcją, co dowodzi, że zbiór \( \displaystyle 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.

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

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

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

Przykłady funkcji silnie rosnących ze skończoną lub równoliczną \( \displaystyle \mathbb{N} \) liczbą punktów nieciągłości są trywialne. Aby wykazać, że dowolna, silnie rosnąca funkcja \( \displaystyle f:\mathbb{R} \rightarrow \mathbb{R} \) 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 \( \displaystyle \mathbb{Q} \). Ustalmy punkt nieciągłości \( \displaystyle a \). Wtedy \( \displaystyle \lim_{x\to a^-}f(x) \) istnieje, ponieważ funkcja jest rosnąca i ograniczona z góry (przez np. \( \displaystyle f(a+1) \)). Podobnie istnieje \( \displaystyle \lim_{x\to a^+}f(x) \). Ponieważ \( \displaystyle a \) jest punktem nieciągłości mamy \( \displaystyle \lim_{x\to a^-}f(x) < \lim_{x\to a^+}f(x) \). Ponieważ \( \displaystyle \mathbb{Q} \) jest gęste w \( \displaystyle \mathbb{R} \) istnieje \( \displaystyle r_a\in\mathbb{Q} \) takie, że \( \displaystyle \lim_{x\to a^-}f(x) < r_a < \lim_{x\to a^+}f(x) \). Pozostaje wykazać, że dla dwóch punktów nieciągłości \( \displaystyle a \) i \( \displaystyle b \), jeśli \( \displaystyle a\neq b \), to \( \displaystyle r_a\neq r_b \). Ponieważ porządek na \( \displaystyle \mathbb{R} \) jest porządkiem liniowym, mamy \( \displaystyle a < b \) lub \( \displaystyle b < a \). Możemy, bez straty ogólności, założyć ten pierwszy przypadek i znaleźć \( \displaystyle c\in\mathbb{R} \) takie, że \( \displaystyle a < c < b \). Wtedy \( \displaystyle r_a < \lim_{x\to a^+}f(x) < f(c) < \lim_{x\to b^-}f(x) < r_b \), co dowodzi, że funkcja \( \displaystyle a\mapsto r_a \) jest iniekcją, jak twierdziliśmy.

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

\( \displaystyle f'(n) = 2n + f(n). \)

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

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 \( \displaystyle (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 \( \displaystyle \mathbb{R} \) w \( \displaystyle \mathbb{Q}\times\mathbb{Q} \), dowodząc, że \( \displaystyle \mathbb{R} \) 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ą.

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

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

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

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 \( \displaystyle 2^{\mathbb{N}} \) przyporządkowuje pewną bijekcję. Jeśli \( \displaystyle f\in 2^{\mathbb{N}} \), to bijekcja \( \displaystyle f' \) działa następująco:

\( \displaystyle f'(2n) = 2n \) oraz \( \displaystyle f'(2n+1) = 2n+1 \) wtedy i tylko wtedy, kiedy \( \displaystyle f(n)=0 \)

oraz

\( \displaystyle f'(2n) = 2n+1 \) oraz \( \displaystyle f'(2n+1) = 2n \) wtedy i tylko wtedy, kiedy \( \displaystyle f(n)=1. \)

Oczywiście \( \displaystyle 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.

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

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

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

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