www.wikidata.uk-ua.nina.az

Діагональний метод Кантора У теорії множин абодіагональний аргумент Кантора також відомий як метод діагоналізації був оп

Діагональний метод Кантора

У теорії множин, Діагональний метод Кантора або діагональний аргумент Кантора, також відомий як метод діагоналізації, був опублікований у 1891 році Георгом Кантором як математичний доказ того, що існують нескінченні множини для котрих не існує взаємно однозначної відповідності з нескінченною множиною натуральних чисел. Такі множини тепер називають незліченними множинами, і розміри незліченних множин вивчає теорія кардинальних чисел, започаткована Кантором.

Ілюстрація діагонального аргументу  Кантора існування незліченних множин. Послідовність s не може входити у наведений перелік послідовностей.
Бієкція f(x) = 2x із натуральних у парні числа показує, що нескінченна множина може мати однакову потужність із точною підмножиною себе самої. Однак, діагональний метод Кантора показує, що  існують нескінченні множини різних потужностей.

Кантор вперше довів[en] незліченність дійсних чисел у 1874 році іншим методом, відмінним від діагонального. Однак діагональний метод є потужним і універсальним способом, що був відтоді використаний у широкому діапазоні доведень, включаючи першу теорему Геделя про неповноту і тезу Черча — Тюрінга. Аргументи діагоналізації також часто є джерелом суперечностей, таких як парадокс Рассела і парадокс Рішара[en].

Незліченна множина ред.

У статті 1891 року Кантор розглянув множину T усіх нескінченних послідовностей двійкових чисел (тобто кожна цифра числа є нулем або одиницею). Він почав із конструктивного доведення такої теореми:

Доведення починається із перелічення усіх елементів із T, наприклад:

Далі, послідовність s будується вибираючи 1-шу цифру оберненою до 1-ї цифри s1 (замінюючи 0 на 1 і навпаки), 2-гу цифру оберненою до 2-ї цифри s2, 3-тю цифру оберненою до 3-ї цифри s3, і загалом для кожного n, n-та цифра s є  оберненою до n-тої цифри sn. Для прикладу вище отримаємо:

За побудовою, s відрізняється від кожного sn, оскільки їхні n-ті цифри відрізняються (підсвічені у прикладі). Тому s не може бути у переліку.

На основі цієї теореми, використовуючи доведення від супротивного Кантор показує, що:

Доведення починається із припущення, що T зліченна. Тоді всі її елементи можуть бути записані як перелік s1, s2, … , sn, … . Використання попередньої теореми до цього переліку дає елемент s, який не належить до переліку. Але, це суперечить тому, що s є елементом T і тому належить до переліку. Із суперечності випливає, що первісне припущення хибне. Отже, T незліченна.

Дійсні числа ред.

Незліченність дійсних чисел вже була встановлена першим доведенням незліченності Кантора[en], але вона також випливає із попереднього результату. Для доведення цього будується ін'єкція f з множини T нескінченних двійкових рядків у множину R дійних чисел. Оскільки T є незліченною, то образ цієї функції f, який є підмножиною R, теж незліченний. Отже, множина R теж є незліченною. Також Кантор запропонував спосіб побудови бієкції між T і R. Отже, T і R мають однакову потужність, яка називається "потужністю континууму" і зазвичай позначається .

Ін'єкція з T у R визначається відображенням рядків із T у десяткові числа, наприклад t = 0111… у число 0.0111…. ця функція визначена як f(t) = 0.t, є ін'єкцією, оскільки відображає різні рядки у різні числа.

Узагальнення для множин ред.

Кантор використав узагальнену форму діагонального аргументу щоби довести Теорему Кантора: для кожної множини S, булеан S — тобто, множина всіх підмножин S (позначена як P(S))—має більшу потужність ніж сама S. Доведення відбувається так:

Нехай f буде будь-якою функцією із S у P(S). досить довести, що f не може бути сюр'єкцією. Це значить що деякий елемент T із P(S), тобто деяка підмножина S, не лежить в образі f. Розглянемо таку множину:

Для кожного s із S, або s належить T або ні. Якщо s належить T, то за визначенням T, s не належить f(s), тобто T не дорівнює f(s). З іншої сторони, якщо s не належить T, то за визначенням T, s належить f(s), тобто знову T не дорівнює f(s).

