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:

Privzame se (kot predpostavko, za katero se bo pozneje dokazalo, da mora biti napačna), da bi interval [0,1] res bil števno neskončen.
Potem se lahko oštevilči vsa (realna) števila na tem intervalu v zaporedje, ( r₁, r₂, r₃, …)
Ve se, da se lahko vsako od teh števil predstavi v desetiškem zapisu.
Vsa ta števila se zbere 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…, se vzame zapis, ki se končuje z deveticami. Vzame se, 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 …

…
Zdaj se bo skonstruiralo realno število x z intervala [0,1] tako, da se bo pogledalo k-to števko za desetiško vejico v desetiškem zapisu števila k-tega števila, r_k. Števke, ki se jih bo gledalo, 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 …

…
Iz teh števk naj se definira š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.
Š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, se dobi naslednji desetiški zapis:
x = 0 , 4 5 5 5 5 5 4 …
Torej mora za neki n veljati r_n = x, saj se je predpostavilo, da zaporedje (r₁, r₂, r₃, …) oštevilči vsa realna števila na intervalu [0,1].
Toda, ker so se v 6. koraku 4-ke in 5-ke izbralo 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!
To zaporedje torej ni oštevilčenje množice vseh realnih števil z intervala [0,1]. To je protislovje.
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 se lahko oštevilčilo vsa realna števila in bi se zaporedje, ki bi oštevilčilo [0,1], lahko dobilo tako, da bi se odstranilo vsa realna števila zunaj tega intervala. Vendar se je pravkar pokazalo, da tako zaporedje, ki bi oštevilčilo [0,1], ne more obstajati.

Lahko bi se tudi dokazalo, da sta množici [0,1] in R enako močni tako, da bi se med njima konstruirala bijekcija. Za zaprti interval [0,1] je to storiti rahlo nerodno, čeprav možno; za odprti interval (0,1) bi se lahko uporabilo $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. zgornji 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 se jo bo pisalo 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 je protislovje.

Bodite pozorni na podobnost pri konstrukciji T in množice v Russllovem 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 pokaže, da je množica realnih števil »večja« kot množica celih števil. Vpraša se lahko, ali obstaja množica, katere kardinalnost je »vmes« med kardinalnostjo množice celih in kardinalnostjo množice realnih števil. To vprašanje privede do slavne domneve kontinuuma. Podobno 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.