Diagonala argumento de Cantor

En matematiko, la diagonala argumento de Cantor estas pruvo ke ekzistas nefiniaj aroj, kiuj ne povas esti en bijekcia 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 (x₁, x₂, x₃, ...) kie ĉiu ero x_i estas 0 aŭ 1.

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

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

kaj ĝenerale

s_n = (s_n,1, s_n,2, s_n,3, s_n,4, ...)

kio estas ke s_{n, m} estas la m-a ero de la n-a vico de la listo.

Eblas konstrui vicon de eroj s₀ 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 s_m,m=0, do s_0,m=1; kaj se s_m,m=1, do s_0,m=0. En la ekzemplo:

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

La eroj s_1,1, s_2,2, s_3,3, ..., laŭ kiuj estas la konstruado, estas situantaj laŭ diagonalo de la tabelo, de kie aperis la nomo "diagonala argumento".

Tiel la nova vico s₀ estas malsama de ĉiuj vicoj en la listo, ĉar ĝi estas malsama de ĉiu vico s_i je almenaŭ unu ero s_{0, i}≠s_{i, 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 s₁, s₂, s₃, .... Alie, ĝi devus ebli per la pli supre priskribita procezo konstrui vicon s₀, 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 bijekcia (unu al unu) rilato kun la naturaj nombroj. En aliaj vortoj, ĝi estas nekalkulebla.

Reelaj nombroj[redakti | redakti fonton]

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 r_i 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:

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

...

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

r₀ = 0 , 4 5 5 5 5 5 4 ...

Ĝeneralaj aroj[redakti | redakti fonton]

Ĝ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 surjekcia, 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ŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]

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