Cantorova diagonálna metóda

Cantorova diagonálna metóda je matematický dôkaz, pomocou ktorého Georg Cantor dokázal, že množina všetkých reálnych čísel je nespočítateľná.

Diagonálna metóda nebola prvým dôkazom, ktorý Cantor použil k dokázaniu tohto faktu, bola publikovaná tri roky po prvom dôkaze. Na druhej strane je oproti pôvodnému dôkazu oveľa známejšia, navyše bol princíp metódy použitý na dokázanie mnohých ďalších viet (napríklad problém zastavenia).

Dôkaz 
Cantorov dôkaz ukazuje, že interval [0,1] nie je spočítateľný.

Dôkaz sporom:

 Predpokladajme, že interval [0,1] je spočítatelne nekonečný.
 Môžeme teda „zapísat“ všetky čísla do postupnosti (r1, r2, r3, …)
 Každé z týchto čísel možno zapísať v desatinnom rozvoji.
 Zoraďme tieto čísla (nemusia byť zoradené v prirodzenom usporiadaní). Predpokladajme napríklad, že začiatok nášho zoznamu vyzerá takto:
 r1 = 0 , 5 1 0 5 1 1 0 …
 r2 = 0 , 4 1 3 2 0 4 3 …
 r3 = 0 , 8 2 4 5 0 2 6 …
 r4 = 0 , 2 3 3 0 1 2 6 …
 r5 = 0 , 4 1 0 7 2 4 6 …
 r6 = 0 , 9 9 3 7 8 3 8 …
 r7 = 0 , 0 1 0 5 1 3 5 …
 …
 Zostrojme reálne číslo x ležiace v intervale [0,1] tak, že pre k-tú číslicu v jeho desatinnom rozvoji vezmeme do úvahy k-tú číslicu v desatinnom rozvoji rk. Číslice, ktoré berieme do úvahy, sú v následujúcej postupnosti zvýraznené (aby bolo vidno, prečo sa dôkaz nazýva diagonálna metóda).
 r1 = 0 , 5 1 0 5 1 1 0 …
 r2 = 0 , 4 1 3 2 0 4 3 …
 r3 = 0 , 8 2 4 5 0 2 6 …
 r4 = 0 , 2 3 3 0 1 2 6 …
 r5 = 0 , 4 1 0 7 2 4 6 …
 r6 = 0 , 9 9 3 7 8 3 8 …
 r7 = 0 , 0 1 0 5 1 3 5 …
 …
 Z týchto číslic definujeme číslice čísla  x nasledovne:
 pokiaľ je na k-tom mieste v rk číslica α ∈ {0,1,2,3,4,5,6,7,8,9} potom na k-tom mieste v x bude číslica β ∈ ({0,1,2,3,4,5,6,7,8,9} - {α})
 zjednodušene napr.:
 pokiaľ je na k-tom mieste v rk číslica 5 potom na k-tom mieste v x bude 4,
 pokiaľ nie je na k-tom mieste v rk číslica 5 potom na k-tom mieste v x bude 5.
 Číslo x je zjavne reálne (keďže všetky desatinné rozvoje reprezentujú reálne číslo) z intervalu [0,1]. Napríklad pre hore uvedenú postupnosť by x vyzeralo takto:
 x = 0 , 4 5 5 5 5 5 4 …
 Musí teda existovať rn = x pre nejaké n, keďže sme predpokladali, že v postupnosti (r1, r2, r3, …) sú všetky reálne čísla z intervalu [0, 1].
 Ale vďaka spôsobu zostrojenia čísla x sa x líši od každého rn na n-tom desatinnom mieste, teda x neleží v postupnosti (r1, r2, r3, …)
 Táto sekvencia teda nie je sekvenciou všetkých reálných čísel z intervalu [0,1], dochádzame k sporu.
 Z toho vyplýva, že predpoklad, že interval [0,1] je spočítateľný, je nepravdivý.

Zdroj 

Teória množín
Matematické vety