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 s0, 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:



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 


 Diagonala pruvo de Cantor je MathPages
 Georg Cantor  (1874) Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, Journal de Crelle 77, p258-262 
 Georg Cantor (1891) Über eine elementare Frage der Mannigfaltigskeitslehre, Jahresericht der Deutsch. Math.Vereing., Vol. I, pp 75-78 (1890-1891). 
 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