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:
- Předpokládejme, že interval [0,1] je spočetně nekonečný.
- Můžeme tedy „zapsat“ všechna čísla do posloupnosti (r1, r2, r3, …)
- Každé z těchto čísel lze zapsat v desetinném rozvoji.
- Seřadíme tato čísla (nemusí být seřazena v přirozeném uspořadání). Předpokládejme například, že počátek našeho seznamu vypadá 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 …
- …
- Sestrojíme reálné číslo x ležící v intervalu [0,1] tak, že pro k-té číslo v jeho desetinném rozvoji vezmeme v úvahu k-té číslo v desetinném rozvoji rk. Číslice, které bereme v úvahu, jsou v následující posloupnosti zvýrazněny (abychom ukázali, proč se důkaz nazývá diagonální metoda).
- 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 následovně:
- pokud je na k-tém místě v rk číslice α ∈ {0,1,2,3,4,5,6,7,8,9} pak na k-tém místě v x bude číslice β ∈ ({0,1,2,3,4,5,6,7,8,9} - {α})
- zjednodušeně např.:
- pokud je na k-tém místě v rk číslice 5 pak na k-tém místě v x bude 4,
- pokud není na k-tém místě v rk číslice 5 pak na k-tém místě v x bude 5.
- Číslo x je zřejmě reálné (jelikož všechny desetinné rozvoje reprezentují reálné číslo) z intervalu [0,1]. Například pro posloupnost uvedenou výše by x vypadalo takto:
- x = 0 , 4 5 5 5 5 5 4 …
- Musí tedy existovat rn = x pro nějaké n, jelikož jsme předpokládali, že v posloupnosti (r1, r2, r3, …) jsou všechna reálná čísla z intervalu [0, 1].
- Ale díky našemu způsobu sestrojování čísla x se x liší od každého rn na n-tém desetinném čísle, tedy x neleží v posloupnosti (r1, r2, r3, …)
- Tato sekvence tedy není sekvencí všech reálných čísel z intervalu [0,1], docházíme ke sporu.
- Odtud plyne, že předpoklad, že interval [0,1] je spočetný, musí být špatný.
