Cantorova diagonální metoda

Z Wikipedie, otevřené encyklopedie

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í).

[editovat] 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 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í). Předpokládejme například, že počátek našeho seznamu vypadá takto:

   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-té číslo v jeho desetinném rozvoji vezmeme v úvahu k-té číslo v desetinném rozvoji r_k. Čí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).

   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 β є ({0,1,2,3,4,5,6,7,8,9} - {α})
7. 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 není na k-tém místě v r_k číslice 5 pak na k-tém místě v x bude 5.
8. Čí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 …

9. 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].
10. Ale díky našemu způsobu sestrojování čísla x se x liší od každého r_n na n-tém desetinném čísle, tedy x neleží v posloupnosti (r₁, r₂, r₃, …)
11. Tato sekvence tedy není sekvencí všech reálných čísel z intervalu [0,1], docházíme ke sporu.
12. Odtud plyne, že předpoklad, že interval [0,1] je spočetný, musí být špatný.