Cantori diagonaaltõestus

Cantori diagonaaltõestus on Georg Cantorilt pärinev tõestus, et reaalarvude hulk ei ole loenduv. 
See ei olnud Cantori esimene tõestus reaalarvude hulga mitteloenduvuse kohta. Tema algne tõestus ei kasutanud kümnendmurde ega üldse ühtegi arvusüsteemi. 
Hiljem on selle tõestuse eeskujul konstrueeritud palju teisi tõestusi. Neid nimetatakse diagonaaltõestusteks. 
Reaalarvud.
Cantori tõestus näitab, et lõigu [0,1] arvude hulk ei ole loenduv. 
Vastuväiteline tõestus koosneb järgmistest sammudest: 
 "r"1 = 0 , 5 1 0 5 1 1 0 ... 
 "r"2 = 0 , 4 1 3 2 0 4 3 ...
 "r"3 = 0 , 8 2 4 5 0 2 6 ... 
 "r"4 = 0 , 2 3 3 0 1 2 6 ...
 "r"5 = 0 , 4 1 0 7 2 4 6 ... 
 "r"6 = 0 , 9 9 3 7 8 3 8 ...
 "r"7 = 0 , 0 1 0 5 1 3 5 ... 
 "r"1 = 0 , 5 1 0 5 1 1 0 ... 
 "r"2 = 0 , 4 1 3 2 0 4 3 ...
 "r"3 = 0 , 8 2 4 5 0 2 6 ... 
 "r"4 = 0 , 2 3 3 0 1 2 6 ...
 "r"5 = 0 , 4 1 0 7 2 4 6 ... 
 "r"6 = 0 , 9 9 3 7 8 3 8 ...
 "r"7 = 0 , 0 1 0 5 1 3 5 ... 
 Meid huvitavad komakohad on antud paksus kirjas. Nad illustreerivad tõestuse "diagonaalsust". 
* kui arvu "r""k" "k"-s komakoht on 5, siis arvu "x" "k"-s komakoht on 4
* kui arvu "r""k" "k"-s komakoht ei ole 5, siis arvu "x" "k"-s komakoht on 5
 Ülaltoodud näites saame tulemusena järgmise kujuga kümnendmurru: 
 "x" = 0 , 4 5 5 5 5 5 4 ...
Sellest tulemusest järeldub otseselt, et kõikide reaalarvude hulk formula_1 on mitteloenduv. Kui formula_1 oleks loenduv, siis me saaksime mingi jadaga kõik reaalarvud ära nummerdada ning seejärel saada lõiku [0, 1] kuuluvaid arve nummerdava jada, eemaldades kõik reaalarvud, mis sellesse lõiku ei kuulu. Ent me näitasime äsja, et seda viimast jada ei ole olemas.&lt;br&gt; 
Teine võimalus on näidata, et hulkadel [0, 1] ja formula_1 on sama võimsus, konstrueerides nendevahelise bijektsiooni (üksühese vastavuse. Lõigu [0, 1] puhul on seda pisut tülikas (kuigi võimalik) teha. Vahemiku (0, 1) puhul võib kasutada funktsiooni formula_4, mis on defineeritud nii: 
formula_5.
Üldistus.
Diagonaaltõestust üldistatud kujul kasutas Cantor selleks, et tõestada Cantori teoreemi: iga hulga "S" puhul on hulga "S" astmehulk (hulga "S" kõikide alamhulkade hulk) P("S")) suurema võimsusega kui hulk "S" ise. See tõestus käib nii: 
Olgu "f" mis tahes üksühene funktsioon (bijektsioon) hulgalt "S" hulka P("S"). Piisab sellest, kui näidata, et "f" ei saa olla sürjektiivne. See tähendab, et hulga P("S") mingi element (hulga "S" mingi alamhulk) ei ole funktsiooni "f" kujutise element. Selline hulk on 
formula_6
Kui "T" kuulub funktsiooni "f" kujutisse, siis mingi "t" puhul hulgast "S" kehtib võrdus "T" = "f"("t"). Element "t" kas on hulga "T" element või ei ole.&lt;br&gt;
Kui "t" on "T" element, siis "t" on kujutise "f"("t") element, kuid hulga "T" definitsiooni kohaselt järeldub sellest, et "t" ei ole "T" element. Teiselt poolt, kui "t" ei ole "T" element, siis "t" ei ole kujutise "f"("t") element, ning hulga "T" definitsiooni kohaselt järeldub sellest, et "t" on "T" element. Mõlemal juhul on tegemist vastuoluga. 
Märgime sarnasust hulga "T" ning Russelli paradoksis konstrueeritava hulga konstruktsiooni vahel. Siinse tulemuse põhjal saab näidata, et kõikide hulkade hulga mõiste on tavalises hulgateoorias vastuoluline: kui S oleks kõikide hulkade hulk, siis P(S) oleks samal ajal võimsuselt suurem kui S ja hulga S alamhulk.
Ülaltoodud vastuolu sõltub aksioomide valikust ja näiteks ei ole niisuguse tulemuseni jõudmine võimalik Willard Van Orman Quine'i "uute aluste" hulgateoorias, kus eralduvusaksioomil on teistsugune kuju, nii et hulka formula_7 ei saa väljendada. Samuti välistab naiivse hulgateooria paradoksid Zermelo-Fraenkeli hulgateooria.
Sama tõestus on esitatud kujul, millest on võib-olla lihtsam aru saada, artiklis Cantori teoreem.
Diagonaaltõestuse analooge kasutatakse matemaatikas laialdaselt mingite objektide olemasolu või mitteolemasolu tõestamiseks. Näiteks peatumisprobleemi mittelahenduvuse tavaline tõestus on diagonaaltõestus. 
Diagonaaltõestus näitab, et reaalarvude hulk on "suurem" kui naturaalarvude hulk. Sellepärast võib küsida, kas on olemas hulk, mille võimsus on naturaalarvude hulga ja reaalarvude hulga võimsuse "vahepeal". See küsimus viib kontiinuumhüpoteesini. Samamoodi viib küsimus, kas mõne hulga "s" puhul on olemas hulk, mille võimsus on hulkade "s" ja P("s") võimsuste vahepeal, üldistatud kontiinuumhüpoteesini.