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: 
 1) Oletame, et lõigu [0,1] arvude hulk on loenduv.
 2) Siis me saame nummerdada kõik selle lõigu punktid jadana ( r1, r2, r3, ... )
 3) Me teame juba, et iga arvu nende seast saab esitada lõpmatu kümnendmurruna. 
 4) Me koostame arvude loendi. Kui mõni arv on esitatav kahe erineva kümnendmurruna (näiteks 0,499 ... = 0,500 ...), siis valime üheksatega lõppeva esituse (ainult arvu 0 puhul on meil nullidega esitus). Oletame näiteks, et jada algus näeb kümnendmurdudena välja nii: 
 
  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 ... 
  ...

 5) Nüüd me konstrueerime lõiku [0,1] kuuluva reaalarvu x, vaadeldes arvu rk k-ndat komakohta.  

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

 Meid huvitavad komakohad on antud paksus kirjas. Nad illustreerivad tõestuse "diagonaalsust". 
 6) Nende komakohtade järgi me konstrueerime arvu x komakohad järgmiselt:
 kui arvu rk k-s komakoht on 5, siis arvu x k-s komakoht on 4
 kui arvu rk 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 ...

 7) On ilmne, et arv x on reaalarv (me teame, et kõik lõpmatud kümnendmurrud esitavad reaalarve). 
 8) Sellepärast peab mingi n korral kehtima võrdus rn = x, sest me oletasime, et jada ( r1, r2, r3, ... ) nummerdab kõik reaalarvud lõigus [0, 1]. 
 9) Kuid viisi tõttu, kuidas me sammul 6) valisime komakohad 4 ja 5, erineb arv x n-inda komakoha poolest arvust rn, mistõttu arvu x jadas ( r1, r2, r3, ... ) ei leidu.
 10) Sellepärast ei nummerda see jada kõikide lõiku [0,1] kuuluvate reaalarvude hulka. See on vastuolu. 
 11) Seega peab oletus 1), et lõik [0,1] on loenduv arvude hulk, olema väär.  

Sellest tulemusest järeldub otseselt, et kõikide reaalarvude hulk  on mitteloenduv. Kui  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. 
Teine võimalus on näidata, et hulkadel [0, 1] ja  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 , mis on defineeritud nii: 
.

Ü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 

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

Vaata ka
Cantori esimene diagonaalargument

Hulgateooria