Наслідки ред.

Із цього випливає що поняття множини всіх множин є суперечливим. Якби S була множиною всіх множин, то P(S) була б одночасно більшою за S і підмножиною S.

Парадокс Рассела показав, що наївна теорія множин, що базується на аксіомній схемі необмеженого розуміння, є суперечливою. 

Діагональний метод показує, що множина дійсних чисел більша за множину натуральних (і разом цілих та раціональних). Отже, можна запитати чи існує множина потужність якої посередині між потужністю цілих і дійсних чисел. Це питання приводить до континуум-гіпотези. Аналогічно, питання чи існує множина з потужністю між  |S| і |P(S)| для деякої нескінченної S приводить до  узагальненої континуум-гіпотези.

Примітки ред.

  1. Georg Cantor (1891). . Jahresbericht der Deutschen Mathematiker-Vereinigung[en] 1890—1891 1: 75–78. Архів оригіналу за 15 квітня 2019. Процитовано 18 серпня 2018.  Англійський переклад: Ewald, William B. (ed.) (1996). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2. Oxford University Press. с. 920–922. ISBN 0-19-850536-1. 
  2. Keith Simmons (30 липня 1993). . Cambridge University Press. с. 20–. ISBN 978-0-521-43069-2. Архів оригіналу за 4 листопада 2020. Процитовано 18 серпня 2018. 
  3. Rudin, Walter (1976). Principles of Mathematical Analysis (вид. 3rd). New York: McGraw-Hill. с. 30. ISBN 0070856133. 
  4. Gray, Robert (1994). . American Mathematical Monthly 101 (9): 819–832. JSTOR 2975129. doi:10.2307/2975129. Архів оригіналу за 21 січня 2022. Процитовано 18 серпня 2018. 
  5. Bloch, Ethan D. (2011). The Real Numbers and Real Analysis. New York: Springer. с. 429. ISBN 978-0-387-72176-7. 
  6. Sheppard, Barnaby (2014). (вид. illustrated). Cambridge University Press. с. 73. ISBN 978-1-107-05831-6. Архів оригіналу за 13 серпня 2020. Процитовано 18 серпня 2018. 
  7. . Stanford encyclopedia of philosophy. Архів оригіналу за 12 серпня 2018. Процитовано 18 серпня 2018. 
  8. Bertrand Russell (1931). Principles of mathematics. Norton. с. 363–366. 
  9. Keith Simmons (30 липня 1993). . Cambridge University Press. с. 27. ISBN 978-0-521-43069-2. Архів оригіналу за 4 листопада 2020. Процитовано 18 серпня 2018. 

