Cantorův diagonální argument

Následující příklad využívá dvě nejjednodušší nekonečné množiny, a to množinu přirozených čísel a množinu kladných zlomků. Cílem je ukázat, že obě tyto množiny, N {\displaystyle \mathbb {N} } a Q + {\displaystyle \mathbb {Q^{+}} } mají stejnou kardinalitu.

Nejprve se zlomky seřadí do pole 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 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccc}{\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}}}

Poté se čísla spočítají, jak je znázorněno na obrázku. Zlomky, které lze zjednodušit, se 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)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(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}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\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 způsobem se 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}{\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}}}

Vynecháním zlomků, které lze ještě zjednodušit, vznikne bijekce, která přiřadí každý prvek přirozených čísel k jednomu prvku zlomků:

Abychom ukázali, že všechna přirozená čísla a zlomky mají stejnou kardinalitu, je třeba přidat prvek 0; za každý zlomek se přidá 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}{\ccccccccccccccccc}{\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 }&{\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 způsobem existuje úplná bijekce, která ke každému přirozenému číslu přiřazuje zlomek. Jinými slovy: obě množiny mají stejnou kardinalitu. Dnes se množiny, které mají stejný počet prvků jako množina přirozených čísel, nazývají spočetné. Množiny, které mají méně prvků než množina přirozených čísel, se nazývají nejvýše spočetné. S touto definicí je množina racionálních čísel / zlomků spočetná.

Nekonečné množiny mají často vlastnosti, které jsou v rozporu s intuicí: David Hilbert to ukázal v experimentu, který se nazývá Hilbertův paradox Grand Hotelu.

Množina reálných čísel nemá stejnou kardinalitu jako množina přirozených čísel; reálných čísel je více než přirozených. Výše uvedená myšlenka ovlivnila jeho důkaz. Ve svém článku z roku 1891 se Cantor zabýval množinou T všech nekonečných posloupností binárních číslic (tj. každá číslice je nula nebo jednička).

Začíná konstruktivním důkazem následující věty:

Jestliže s₁ , s₂ , ... , s_n , ... je libovolný výčet prvků z T, pak vždy existuje prvek s z T, kterému ve výčtu neodpovídá žádný s_n .

To dokážeme tak, že zadáme výčet prvků z T, jako např.

Posloupnost s sestrojíme tak, že 1. číslici zvolíme jako komplementární k 1. číslici s₁ (zaměňujeme 0 za 1 a naopak), 2. číslici jako komplementární k 2. číslici s₂ , 3. číslici jako komplementární k 3. číslici s₃ a obecně pro každé n číslici n^th jako komplementární k číslici n^th s_n . V příkladu tak získáme:

Podle konstrukce se s liší od každého s_n , protože se liší jejich n^th číslic (v příkladu zvýrazněno). Proto se s nemůže ve výčtu vyskytovat.

Na základě této věty pak Cantor pomocí důkazu kontradikcí dokazuje, že:

Množina T je nepočetná.

Předpokládá, že T je spočetné. V takovém případě by se všechny jeho prvky daly zapsat jako výčet s₁ , s₂ , ... , s_n , ... . Aplikací předchozí věty na tento výčet by vznikla posloupnost s, která do výčtu nepatří. Nicméně s byl prvkem T, a proto by měl být ve výčtu. To je v rozporu s původním předpokladem, takže T musí být nepočetné.