Vikipedio

Diagonala argumento de Cantor: Malsamoj inter versioj

Browse history interactively
[kontrolita revizio][kontrolita revizio]
← Iru al antaŭa ŝanĝoIru al sekvanta ŝanĝo →
Enhavo forigita Enhavo aldonita
VidaVikiteksto
situita --> situanta
Linio 1:
En [[matematiko]], la '''diagonala argumento de Cantor''' estas [[matematika pruvo|pruvo]] ke ekzistas [[malfinia aro|malfiniaj aroj]], kiuj ne povas esti en [[ensurĵeto|bijekcia rilato]] kun la malfinia aro de [[natura nombro|naturaj nombroj]]. Ĉi tiaj aroj estas [[nekalkulebla aro|nekalkuleblaj aroj]], iliaj [[kardinala nombro|kardinalojkardinalecoj]] estas pli grandaj ol kardinalokardinaleco de la aro de naturaj nombroj.
 
La diagonala argumento estis publikigita de [[Georg Cantor]] en 1891. LaĜi diagonalo argumentone estis ne [[unua nekalkulebleca pruvo]] de Cantor de la nekalkulebleco de la [[reela nombro|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ŭ sciatajkonataj 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 malfiniajn vicojn de formo ''(x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, ...)'' kie ĉiu ero ''x<sub>i</sub>'' estas 0 aŭ 1.
Linio 18:
kaj ĝenerale
 
: ''s<sub>n</sub> = (s<sub>n, 1</sub>, s<sub>n, 2</sub>, s<sub>n, 3</sub>, s<sub>n, 4</sub>, ...)''
 
kio estas ke ''s<sub>n, m</sub>'' estas la ''m''-a ero de la ''n''-a vico de la listo.
 
Eblas konstrui vicon de eroj ''s<sub>0</sub>'' tieltian, 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<sub>m, m</sub>=0'', do ''s<sub>0, m</sub>=1''; kaj se ''s<sub>m, m</sub>=1'', do ''s<sub>0, m</sub>=0''. En la ekzemplo:
 
:''s<sub>1</sub> = ('''0''', 0, 0, 0, 0, 0, 0, ...)''
Linio 35:
:''s<sub>0</sub> = (1, 0, 1, 1, 1, 0, 1, ...)''
 
La eroj ''s<sub>1, 1</sub>, s<sub>2, 2</sub>, s<sub>3, 3</sub>, ...'', laŭ kiuj estas la konstruado, estas situitajsituantaj laŭ diagonalo de la tabelo, de kie aperis la nomo "diagonala argumento".
 
Tiel la nova vico ''s<sub>0</sub>'' estas malsama de ĉiuj vicoj en la listo, ĉar ĝi estas malsama de ĉiu vico ''s<sub>i</sub>'' je almenaŭ unu ero ''s<sub>0, i</sub>≠s<sub>i, i</sub>''.
 
De ĉi tio sekvas ke la aro ''T'', konsistanta el ĉiuj malfiniaj vicoj de 0 kaj 1, ne povas esti metita en [[kalkulebla]] listo ''s<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>, ...''. Alie, ĝi devus ebli per la pli supre priskribita procezo konstrui vicon ''s''<sub>0</sub>, 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 [[bijekcio|bijekcia]] (unu al unu) rilato kun la naturaj nombroj. En aliaj vortoj, ĝi estas nekalkulebla.
Linio 45:
== Reelaj nombroj ==
 
Naive, oni povus konsideri malfiniajn duumajn vicojn de 0 kaj 1 kiel duumajduumajn elvolvaĵojelvolvaĵojn de [[reela nombro|reelaj nombroj]] inter 0 kaj 1. Tamen, estas [[0,999...|ne-unikeco de malfiniaj 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 malfinia frakcio finiĝanta je ''222...'' estas egala al triuma malfinia 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.
Elŝutita el "https://eo.wikipedia.org/wiki/Diagonala_argumento_de_Cantor"