Diagonala argumento de Cantor

En matematiko, la **diagonala argumento de Cantor** estas pruvo, ke ekzistas nefiniaj aroj, kiuj ne povas esti en reciproke unuvalora rilato kun la nefinia aro de naturaj nombroj. Ĉi tiaj aroj estas nekalkuleblaj aroj, iliaj kardinalecoj estas pli grandaj ol kardinaleco de la aro de naturaj nombroj.

La diagonala argumento estis publikigita de Georg Cantor en 1891. Ĝi ne estis unua nekalkulebleca pruvo de Cantor de la nekalkulebleco de la reelaj nombroj. La diagonala argumento estis publikigita multe poste ol lia unua pruvo, kiu aperis en 1874. Tamen, ĝi demonstracias povan kaj ĝeneralan manieron kiu estas uzata en larĝa limigo de pruvoj, ankaŭ konataj kiel diagonalaj argumentoj. Iuj ekzemploj estas paradokso de Russell, la unua el la teoremoj de nekompleteco, kaj respondo de Turing al la problemo de formala decida algoritmo.

La originala pruvo konsideras nefiniajn vicojn de formo *(x1, x2, x3, ...)* kie ĉiu ero *xi* estas 0 aŭ 1.

Konsideru ĉiun kalkuleblan liston de iuj el ĉi tiuj vicoj, ekzemple:

:*s1 = (0, 0, 0, 0, 0, 0, 0, ...)*
:*s2 = (1, 1, 1, 1, 1, 1, 1, ...)*
:*s3 = (0, 1, 0, 1, 0, 1, 0, ...)*
:*s4 = (1, 0, 1, 0, 1, 0, 1, ...)*
:*s5 = (1, 1, 0, 1, 0, 1, 1, ...)*
:*s6 = (0, 0, 1, 1, 0, 1, 1, ...)*
:*s7 = (1, 0, 0, 0, 1, 0, 0, ...)*
:...

kaj ĝenerale

: *sn = (sn,1, sn,2, sn,3, sn,4, ...)*

kio estas ke *sn, m* estas la *m*-a ero de la *n*-a vico de la listo.

Eblas konstrui vicon de eroj *s0* tian, ke ĝia unua ero estas malsama de la unua ero de la unua vico en la listo, ĝia dua ero estas malsama de la dua ero de la dua vico de la listo, kaj, ĝenerale, ĝia *n*-a ero estas malsama de la *n*-a ero de la *n*-a vico de la listo. Tio estas, se *sm,m=0*, do *s0,m=1*; kaj se *sm,m=1*, do *s0,m=0*. En la ekzemplo:

:*s1 = (**0**, 0, 0, 0, 0, 0, 0, ...)*
:*s2 = (1, **1**, 1, 1, 1, 1, 1, ...)*
:*s3 = (0, 1, **0**, 1, 0, 1, 0, ...)*
:*s4 = (1, 0, 1, **0**, 1, 0, 1, ...)*
:*s5 = (1, 1, 0, 1, **0**, 1, 1, ...)*
:*s6 = (0, 0, 1, 1, 0, **1**, 1, ...)*
:*s7 = (1, 0, 0, 0, 1, 0, **0**, ...)*
:...

:*s0 = (1, 0, 1, 1, 1, 0, 1, ...)*

La eroj *s1,1, s2,2, s3,3, ...*, laŭ kiuj estas la konstruado, estas situantaj laŭ diagonalo de la tabelo, de kie aperis la nomo "diagonala argumento". 

Tiel la nova vico *s0* estas malsama de ĉiuj vicoj en la listo, ĉar ĝi estas malsama de ĉiu vico *si* je almenaŭ unu ero *s0, i≠si, i*.

De ĉi tio sekvas ke la aro *T*, konsistanta el ĉiuj nefiniaj vicoj de 0 kaj 1, ne povas esti metita en kalkulebla listo *s1, s2, s3, ...*. Alie, ĝi devus ebli per la pli supre priskribita procezo konstrui vicon *s*0, kiu devus esti en *T* (ĉar ĝi estas vico de 0 kaj 1 kiu estas en *T* laŭ la difino de *T*) kaj samtempe ne en *T* (ĉar oni povas intence konstrui ĝi tiel ke ĝi ne estas en la listo).

Pro tio *T* ne povas esti en reciproke unuvslora (unu al unu) rilato kun la naturaj nombroj. En aliaj vortoj, ĝi estas nekalkulebla.

