$|\mathbb N| \le |\mathcal P(\mathbb N)|$ a $|\mathbb R\setminus\mathbb N|=|\mathbb R|$

[Martin Sleziak]

$\newcommand{\abs}[1]{|#1|}\newcommand{\N}{\mathbb N}\newcommand{\R}{\mathbb R}\newcommand{\alnul}{\aleph_0}\newcommand{\sm}{\setminus}$
Dokážte, nasledujúce tvrdenia -- pričom je povolené používať len veci, ktoré už boli na prednáške. (Definície, vlastnosti rovnosti a nerovnosti, Cantor--Bernsteinova veta, $\ldots$ T.j. skúsiť to bez použitia vecí, ktoré v texte dokázané sú napríklad o súčte kardinálnych čísel.) Vlastne celý tento dlhý pokec smeruje najmä k tomu, že by ste to mali skúsiť bez použitia výsledku, že platí: $\abs{A}\ge\alnul$ $\Rightarrow$ $\abs{A}+\alnul=\abs{A}$. (Takýto fakt zanedlho dokážeme, keď sa začneme zaoberať vlastnosťami súčtu kardinálnych čísel.)
a) $\abs{\R\sm\N}=\abs{\R}$;
b) $\abs{\N}\le\abs{\mathcal P(\N)}$

Napíšem sem stručne niečo k týmto dvom úlohám.

K úlohe o $\abs{\R\sm\N}=\abs{\R}$ mám niečo aj v starších topicoch:
viewtopic.php?t=543
viewtopic.php?t=360
viewtopic.php?t=132
Vtedy ale bola táto úloha zadaná už po dôkaze toho, že z $\abs A\ge\alnul$ vyplýva $\abs A+\alnul=\abs A$.
Ak poznáme toto tvrdenie, tak stačí skontrolovať, že $\abs{\R\sm\N}\ge\alnul$. (Napríklad si môžeme všimnúť, že $n\mapsto n+\frac12$ je injekcia $\N\to\R$.) A potom už máme:
$$\abs{\R\sm\N}=\abs{R\sm\N}+\alnul=\abs{R\sm\N}+\abs{\N}=\abs{\R}.$$

Tu sme chceli dôkaz bez použitia tohto výsledku. Asi najprirodzenejší spôsob je použiť Cantor-Bernsteinovu vetu.
Máme nerovnosť $\abs{\R\sm\N}\le\abs{\N}$, lebo $\R\sm\N \subseteq \R$.
Takže už stačí nejako vymyslieť zdôvodnenie nerovnosti $$\abs{\R} \le \abs{\R\sm\N}.$$
Na to by nám stačila injekcia $\R\to\R\sm\N$.
Takýchto injekcií môžeme vymyslieť veľa.
Napríklad:

• Funkcia $f(x)=-e^x$ nadobúda iba záporné hodnoty, je to injekcia $\R\mapsto\R\sm\N$.
• Môžeme zobrať ľubovoľnú reálnu funkciu, ktorá nadobúda iba hodnoty z intervalu $(0,1)$ a je injektívna. Takých funkcií vieme vymyslieť viacero. A vrátime sa k nim aj na hodine, keď budeme chcieť zdôvodniť, že $\abs{R}=\abs{(0,1)}$.

Niektorí z vás ste použili aj argumenty, ktoré pripomínajú to, ako sme robili dôkaz spomenutého tvrdenia alebo sa iným spôsobom podobajú na Hilbertov hotel: viewtopic.php?t=467

Napríklad môžeme dostať bijekciu $g\colon \R\to\R\sm\N$ tak, že
\begin{align*}
g(n)&=n+\frac12;\text{ pre }n\in\N\\
g\left(n+\frac1{2^{k+1}}\right)&=n+\frac1{2^{k+2}};\text{ pre }n,k\in\N\\
g(x)&=x\text{ ak $x$ má iný tvar}
\end{align*}
Inak povedané, posúvali sme niektoré čísla podľa takejto schémy: $n\mapsto n+\frac12 \mapsto n+\frac14 \mapsto n+\frac18 \mapsto \dots$
A ostatné čísla sme nechali na mieste.
(V reči nekonečného hotela: Ak sa hostia na týchto miestach posunú, vedeli sme pridať ako hosťa $n$.)

A ak by sme použili podobný argument ak v dôkaze spomenutého tvrdenia, tak si okrem $\N$ ešte vezmeme jednu rovnako veľkú množinu, napríklad $B=\{n+\frac12; n\in\N\}$.
Skúsime vyrobiť bijekciu $\N\cup B\to B$ (rovnakým spôsobom ako v dôkaze $\alnul+\alnul=\alnul$).
A potom z nej urobíme bijekciu $\R\mapsto \R\sm\N$.

[Martin Sleziak]

