La diagonala argumento de Cantor
#000000
En aroteorio, la diagonala argumento de Cantor, ankaŭ nomita la diagonaligargumento, la diagonala oblikvargumento aŭ la diagonala metodo, estis publikigita en 1891 fare de Georg Cantor kiel matematika pruvo kiu ekzistas senfinaj aroj kiuj ne povas esti metitaj en ekzaktan korespondadon kun la senfina aro de naturaj nombroj.
Tiaj aroj nun estas konataj kiel nenombreblaj aroj, kaj la grandeco de senfinaj aroj nun estas traktita per la teorio de povo de aroj kiu kantoro komencis.
#000002
La diagonala argumento ne estis Cantor unua pruvo de la unkountabileco de la realaj nombroj, kiuj aperis en 1874.
Tamen, ĝi montras potencan kaj ĝeneralan teknikon kiu poste estis uzita en larĝa gamo de pruvoj, [6] inkluzive de la unua el la nekompleteco-teoremoj de Gödel [2] kaj tiu de Turing respondi al la Entscheidungsproblem .
Diagonaligargumentoj ofte estas ankaŭ la fonto de kontraŭdiroj kiel la paradokso de Russell [7] [8] kaj la paradokso de Rikardo.
#000003
Historie, la diagonala argumento unue aperis en la laboro de Paul du Bois-Reymond en 1875.
#000004
Versio por New Foundations de Quine
#000005
En lia 1891 artikolo, Kantoro pripensis la aron T de ĉiuj senfinaj sekvencoj de binaraj diĝitoj (t.e. ĉiu cifero estas nul aŭ oni).
Li komencas kun helpema pruvo de la sekva teoremo:
#000006
ĉiu listigo de elementoj de T estas, tiam ekzistas ĉiam elemento s de T kiu egalrilatas al neniu s n en la listigo.
#000007
Pruvi tion, surbaze de listigo de elementoj de T, kiel ekz.
#000008
li konstruas la sekvencon s elektante la unuan fingron tiel komplementa al la unua fingro da s 1 (interŝanĝante 0s kun 1s kaj inverse), la duan fingron tiel komplementa al la dua fingro da s 2 , la trian fingron kiel komplemente al la tria fingro da s 3 , kaj ĝenerale por ĉiu n, la n th cifero kiel komplemente al la n th cifero da s n .
En la ekzemplo, tio donas:
#000009
Proksime de konstruo, s devias de ĉiu s n , ĉar iliaj n th ciferoj malsamas (elstarigite en la ekzemplo).
Tial, s ne povas okazi en la listigo.
#000010
Surbaze de tiu teoremo, Kantoro tiam utiligas pruvon de kontraŭdiro por montri tion:
#000011
La aro T estas nenombrebla.
#000012
Li supozas por kontraŭdiro ke tiu T estis nombrebla.
Tiam ĉiuj ĝiaj elementoj povus esti skribitaj kiel listigo s 1, s 2
Apliki la antaŭan teoremon al tiu listigo produktus sekvencon s ne apartenanta al la listigo.
Tamen, s estis elemento de T kaj devus tial esti en la listigo.
Tio kontraŭdiras la originan supozon, tiel ke T devas esti nenombrebla.
#000013
La interpreto de la rezulto de Cantor dependos sur onies vido de matematiko.
Al konstruistoj, la argumento montras al ne pli ol ke ekzistas neniu ensurĵeto inter la naturaj nombroj kaj T.
Ne ekskludas la eblecon ke la lasta estas subnombreblaj.
En la kunteksto de klasika matematiko, tio estas malebla, kaj la diagonala argumento establas ke, kvankam ambaŭ aroj estas senfinaj, ekzistas fakte pli senfinaj sekvencoj de tiaj kaj nuloj ol ekzistas naturaj nombroj.
#000014
La unkountabileco de la realaj nombroj jam estis establita per Cantor unua unkountabilecpruvo, sed ĝi ankaŭ sekvas el ĉi-supra rezulto.
Por pruvi tion, injekto estos konstruita de la aro T el senfinaj binaraj ŝnuroj ĝis la aro R da realaj nombroj.
Ĉar T estas nenombrebla, la bildo de tiu funkcio, kiu estas subaro de R, estas nenombrebla.
Ankaŭ, uzante metodon de konstruo elpensita fare de Kantoro, ensurĵeto estos konstruita inter T kaj R.
#000015
Injekto de T ĝis R ricevas mapante ŝnurojn en T al decimaloj, kiel ekzemple mapado de t = 0111 ...
Tiu funkcio, difinita per f ( t) = 0.
t , estas injekto ĉar ĝi mapas malsamajn ŝnurojn al malsamaj nombroj.
#000016
Anstataŭe de mapado 0111 ...
, ĝi povas esti mapita al la baz b nombro: 0.0111 ...
Tio kondukas al la familio de funkcioj:
La funkcioj f b ( t) estas injektoj, krom f 2 ( t).
Tiu funkcio estos modifita por produkti ensurĵeton inter T kaj R.
#000017
Tiu konstruo uzas metodon elpensitan fare de Kantoro kiu estis publikigita en 1878.
Li uzis ĝin por konstrui ensurĵeton inter la fermita intervalo [0, 1] kaj la irational en la malferma intervalo (0, 1).
Li unue forigis nombreble senfinan subaron de ĉiu el tiuj aroj tiel ke ekzistas ensurĵeto inter la ceteraj nenombreblaj aroj.
Ĉar ekzistas ensurĵeto inter la nombreble senfinaj subaroj kiuj estis forigitaj, kombini la du ensurĵetojn produktas ensurĵeton inter la originaj aroj.
#000018
La metodo de Cantor povas esti uzita por modifi la funkcio f 2 ( t) = 0.
t 2 produkti ensurĵeton de T ĝis (0, 1).
Ĉar kelkaj nombroj havas du binarajn vastiĝojn, f 2 ( t) estas ne eĉ injektivo.
mapo al la sama nombro, 1/2.
#000019
Por modifi f 2 ( t), observi ke ĝi estas ensurĵeto krom nombreble senfina subaro de (0, 1) kaj nombreble senfina subaro de T.
Ĝi ne estas ensurĵeto ĉar la nombroj en (0, 1) tio havas du binarajn vastiĝojn.
Tiuj nombroj havas la formon m /2 n kie m estas stranga entjero kaj n estas natura nombro.
Metu tiujn nombrojn en la sekvencon:
Ankaŭ, f 2 ( t) ne estas ensurĵeto al (0, 1) ĉar la ŝnuroj en T prezentiĝanta post la binara punkto en la binaraj vastiĝoj de 0, 1, kaj la nombroj en sekvenco r.
Metu tiujn poste-konstantajn ŝnurojn en la sekvencon:
Difinu la ensurĵeton g ( t) de T ĝis (0, 1): Se t estas la n th ŝnuro en sekvenco s, lasu g ( t) esti la n th nombro en sekvenco r;
#000020
Ĝeneraligita formo de la diagonala argumento estis uzita fare de Kantoro por pruvi la teoremon de Cantor: por ĉiu aro S la aro de ĉiuj subaroj de S;
tio estas, la aro de ĉiuj subaroj de S (ĉi tie skribita kiel P ( S), havas pli grandan kardinalecon ol S mem.
#000022
Lasu f esti ajna funkcio de S ĝis P ( S).
Ĝi sufiĉas por pruvi f ne povas esti surjektive.
Tio signifas ke iu membro T de P ( S), t.e. iu subaro de S, ne estas en la bildo de f.
#000023
Por ĉiu s en S, ĉiu s estas en T aŭ ne.
Se s estas en T, tiam de difino de T, s ne estas en f ( j), tiel ke T ne estas egala al f ( j).
Aliflanke, se s ne estas en T, tiam de difino de T, s estas en f ( j), tiel ke denove T ne estas egala al f ( j);
Por pli kompleta raporto pri tiu pruvo, vidu la teoremon de Cantor.
#000024
Tiu rezulto implicas ke la nocio de la aro de ĉiuj aroj estas malkonsekvenca nocio.
Se S estus la aro de ĉiuj aroj tiam P ( S) en la sama tempo estus pli granda ol S kaj subaro de S.
#000025
Russell's Paradox montris al ni ke naiva aroteorio, surbaze de senrestrikta kompren skemo, estas malkongrua.
Notu ke ekzistas simileco inter la konstruado de T kaj la aro en la paradokso de Russell.
Tial, depende de kiel ni modifas la aksiomskemon de kompreno por eviti la paradokson de Russell, argumentoj kiel ekzemple la neekzistado de aro de ĉiuj aroj povas aŭ eble ne restas validaj.
#000026
Analogoj de la diagonala argumento estas vaste uzitaj en matematiko por pruvi la ekziston aŭ enekziston de certaj objektoj.
Ekzemple, la konvencia pruvo de la unsolvabileco de la haltadproblemo estas esence diagonala argumento.
Ankaŭ, diagonaligo estis origine utiligita por montri la ekziston de propraaŭtoritate malmolaj kompleksecklasoj kaj ludis ŝlosilan rolon en fruaj provoj pruvi P ne korespondas al NP.
#000028
Ĉi-supra pruvo malsukcesas por tiu de W. V. Quine
" Nova fundamento- " aroteorio (NF).
En NF, la naiva aksiomskemo de kompreno estas modifita por eviti la paradoksojn lanĉante specon de "lokan" teorion de tipoj.
#000029
estas ne aro - t.e., ne kontentigas la aksiomskemon.
Aliflanke, ni eble provos krei modifitan diagonalan argumenton rimarkante tion
#000030
koincidas kun la modifita diagonala metis, supre.
#000032
Estas ne eble meti P 1 ( S) en unu-al-unun rilaton kun S, ĉar la du havas malsamajn tipojn, kaj tiel ajnaj funkcias tiel difinitaj malobservus la klasifikadregulojn por la komprenskemo.
#000033
Disputo pri la teorio de Cantor
#000034
La leĝoj de De Morgan
#000037
Povo de aro ( granda)
#000038
En matematiko, la diagonala argumento de Cantor estas pruvo ke ekzistas malfiniaj aroj, kiuj ne povas esti en bijekcia rilato kun la malfinia aro de naturaj nombroj. Ĉi tiaj aroj estas nekalkuleblaj aroj, iliaj kardinalecoj estas pli grandaj ol kardinaleco de la aro de naturaj nombroj.
#000039
La diagonala argumento estis publikigita de Georg Cantor en 1891. Ĝ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, ĝi demonstracias povan kaj ĝeneralan manieron kiu estas uzata en larĝa limigo de pruvoj, ankaŭ 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.
#000040
La originala pruvo konsideras malfiniajn vicojn de formo (x1, x2, x3, ...) kie ĉiu ero xi estas 0 aŭ 1.
#000041
Konsideru ĉiun kalkuleblan liston de iuj el ĉi tiuj vicoj, ekzemple:
#000042
kio estas ke sn, m estas la m-a ero de la n-a vico de la listo.
#000043
Eblas konstrui vicon de eroj s0 tian, ke ĝia unua ero estas malsama de la unua ero de la unua vico en la listo, ĝia dua ero estas malsama de la dua ero de la dua vico de la listo, kaj, ĝenerale, ĝ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:
#000044
La eroj s1,1, s2,2, s3,3, ..., laŭ kiuj estas la konstruado, estas situantaj laŭ diagonalo de la tabelo, de kie aperis la nomo "diagonala argumento".
#000045
Tiel la nova vico s0 estas malsama de ĉiuj vicoj en la listo, ĉar ĝi estas malsama de ĉiu vico si je almenaŭ unu ero s0, i≠si, i.
#000046
De ĉi tio sekvas ke la aro T, konsistanta el ĉiuj malfiniaj vicoj de 0 kaj 1, ne povas esti metita en kalkulebla listo s1, s2, s3, .... Alie, ĝi devus ebli per la pli supre priskribita procezo konstrui vicon s0, kiu devus esti en T (ĉar ĝi estas vico de 0 kaj 1 kiu estas en T laŭ la difino de T) kaj samtempe ne en T (ĉar oni povas intence konstrui ĝi tiel ke ĝi ne estas en la listo).
#000047
Pro tio T ne povas esti en bijekcia (unu al unu) rilato kun la naturaj nombroj. En aliaj vortoj, ĝi estas nekalkulebla.
#000048
Naive, oni povus konsideri malfiniajn duumajn vicojn de 0 kaj 1 kiel duumajn elvolvaĵojn de reelaj nombroj inter 0 kaj 1. Tamen, estas ne-unikeco de malfiniaj elvolvaĵoj en poziciaj nombrosistemoj, kio signifas ke ĉ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 ĉe komparo de ili kiel reelaj nombroj.
#000049
Pli ĝenerale, la maniero povas labori kun ĉiu nombra bazo b≥3. Por la nombroj ri oni devas elekti prezentojn ne finiĝatajn je malfinia ĉ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 ĉiam malsama de la cifero en la diagonalo, kaj la cifero b-1 devas esti neuzata.
#000051
Ekzemple en dekuma sistemo estu:
#000052
En la nova nombro cifero estu 4 se la fonta cifero estas 5, kaj 5 en la ceteraj okazoj:
#000053
Ĝeneraligita formo de la diagonala argumento estis uzata de Cantor por pruvi teoremon de Cantor: por ĉiu aro S la aro de ĉiuj subaroj de S estas pli granda ol S mem. Ĉi tiu pruvo procedas kiel sekvas:
#000054
Estu f esti ĉiu funkcio de S al ĝia aro de ĉiuj subaroj P(S). Sufiĉ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:
#000055
Por ĉiu s en S, s estas en T aŭ ne. Se s estas en T, do laŭ 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).
#000056