## Reelaj nombroj 
Naive, oni povus konsideri nefiniajn duumajn vicojn de 0 kaj 1 kiel duumajn elvolvaĵojn de reelaj nombroj inter 0 kaj 1. Tamen, estas ne-unikeco de nefiniaj elvolvaĵoj en poziciaj nombrosistemoj, kio signifas ke ĉi tiu argumento ne laboras: du malsamaj duumaj vicoj povas respektivi al la sama reela nombro. Tial la nova vico produktita per diagonaligo povas esti egala al unu el la listigitaj vicoj ĉe komparo de ili kiel reelaj nombroj.

Malmulte la alia maniero povas esti uzata por ĉi tiu celo. Oni povas uzi triumajn elvolvaĵojn de reelaj nombroj (kun ciferoj 0, 1, 2), nefiniĝantajn je *222...*, ĉar triuma nefinia frakcio finiĝanta je *222...* estas egala al triuma nefinia frakcio finiĝanta je *000...* kun la antaŭa parto pli granda je unuo de la ĝia lasta cifero. En konstruado de la nova vico surbaze de la diagonalo oni uzu nur ciferojn 0 aŭ 1 sed ne 2.

Pli ĝenerale, la maniero povas labori kun ĉiu nombra bazo *b≥3*. Por la nombroj *ri* oni devas elekti prezentojn ne finiĝatajn je nefinia ĉeno de ciferoj *b-1* (la maksimuma cifero de la nombrosistemo). En konstruado de la nova vico surbaze de la diagonalo por elektado de la ciferoj povas esti uzata ajna regulo tia ke la cifero de la nova vico estu ĉiam malsama de la cifero en la diagonalo, kaj la cifero *b-1* devas esti neuzata.

Ekzemple en dekuma sistemo estu:

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

En la nova nombro cifero estu 4 se la fonta cifero estas 5, kaj 5 en la ceteraj okazoj:

: *r0 = 0 , 4 5 5 5 5 5 4 ...*

## Ĝeneralaj aroj 
Ĝeneraligita formo de la diagonala argumento estis uzata de Cantor por pruvi teoremon de Cantor: por ĉiu aro *S* la aro de ĉiuj subaroj de *S* estas pli granda ol *S* mem. Ĉi tiu pruvo procedas kiel sekvas:

Estu *f* esti ĉiu funkcio de *S* al ĝia aro de ĉiuj subaroj *P(S)*. Sufiĉas al pruvi *f* ne povas esti surleta, kio signifas ke ekzistas iu ero de *P(S)*, kio estas, iu subaro de *S*, kiu estas ne en la bildo de *f*. Konsideru aron:

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

Por ĉiu *s* en *S*, *s* estas en *T* aŭ ne. Se *s* estas en *T*, do laŭ difino de *T*, *s* estas ne en *f(s)*, do *T* estas ne egala al *f(s)*. Aliflanke, se *s* estas ne en *T*, tiam per difino de *T*, *s* estas en *f(s)*, tiel denove *T* estas ne egala al *f(s)*. Do *T* estas ero de *P(S)*, tia ke ne ekzistas tia *s* ke *T=f(s)*.

## Vidu ankaŭ 
* Unua nekalkulebleca pruvo
* Paradokso de Russell
* Teoremoj de nekompleteco
* Numero (matematiko)
* Kardinala nombro
* Kardinalo de kontinuumo
* Kontinuuma hipotezo
* Povo de aro
* Transfinia nombro
* Hilberta hotelo
* Aro de ĉiuj subaroj
* Teoremo de Cantor
* Ĉefdiagonalo

## Eksteraj ligiloj 
* https://web.archive.org/web/20060423090728/http://uk.geocities.com/frege@btinternet.com/cantor/diagarg.htm
* Diagonala pruvo de Cantor je MathPages
* Georg Cantor  (1874) *Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen*, Journal de Crelle 77, p258-262 http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=49464
* Georg Cantor (1891) *Über eine elementare Frage der Mannigfaltigskeitslehre*, Jahresericht der Deutsch. Math.Vereing., Vol. I, pp 75-78 (1890-1891). http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=49471
* *Sur une propriété du système de tous les nombres algébriques réels*, Acta Math. 2 (1883), pp 305-310, en retejo de BNF

Kategorio:Aro-teorio
Kategorio:Matematikaj teoremoj
Kategorio:Pruvoj
Kategorio:Senfineco