Cantorjev diagonalni dokaz

Cantorjev diagonalni dokaz je matematični dokaz, s katerim je Georg Ferdinand Cantor leta 1877 pokazal, da realnih števil ni števno neskončno. To pomeni, da je realnih števil več kot naravnih, čeprav sta obe množici neskončni.

Čeprav je najbolj znan, to ni bil prvi Cantorjev dokaz o neštevnosti realnih števil. Njegov tri leta starejši prvi dokaz ni omenjal desetiškega zapisa niti drugih številskih sistemov. Cantorjev diagonalni dokaz uporablja isti koncept kot diagonalizacija s katero je dokazal, da je racionalnih in naravnih števil enako mnogo.

Realna števila

Cantorjev izvirni dokaz pokaže, da interval [0,1] ni števno neskončen. Ta dokaz s protislovjem gre takole:

1. Privzemimo (kot predpostavko, za katero bomo pozneje dokazali, da mora biti napačna), da bi interval [0,1] res bil števno neskončen.
2. Potem lahko oštevilčimo vsa (realna) števila na tem intervalu v zaporedje, ( r₁, r₂, r₃, …)
3. Vemo, da vsako od teh števil lahko predstavimo v desetiškem zapisu.
4. Vsa ta števila zberemo v seznam (ni treba, da so v kakšnem posebnem vrstnem redu). V primeru števil, ki imajo po dva desetiška zapisa, kot npr. 0,499… = 0,500…, vzamemo zapis, ki se končuje z deveticami. Vzemimo, na primer, da so desetiški zapisi na začetku zaporedja takšni:

   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. Zdaj bomo skonstruirali realno število x z intervala [0,1] tako, da bomo pogledali k-to števko za desetiško vejico v desetiškem zapisu števila k-tega števila, r_k. Števke, ki jih bomo gledali, so krepke in podrčtane, da nakazujejo zakaj se temu reče diagonalni dokaz.

   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. Iz teh števk definirajmo števke števila x kot sledi.
   • če je k-ta števka števila r_k enaka 5, potem naj bo k'-ta števka števila x enaka 4,
   • če k-ta števka števila r_k ni enaka 5, potem naj bo k'-ta števka števila x enaka 5.
7. Število x je očitno realno število (saj vsak desetiški zapis predstavlja neko realno število) na intervalu [0,1]. Za zgornje zaporedje {r_n}, na primer, dobimo naslednji desetiški zapis:

   x = 0 , 4 5 5 5 5 5 4 …

8. Torej mora za neki n veljati r_n = x, saj smo predpostavili, da zaporedje (r₁, r₂, r₃, …) oštevilči vsa realna števila na intervalu [0,1].
9. Toda, ker smo v 6. koraku 4-ke in 5-ke izbrali na posebno »zloben« način, se x od r_n razlikuje vsaj na n-tem mestu, za vsak n. To pomeni, da števila x v zaporedju (r₁, r₂, r₃, …) ni!
10. To zaporedje torej ni oštevilčenje množice vseh realnih števil z intervala [0,1]. To je protislovje.
11. Sklep: privzetek (1), da je interval [0,1] števno neskončen, mora biti napačen.

Neposredna posledica tega rezultata je, da tudi množica vseh realnih števil R ni števna. Če bi bila R števna, bi lahko oštevilčili vsa realna števila in bi zaporedje, ki bi oštevilčilo [0,1], lahko dobili tako, da bi odstranili vsa realna števila zunaj tega intervala. Vendar smo pravkar pokazali, da tako zaporedje, ki bi oštevilčilo [0,1], ne more obstajati.

Lahko bi tudi dokazali, da sta množici [0,1] in R enako močni tako, da bi med njima konstruirali bijekcijo. Za zaprti interval [0,1] je to storiti rahlo nerodno, čeprav možno; za odprti interval (0,1) bi lahko uporabili $f\colon (0,1)\rightarrow \mathbb {R}$ definirano kot $f(x)=\,\mathrm {tg} \,\left(\pi \left(x-{\frac {1}{2}}\right)\right)$.

Zakaj to ne deluje na celih številih

Ljudje včasih mislijo, da je moč zgornji dokaz prilagoditi na cela števila in s tem pokazati, da so tudi ona neštevna. To skušajo storiti tako, da iz zgornjih izrazov črtajo decimalne vejice. Težava pri tem je, da neskončno zaporedje neničelnih števil ne določa celega števila. To je razlog za 7. zgordnji korak. Množica celih števil je seveda števna, zato tak dokaz ni mogoč.

Splošne množice

Cantor je uporabil posplošeno obliko diagonalnega dokaza, da je dokazal Cantorjev izrek: za vsako množico S, je potenčna množica množice S - se pravi, množica vseh podmnožic množice S (tu jo bomo pisali kot P(S)) - večja kot sama množica S. Ta dokaz s protislovjem gre takole:

Denimo, da sta S in P(S) enako močni in naj bo torej f katerakoli bijektivna preslikava med njima. Zadostuje dokazati, da f ne more biti surjekcija. To pomeni, da neki element množice P(S) - to se po zgornji definiciji v konkretnem primeru pravi: neka podmnožica množice S - ni v sliki preslikave f. Taka množica je množica T, definirana kot

$T=\{\,s\in S:s\not \in f(s)\,\}.$

Če je T v sliki f, potem za neki t iz S velja T = f(t). Bodisi je t v množici T, ali pa ni:

• Če t je v T, potem je t v f(t), vendar, po definiciji množice T, odtod sledi, da t ni v T.
• Po drugi plati, če t ni v T, potem t ni v f(t), in po definiciji T odtod sledi, da t je v T.

V vsakem primeru imamo protislovje.

Bodite pozorni na podobnost pri konstrukciji T in množice v Russelovem paradoksu. Cantorjev rezultat pomeni, da je pojem »množice vseh množic« v običajni teoriji množic nekonsistenten; če bi bila S res množica vseh množic, bi bila njena potenčna množica P(S) hkrati večja od S in podmnožica množice S.

Zgornjega dokaza ni moč izvesti v Quineovi teoriji množici na »novih temeljih«, ki uporablja drugačno različico aksioma ločljivosti, v katerem ni moč izraziti $\{\,s\in S:s\not \in f(s)\,\}$.

Analogije diagonalnega dokaza se uporabljajo v matematiki za dokaz obstoja ali neobstoja določenih objektov. Denimo, standardni dokaz nerešljivosti problema ustavitve je v bistvu diagonalni dokaz.

Diagonalni dokaz nam pokaže, da je množica realnih števil »večja« kot množica celih števil. Vprašamo se lahko, ali obstaja množica, katere kardinalnost je »vmes« med kardinalnostjo množice celih in kardinalnostjo množice realnih števil. To vprašanje nas privede do slavne domneve kontinuuma. Podobno nas vprašanje ali za neko množico s obstaja množica, katere kardinalnost je med močjo s in P(s), pripelje do posplošene domneve kontinuuma.