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.