Informatyka MIMUW

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