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