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