Зовнішні посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U teoriyi mnozhin Diagonalnij metod Kantoraabodiagonalnij argument Kantora takozh vidomij yak metod diagonalizaciyi buv opublikovanij u 1891 roci Georgom Kantorom yak matematichnij dokaz togo sho isnuyut neskinchenni mnozhini dlya kotrih ne isnuye vzayemno odnoznachnoyi vidpovidnosti z neskinchennoyu mnozhinoyu naturalnih chisel 1 2 3 Taki mnozhini teper nazivayut nezlichennimi mnozhinami i rozmiri nezlichennih mnozhin vivchaye teoriya kardinalnih chisel zapochatkovana Kantorom Ilyustraciya diagonalnogo argumentu Kantora isnuvannya nezlichennih mnozhin Poslidovnist s ne mozhe vhoditi u navedenij perelik poslidovnostej Biyekciya f x 2x iz naturalnih u parni chisla pokazuye sho neskinchenna mnozhina mozhe mati odnakovu potuzhnist iz tochnoyu pidmnozhinoyu sebe samoyi Odnak diagonalnij metod Kantora pokazuye sho isnuyut neskinchenni mnozhini riznih potuzhnostej Kantor vpershe doviv en nezlichennist dijsnih chisel u 1874 roci inshim metodom vidminnim vid diagonalnogo 4 5 Odnak diagonalnij metod ye potuzhnim i universalnim sposobom sho buv vidtodi vikoristanij u shirokomu diapazoni doveden 6 vklyuchayuchi pershu teoremu Gedelya pro nepovnotu i tezu Chercha Tyuringa Argumenti diagonalizaciyi takozh chasto ye dzherelom superechnostej takih yak paradoks Rassela 7 8 i paradoks Rishara en 9 Zmist 1 Nezlichenna mnozhina 1 1 Dijsni chisla 2 Uzagalnennya dlya mnozhin 2 1 Naslidki 3 Primitki 4 Zovnishni posilannyaNezlichenna mnozhina red U statti 1891 roku Kantor rozglyanuv mnozhinu T usih neskinchennih poslidovnostej dvijkovih chisel tobto kozhna cifra chisla ye nulem abo odiniceyu Vin pochav iz konstruktivnogo dovedennya takoyi teoremi Yaksho s1 s2 sn ye dovilnim perelikom elementiv iz T to zavzhdi isnuye element s iz T yakomu ne vidpovidaye zhoden element sn u pereliku Dovedennya pochinayetsya iz perelichennya usih elementiv iz T napriklad s1 0 0 0 0 0 0 0 s2 1 1 1 1 1 1 1 s3 0 1 0 1 0 1 0 s4 1 0 1 0 1 0 1 s5 1 1 0 1 0 1 1 s6 0 0 1 1 0 1 1 s7 1 0 0 0 1 0 0 Dali poslidovnist s buduyetsya vibirayuchi 1 shu cifru obernenoyu do 1 yi cifri s1 zaminyuyuchi 0 na 1 i navpaki 2 gu cifru obernenoyu do 2 yi cifri s2 3 tyu cifru obernenoyu do 3 yi cifri s3 i zagalom dlya kozhnogo n n ta cifra s ye obernenoyu do n toyi cifri sn Dlya prikladu vishe otrimayemo s1 0 0 0 0 0 0 0 s2 1 1 1 1 1 1 1 s3 0 1 0 1 0 1 0 s4 1 0 1 0 1 0 1 s5 1 1 0 1 0 1 1 s6 0 0 1 1 0 1 1 s7 1 0 0 0 1 0 0 s 1 0 1 1 1 0 1 Za pobudovoyu s vidriznyayetsya vid kozhnogo sn oskilki yihni n ti cifri vidriznyayutsya pidsvicheni u prikladi Tomu s ne mozhe buti u pereliku Na osnovi ciyeyi teoremi vikoristovuyuchi dovedennya vid suprotivnogo Kantor pokazuye sho Mnozhina T ye nezlichennoyu Dovedennya pochinayetsya iz pripushennya sho T zlichenna Todi vsi yiyi elementi mozhut buti zapisani yak perelik s1 s2 sn Vikoristannya poperednoyi teoremi do cogo pereliku daye element s yakij ne nalezhit do pereliku Ale ce superechit tomu sho s ye elementom T i tomu nalezhit do pereliku Iz superechnosti viplivaye sho pervisne pripushennya hibne Otzhe T nezlichenna Dijsni chisla red Nezlichennist dijsnih chisel vzhe bula vstanovlena pershim dovedennyam nezlichennosti Kantora en ale vona takozh viplivaye iz poperednogo rezultatu Dlya dovedennya cogo buduyetsya in yekciya f z mnozhini T neskinchennih dvijkovih ryadkiv u mnozhinu R dijnih chisel Oskilki T ye nezlichennoyu to obraz ciyeyi funkciyi f yakij ye pidmnozhinoyu R tezh nezlichennij Otzhe mnozhina R tezh ye nezlichennoyu Takozh Kantor zaproponuvav sposib pobudovi biyekciyi mizh T i R Otzhe T i R mayut odnakovu potuzhnist yaka nazivayetsya potuzhnistyu kontinuumu i zazvichaj poznachayetsya c displaystyle mathfrak c nbsp 2 ℵ 0 displaystyle 2 aleph 0 nbsp In yekciya z T u R viznachayetsya vidobrazhennyam ryadkiv iz T u desyatkovi chisla napriklad t 0111 u chislo 0 0111 cya funkciya viznachena yak f t 0 t ye in yekciyeyu oskilki vidobrazhaye rizni ryadki u rizni chisla Uzagalnennya dlya mnozhin red Kantor vikoristav uzagalnenu formu diagonalnogo argumentu shobi dovesti Teoremu Kantora dlya kozhnoyi mnozhini S bulean S tobto mnozhina vsih pidmnozhin S poznachena yak P S maye bilshu potuzhnist nizh sama S Dovedennya vidbuvayetsya tak Nehaj f bude bud yakoyu funkciyeyu iz S u P S dosit dovesti sho f ne mozhe buti syur yekciyeyu Ce znachit sho deyakij element T iz P S tobto deyaka pidmnozhina S ne lezhit v obrazi f Rozglyanemo taku mnozhinu T s S s f s Dlya kozhnogo s iz S abo s nalezhit T abo ni Yaksho s nalezhit T to za viznachennyam T s ne nalezhit f s tobto T ne dorivnyuye f s Z inshoyi storoni yaksho s ne nalezhit T to za viznachennyam T s nalezhit f s tobto znovu T ne dorivnyuye f s Naslidki red Iz cogo viplivaye sho ponyattya mnozhini vsih mnozhin ye superechlivim Yakbi S bula mnozhinoyu vsih mnozhin to P S bula b odnochasno bilshoyu za S i pidmnozhinoyu S Paradoks Rassela pokazav sho nayivna teoriya mnozhin sho bazuyetsya na aksiomnij shemi neobmezhenogo rozuminnya ye superechlivoyu Diagonalnij metod pokazuye sho mnozhina dijsnih chisel bilsha za mnozhinu naturalnih i razom cilih ta racionalnih Otzhe mozhna zapitati chi isnuye mnozhina potuzhnist yakoyi poseredini mizh potuzhnistyu cilih i dijsnih chisel Ce pitannya privodit do kontinuum gipotezi Analogichno pitannya chi isnuye mnozhina z potuzhnistyu mizh S i P S dlya deyakoyi neskinchennoyi S privodit do uzagalnenoyi kontinuum gipotezi Primitki red Georg Cantor 1891 Ueber eine elementare Frage der Mannigfaltigkeitslehre Jahresbericht der Deutschen Mathematiker Vereinigung en 1890 1891 1 75 78 Arhiv originalu za 15 kvitnya 2019 Procitovano 18 serpnya 2018 Anglijskij pereklad Ewald William B ed 1996 From Immanuel Kant to David Hilbert A Source Book in the Foundations of Mathematics Volume 2 Oxford University Press s 920 922 ISBN 0 19 850536 1 Keith Simmons 30 lipnya 1993 Universality and the Liar An Essay on Truth and the Diagonal Argument Cambridge University Press s 20 ISBN 978 0 521 43069 2 Arhiv originalu za 4 listopada 2020 Procitovano 18 serpnya 2018 Rudin Walter 1976 Principles of Mathematical Analysis vid 3rd New York McGraw Hill s 30 ISBN 0070856133 Gray Robert 1994 Georg Cantor and Transcendental Numbers American Mathematical Monthly 101 9 819 832 JSTOR 2975129 doi 10 2307 2975129 Arhiv originalu za 21 sichnya 2022 Procitovano 18 serpnya 2018 Bloch Ethan D 2011 The Real Numbers and Real Analysis New York Springer s 429 ISBN 978 0 387 72176 7 Sheppard Barnaby 2014 The Logic of Infinity vid illustrated Cambridge University Press s 73 ISBN 978 1 107 05831 6 Arhiv originalu za 13 serpnya 2020 Procitovano 18 serpnya 2018 Russell s paradox Stanford encyclopedia of philosophy Arhiv originalu za 12 serpnya 2018 Procitovano 18 serpnya 2018 Bertrand Russell 1931 Principles of mathematics Norton s 363 366 Keith Simmons 30 lipnya 1993 Universality and the Liar An Essay on Truth and the Diagonal Argument Cambridge University Press s 27 ISBN 978 0 521 43069 2 Arhiv originalu za 4 listopada 2020 Procitovano 18 serpnya 2018 Zovnishni posilannya red Cantor s Diagonal Proof na MathPages Weisstein Eric W Cantor Diagonal Method angl na sajti Wolfram MathWorld Otrimano z https uk wikipedia org w index php title Diagonalnij metod Kantora amp oldid 40282402