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, et reaalarvude hulk on loenduv. Tema algne tõestus ei kasutanud kümnendmurde ega üldse ühtegi arvusüsteemil.

Hiljem on selle tõestuse eeskujul konstrueeritud palju teisi tõestusi. Neid nimetatakse diagonaaltõestusteks.

[redigeeri] 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 ( r₁, r₂, r₃, ... )
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:

      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) Nüüd me konstrueerime lõiku [0,1] kuuluva reaalarvu x, vaadeldes arvu r_k k-ndat komakohta.

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

Meid huvitavad komakohad on antud rasvases kirjas. Nad illustreerivad tõestuse "diagonaalsust".

6) Nende komakohtade järgi me konstrueerime arvu x komakohad järgmiselt:

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

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 r_n = x, sest me oletasime, et jada ( r₁, r₂, r₃, ... ) 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 r_n, mistõttu arvu x jadas ( r₁, r₂, r₃, ... ) 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 $\mathbb{R}$ on mitteloenduv. Kui $\mathbb{R}$ 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 $\mathbb{R}$ 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 $f:(0, 1)\rightarrow\mathbb{R}$ , mis on defineeritud nii: $f(x) = \tan\left(\pi\left(x-\frac{1}{2}\right)\right)$ .

[redigeeri] Üldistus

Diagonaaltõestust üldistatud kujul kasutas Cantor selleks, et tõestada Cantori teoreemi: iga hulga S puhul on hulga S potentshulk (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

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

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 tõestust ei saa läbi viia Williard Van Orman Quine'i "uute aluste" hulgateoorias, kus eralduvusaksioomil on teistsugune kuju, nii et hulka $\{\,s\in S: s\not\in f(s)\,\}$ ei saa väljendada.

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.

Välja otsitud andmebaasist "http://et.wikipedia.org../../../c/a/n/Cantori_diagonaalt%C3%B5estus.html"

Kategooriad: Hulgateooria

We provide Linux to the World

Cantori diagonaaltõestus

[redigeeri] Reaalarvud

[redigeeri] Üldistus

Views

Navigeerimiskast

Otsi

Teised keeled