Kantorov diagonálny argument

Prvý Cantorov diagonálny argument

V nasledujúcom príklade sú použité dve najjednoduchšie nekonečné množiny, a to množina prirodzených čísel a množina kladných zlomkov. Cieľom je ukázať, že obe tieto množiny, N {\displaystyle \mathbb {N} } a Q + {\displaystyle \mathbb {Q^{+}} } majú rovnakú kardinalitu.

Najprv sa zlomky zarovnajú do poľa takto:

1 1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\\end{array}}

Potom sa spočítajú čísla, ako je znázornené na obrázku. Zlomky, ktoré sa dajú zjednodušiť, sa vynechajú:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{Farba {Polnočná modrá}\rightarrow }&{{tfrac {1}{4}}&{{Farba {Modrá}(6)}&&{{tfrac {1}{5}}\{{Farba {Modrá}(11)}&{{\color {MidnightBlue}\rightarrow }\&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{5}}&\cdots \{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&{{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\tfrac {5}{1}}&&{\color {Blue}(10)}&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}

Týmto spôsobom sa počítajú zlomky:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\end{array}}}

Vynechaním zlomkov, ktoré sa ešte dajú zjednodušiť, vznikne bijekcia, ktorá priradí každý prvok prirodzených čísel k jednému prvku zlomkov:

Aby sme ukázali, že všetky prirodzené čísla a zlomky majú rovnakú kardinalitu, je potrebné pridať prvok 0; za každý zlomok sa pridá jeho zápor;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}\cdots }\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}&\cdots \\\end{array}}}

Týmto spôsobom existuje úplná bijekcia, ktorá ku každému prirodzenému číslu priradí zlomok. Inými slovami: obe množiny majú rovnakú kardinalitu. Dnes sa množiny, ktoré majú rovnaký počet prvkov ako množina prirodzených čísel, nazývajú spočítateľné. Množiny, ktoré majú menej prvkov ako množina prirodzených čísel, sa nazývajú najviac spočítateľné. Podľa tejto definície je množina racionálnych čísel / zlomkov spočítateľná.

Nekonečné množiny majú často vlastnosti, ktoré sú v rozpore s intuíciou: David Hilbert to ukázal v experimente, ktorý sa nazýva Hilbertov paradox Grand Hotela.

Reálne čísla

Množina reálnych čísel nemá rovnakú kardinalitu ako množina prirodzených čísel; reálnych čísel je viac ako prirodzených čísel. Uvedená myšlienka ovplyvnila jeho dôkaz. Cantor vo svojom článku z roku 1891 uvažoval o množine T všetkých nekonečných postupností binárnych číslic (t. j. každá číslica je nula alebo jednotka).

Začína konštruktívnym dôkazom nasledujúcej vety:

Ak s₁ , s₂ , ... , s_n , ... je ľubovoľný výpočet prvkov z T, potom vždy existuje prvok s z T, ktorému nezodpovedá žiadny s_n vo výpočte.

Aby sme to dokázali, je daný výpočet prvkov z T, ako napr.

Postupnosť s sa zostrojí tak, že sa zvolí 1. číslica ako komplementárna k 1. číslici s₁ (zamení sa 0 za 1 a naopak), 2. číslica ako komplementárna k 2. číslici s₂ , 3. číslica ako komplementárna k 3. číslici s₃ a všeobecne pre každé n sa zvolí n^th číslica ako komplementárna k n^th číslici s_n . V príklade to dáva:

Podľa konštrukcie sa s líši od každého s_n , pretože ich n^th číslice sa líšia (zvýraznené v príklade). Preto sa s nemôže vyskytovať vo výčte.

Na základe tejto vety potom Cantor pomocou dôkazu protirečením dokázal, že:

Množina T je nepočítateľná.

Predpokladá, že T bolo spočítateľné. V tom prípade by sa všetky jeho prvky dali zapísať ako výpočet s₁ , s₂ , ... , s_n , ... . Aplikovaním predchádzajúcej vety na tento výpočet by vznikla postupnosť s, ktorá do výpočtu nepatrí. Avšak s bol prvkom T, a preto by mal byť vo výčte. To je v rozpore s pôvodným predpokladom, takže T musí byť nepočítateľné.