Cantorova diagonální metoda

Cantorova diagonální metoda je matematický důkaz, pomocí kterého Georg Cantor ukázal, že množina všech reálných čísel je nespočetná.

Diagonální metoda nebyla prvním důkazem, který Cantor použil k dokázání tohoto faktu, byla publikována až tři roky po prvním důkazu. Na druhou stranu je ale oproti tomuto důkazu mnohem známější, navíc od prvního publikování byla podobná metoda použita pro dokázání mnoha dalších vět (například problém zastavení).

Důkaz

Cantorův důkaz ukazuje, že interval (0,1) není spočetný.

Důkaz sporem je veden takto:

1. Předpokládejme, že interval (0,1) je spočetně nekonečný.
2. Můžeme tedy „zapsat“ všechna čísla z tohoto intervalu do posloupnosti (r₁, r₂, r₃, …)
3. Každé z těchto čísel lze zapsat v desetinném rozvoji.
4. Seřadíme tato čísla (nemusí být seřazena v přirozeném uspořadání). Teď už předpokládáme, že jsou v posloupnosti obsažená a očíslovaná všechna čísla intervalu (0,1). Názorná ukázka naší posloupnosti může vypadat třeba takto (tato čísla nejsou součástí důkazu):

   r₁ = 0 , 5 1 0 5 1 1 0 …

   r₂ = 0 , 4 1 3 2 0 4 3 …

   r₃ = 0 , 8 2 4 5 0 2 6 …

   r₄ = 0 , 2 3 3 0 1 2 6 …

   r₅ = 0 , 4 1 0 7 2 4 6 …

   r₆ = 0 , 9 9 3 7 8 3 8 …

   r₇ = 0 , 0 1 0 5 1 3 5 …

   …

5. Sestrojíme reálné číslo x ležící v intervalu (0,1) tak, že pro k-tou číslici v jeho desetinném rozvoji vezmeme v úvahu k-tou číslici v desetinném rozvoji r_k. V posloupnosti z naší názorné ukázky jsou zvýrazněny číslice, které bereme v úvahu (abychom ukázali, proč se důkaz nazývá diagonální metoda).

   r₁ = 0 , 5 1 0 5 1 1 0 …

   r₂ = 0 , 4 1 3 2 0 4 3 …

   r₃ = 0 , 8 2 4 5 0 2 6 …

   r₄ = 0 , 2 3 3 0 1 2 6 …

   r₅ = 0 , 4 1 0 7 2 4 6 …

   r₆ = 0 , 9 9 3 7 8 3 8 …

   r₇ = 0 , 0 1 0 5 1 3 5 …

   …

6. Z těchto číslic definujeme číslice čísla x následovně:
   • pokud je na k-tém místě v r_k číslice α ∈ {0,1,2,3,4,5,6,7,8,9} pak na k-tém místě v x bude číslice β = 9 - α

   zjednodušeně např.:

   pokud je na k-tém místě v r_k číslice 5, pak na k-tém místě v x bude 4,

   pokud je na k-tém místě v r_k číslice 2, pak na k-tém místě v x bude 7.

7. Číslo x je zřejmě reálné (jelikož všechny desetinné rozvoje reprezentují reálné číslo) z intervalu (0,1). V naší názorné ukázce posloupnosti by x vypadalo takto:

   x = 0 , 4 8 5 9 7 6 4 …

8. Musí tedy existovat r_n = x pro nějaké n, jelikož jsme předpokládali, že v posloupnosti (r₁, r₂, r₃, …) jsou všechna reálná čísla z intervalu (0, 1).
9. Ale díky našemu způsobu sestrojování čísla x se x liší od každého r_n na n-tém místě desetinného rozvoje, tedy x neleží v posloupnosti (r₁, r₂, r₃, …)
10. Tato posloupnost tedy není posloupností všech reálných čísel z intervalu [0,1], docházíme ke sporu.
11. Odtud plyne, že předpoklad, že interval (0,1) je spočetný, musí být špatný.