$\newcommand{\abs}[1]{|#1|}\newcommand{\N}{\mathbb N}\newcommand{\R}{\mathbb R}\newcommand{\alnul}{\aleph_0}\newcommand{\sm}{\setminus}$Pýtal som sa na zdôvodnenie, že $\abs{\N}\le\abs{\mathcal P(\N)}$.
A takmer rovnako vieme dostať, že $\abs{X}\le\abs{\mathcal P(X)}$ pre ľubovoľnú množinu $X$.
Stačí si všimnúť, že zobrazenie
\begin{gather*}
f\colon X \to \mathcal P(X)\\
f\colon x \mapsto \{x\}
\end{gather*}
je injektívne.

Viacerí z vás ste napísali aj to, že platí $\abs X < \abs{\mathcal P(X)}$. (V špeciálnom prípade $X=\N$; ale opäť je to tak, že rovnaký argument prejde pre ľubovoľnú množinu.)
To je o dosť silnejšie tvrdenie než to, na čo som sa písal v zadaní. (Ale určite nie je na škodu, že ste sa na takéto niečo pozreli.)

Ukážeme si to neskôr aj na prednáške, tento výsledok sa volá Cantorova veta.
A argument použitý v dôkaze je Cantorov diagonálny argument.

[Martin Sleziak]

Komentáre k niektorým riešeniam$\newcommand{\abs}[1]{|#1|}\newcommand{\N}{\mathbb N}\newcommand{\R}{\mathbb R}\newcommand{\alnul}{\aleph_0}\newcommand{\sm}{\setminus}$

Funkcia $n\mapsto 2^n$
Viacerí ste v súvislosti s úlohou o $\abs{\N}\le\abs{\mathcal P(\N)}$ spomínali funkciu $$f\colon n\mapsto 2^n.$$
Táto funkcie je injektívna funkcia $\mathbb N\to\mathbb N$. Čiže takáto funkcia by nám povedali iba toľko, že $\abs{\N}\le\abs{\N}$; čo je fakt, ktorý vieme zdôvodniť aj jednoduchšie.
Je pravda, že sa vlastne snažíme ukázať $\alnul\le 2^{\alnul}$; toto je pravdepodobne dôvod, prečo vám napadla takáto funkcia. A dá sa pozerať na túto úlohu tak, že dokazujeme pre $\alnul$ analógiu tvrdenia $n\le2^n$, ktoré platí pre prirodzené čísla.
Ale nie je to funkcia z $\N$ do $\mathcal P(\N)$ ani z $\N$ do $\{0,1\}^{\N}$; v tejto úlohe by sme potrebovali niečo zhruba takéto.

Spojité zobrazenia a veta o strednej hodnote

Niektorí z vás ste sa snažili nájsť injekciu $\R\to\R\sm\N$ predpismi ako napríklad $g(x)=x+\pi$ alebo $h(x)=\frac\pi{x}$ (a $h(0)=0$); prípadne namiesto $\pi$ bolo nejaké iné iracionálne číslo alebo nejaká iná podobná funkcia.
Pravdepodobne k niečomu takémuto trochu mohlo zvádzať, že pre racionálne $x$ naozaj nedostaneme nikdy ako funkčnú hodnotu racionálne číslo. Treba ale nezabúdať aj na to, že ako vstupy môžu byť aj iracionálne čísla.

Napríklad ľahko vidíme, že $g(1-\pi)=1$ alebo $h(\pi)=1$.
V oboch spomenutých prípadoch vieme, ako vyzerá graf funkcie.
Graf funkcie $g(x)=x+\pi$ je priamka, ktorá nie je horizonálna. Teda ako funkčné hodnoty nadobúda všetky reálne čísla.
Funkcia $h(x)=\frac\pi{x}$ pre $x>0$ nadobudne ako funkčené hodnoty všetky kladné reálne čísla.

Z analýzy poznáte vetu o strednej hodnote, čiže viete, že ak spojité zobrazenie nadobúda nejaké dve hodnoty, tak nadobúda aj všetky hodnoty medzi nimi. (Možno ste takéto niečo stretli aj pod názvom Darbouxova vlastnosť alebo darbouxovská funkcia.)
Dve funkcie, ktoré sme spomenuli vyššie, sú spojité na $(0,\infty)$ a nadobúdajú tu hodnoty nad aj pod číslom $1$, teda existuje aj $x$ také, že $h(x)=1$.

Z toho by malo byť jasné aj to, že ak chceme vymyslieť predpis injekcie $\R\to\R\sm\N$, ktorá bude spojitá, tak nám to dáva nejaké obmedzenia na to, ako to môžeme robiť.
Napríklad by sme mohli skúšať nejakú spojitú funkciu, kde všetky funkčné hodnoty budú v intervale $(3,4)$; ale nemôžeme mať súčasne nejaké hodnoty z intervalov $(3,4)$ aj $(4,5)$.
Alebo môžeme skúšať nejakú spojitú funkciu, ktorá bude mať všetky hodnoty záporné. Ale ak sa nadobúdajú aj kladné aj záporné hodnoty, tak spojitá funkcie určite niekde neadobudne aj hodnotu nula.

Samozrejme, na riešenie tejto úlohy nám stačí nájsť nejakú injekciu - nemusí byť nutne spojitá. Keďže ale v riešeniach (či už správnych alebo nesprávnych) sa vyskytovali často spojité funkcie, zdalo sa mi rozumné pridať takúto poznámku.