Перегляд вихідного коду сторінки Діагональний метод Кантора

[[Файл:Diagonal_argument_01_svg.svg|праворуч|міні|325x325пкс|Ілюстрація діагонального аргументу&nbsp; Кантора існування [[Незліченна множина|незліченних множин]]. Послідовність ''s'' не може входити у наведений перелік послідовностей.]]
[[Файл:Aplicación_2_inyectiva_sobreyectiva02.svg|міні|Бієкція ''f''(''x'') = 2''x'' із натуральних ''у'' парні числа показує, що [[нескінченна множина]] може мати однакову [[Потужність множини|потужність]] із точною [[Підмножина|підмножиною]] себе самої. Однак, діагональний метод Кантора показує, що  існують нескінченні множини різних потужностей.]]
У [[Теорія множин|теорії множин]], '''Діагональний метод Кантора '''або''' діагональний аргумент Кантора''', також відомий як '''метод діагоналізації''', був опублікований у 1891 році [[Георг Кантор|Георгом Кантором]] як [[Доведення|математичний доказ]] того, що існують [[Нескінченна множина|нескінченні множини]] для котрих не існує [[Бієкція|взаємно однозначної відповідності]] з нескінченною множиною [[Натуральні числа|натуральних чисел]]<ref>{{cite journal |author=Georg Cantor |title=Ueber eine elementare Frage der Mannigfaltigkeitslehre |journal={{li|Jahresbericht der Deutschen Mathematiker-Vereinigung||Q15758635}} 1890—1891 |volume=1 |pages=75–78 |year=1891 |url=https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi |accessdate=18 серпня 2018 |archive-date=15 квітня 2019 |archive-url=https://web.archive.org/web/20190415082519/https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi }} Англійський переклад: {{cite book |last=Ewald |first=William B. (ed.) |title=From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2 |publisher=Oxford University Press |pages=920–922 |year=1996 |isbn=0-19-850536-1}}</ref><ref name="Simmons1993">{{Cite book|url=https://books.google.com/books?id=wEj3Spept0AC&pg=PA20|title=Universality and the Liar: An Essay on Truth and the Diagonal Argument|last=Keith Simmons|date=30 липня 1993|publisher=Cambridge University Press|pages=20–|isbn=978-0-521-43069-2|accessdate=18 серпня 2018|archive-date=4 листопада 2020|archive-url=https://web.archive.org/web/20201104203828/https://books.google.com/books?id=wEj3Spept0AC&pg=PA20}}</ref><ref name="Rubin1976">{{Cite book|title=Principles of Mathematical Analysis|last=Rudin|first=Walter|date=1976|publisher=McGraw-Hill|edition=3rd|location=New York|page=[https://archive.org/details/principlesofmath00rudi/page/30 30]|isbn=0070856133|url=https://archive.org/details/principlesofmath00rudi/page/30}}</ref>. Такі множини тепер називають [[Незліченна множина|незліченними множинами]], і розміри незліченних множин вивчає теорія [[Кардинальне число|кардинальних чисел]], започаткована Кантором.

Кантор {{нп|Перше доведення незліченності Кантора|вперше довів|en|Cantor's first uncountability proof}} незліченність [[Дійсне число|дійсних чисел]] у 1874 році іншим методом, відмінним від діагонального<ref>{{Citation|title=Georg Cantor and Transcendental Numbers|url=http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Gray819-832.pdf|year=1994|surname=Gray|given=Robert|journal=[[The American Mathematical Monthly|American Mathematical Monthly]]|volume=101|issue=9|pages=819–832|doi=10.2307/2975129|jstor=2975129|accessdate=18 серпня 2018|archive-date=21 січня 2022|archive-url=https://web.archive.org/web/20220121155859/https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Gray819-832.pdf}}</ref><ref name="Bloch2011">{{Cite book|title=The Real Numbers and Real Analysis|url=https://archive.org/details/realnumbersreala00edbl|last=Bloch|first=Ethan D.|date=2011|publisher=Springer|location=New York|page=[https://archive.org/details/realnumbersreala00edbl/page/n458 429]|isbn=978-0-387-72176-7}}</ref>. Однак діагональний метод є потужним і універсальним способом, що був відтоді використаний у широкому діапазоні доведень<ref>{{Cite book|url=https://books.google.com/books?id=RXzsAwAAQBAJ|title=The Logic of Infinity|last=Sheppard|first=Barnaby|year=2014|publisher=Cambridge University Press|edition=illustrated|page=73|isbn=978-1-107-05831-6|accessdate=18 серпня 2018|archive-date=13 серпня 2020|archive-url=https://web.archive.org/web/20200813063035/https://books.google.com/books?id=RXzsAwAAQBAJ}}</ref>, включаючи першу [[Теореми Геделя про неповноту|теорему Геделя про неповноту]] і [[Теза Черча — Тюрінга|тезу Черча&nbsp;— Тюрінга]]. Аргументи діагоналізації також часто є джерелом суперечностей, таких як [[Парадокс Расселла|парадокс Рассела]]<ref>{{Cite web|url=http://plato.stanford.edu/entries/russell-paradox|title=Russell's paradox|publisher=Stanford encyclopedia of philosophy|accessdate=18 серпня 2018|archive-date=12 серпня 2018|archive-url=https://web.archive.org/web/20180812013851/https://plato.stanford.edu/entries/russell-paradox/}}</ref><ref>{{Cite book|title=Principles of mathematics|last=Bertrand Russell|year=1931|publisher=Norton|pages=363–366}}</ref> і {{Не перекладено|парадокс Рішара|||Richard's paradox}}<ref>{{Cite book|url=https://books.google.com/books?id=wEj3Spept0AC&pg=PA20|title=Universality and the Liar: An Essay on Truth and the Diagonal Argument|last=Keith Simmons|date=30 липня 1993|publisher=Cambridge University Press|page=27|isbn=978-0-521-43069-2|accessdate=18 серпня 2018|archive-date=4 листопада 2020|archive-url=https://web.archive.org/web/20201104203828/https://books.google.com/books?id=wEj3Spept0AC&pg=PA20}}</ref>.

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

: Якщо ''s''<sub>1</sub>, ''s''<sub>2</sub>, … , ''s''<sub>''n''</sub>, … є довільним переліком елементів із ''T'', то завжди існує елемент ''s'' із ''T'' якому не відповідає жоден елемент ''s''<sub>''n''</sub> у переліку.

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

: {|
|''s''<sub>1</sub> =
|(0,
|0,
|0,
|0,
|0,
|0,
|0,
|...)
|-
|''s''<sub>2</sub> =
|(1,
|1,
|1,
|1,
|1,
|1,
|1,
|...)
|-
|''s''<sub>3</sub> =
|(0,
|1,
|0,
|1,
|0,
|1,
|0,
|...)
|-
|''s''<sub>4</sub> =
|(1,
|0,
|1,
|0,
|1,
|0,
|1,
|...)
|-
|''s''<sub>5</sub> =
|(1,
|1,
|0,
|1,
|0,
|1,
|1,
|...)
|-
|''s''<sub>6</sub> =
|(0,
|0,
|1,
|1,
|0,
|1,
|1,
|...)
|-
|''s''<sub>7</sub> =
|(1,
|0,
|0,
|0,
|1,
|0,
|0,
|...)
|-
|...
|}

Далі, послідовність ''s'' будується вибираючи {{nobr|1-шу}} цифру [[Обернений код|оберненою]] до {{nobr|1-ї}} цифри ''s''<sub>''1''</sub> (замінюючи '''0''' на '''1''' і навпаки), {{nobr|2-гу}} цифру оберненою до {{nobr|2-ї}} цифри ''s''<sub>''2''</sub>, {{nobr|3-тю}} цифру оберненою до {{nobr|3-ї}} цифри ''s''<sub>''3''</sub>, і загалом для кожного ''n'', {{nobr|''n-та''}} цифра ''s'' є  оберненою до {{nobr|''n-тої''}} цифри ''s''<sub>''n''</sub>. Для прикладу вище отримаємо:

: {|
|''s''<sub>1</sub>
|=
|(<u>'''0'''</u>,
|0,
|0,
|0,
|0,
|0,
|0,
|...)
|-
|''s''<sub>2</sub>
|=
|(1,
|<u>'''1'''</u>,
|1,
|1,
|1,
|1,
|1,
|...)
|-
|''s''<sub>3</sub>
|=
|(0,
|1,
|<u>'''0'''</u>,
|1,
|0,
|1,
|0,
|...)
|-
|''s''<sub>4</sub>
|=
|(1,
|0,
|1,
|<u>'''0'''</u>,
|1,
|0,
|1,
|...)
|-
|''s''<sub>5</sub>
|=
|(1,
|1,
|0,
|1,
|<u>'''0'''</u>,
|1,
|1,
|...)
|-
|''s''<sub>6</sub>
|=
|(0,
|0,
|1,
|1,
|0,
|<u>'''1'''</u>,
|1,
|...)
|-
|''s''<sub>7</sub>
|=
|(1,
|0,
|0,
|0,
|1,
|0,
|<u>'''0'''</u>,
|...)
|-
|...
|-
|-
|''s''
|=
|(<u>'''1'''</u>,
|<u>'''0'''</u>,
|<u>'''1'''</u>,
|<u>'''1'''</u>,
|<u>'''1'''</u>,
|<u>'''0'''</u>,
|<u>'''1'''</u>,
|...)
|}

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

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

: Множина ''T'' є незліченною.

Доведення починається із припущення, що ''T'' [[Зліченна множина|зліченна]]. Тоді всі її елементи можуть бути записані як перелік ''s''<sub>1</sub>, ''s''<sub>2</sub>, … , ''s''<sub>''n''</sub>, … . Використання попередньої теореми до цього переліку дає елемент ''s'', який не належить до переліку. Але, це суперечить тому, що ''s'' є елементом ''T'' і тому належить до переліку. Із суперечності випливає, що первісне припущення хибне. Отже, ''T'' незліченна.

=== Дійсні числа ===
Незліченність [[Дійсне число|дійсних чисел]] вже була встановлена {{нп|Перше доведення незліченності Кантора|першим доведенням незліченності Кантора|en|Cantor's first uncountability proof}}, але вона також випливає із попереднього результату. Для доведення цього будується [[Ін'єкція (математика)|ін'єкція]] ''f'' з множини ''T'' нескінченних двійкових рядків у множину '''R''' дійних чисел. Оскільки ''T'' є незліченною, то [[Образ відображення|образ]] цієї функції ''f'', який є підмножиною '''R''', теж незліченний. Отже, множина '''R''' теж є незліченною. Також Кантор запропонував спосіб побудови [[Бієкція|бієкції]] між ''T'' і '''R'''. Отже, ''T'' і '''R''' мають однакову потужність, яка називається "потужністю континууму" і зазвичай позначається <math>\mathfrak{c}</math><math>2^{\aleph_0}</math>.

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

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

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

: ''T'' = { ''s'' ∈ ''S'': ''s'' ∉ ''f''(''s'') }.

Для кожного ''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'' приводить до  [[Континуум-гіпотеза|узагальненої континуум-гіпотези]].

== Примітки ==
<references />

== Зовнішні посилання ==

* [http://www.mathpages.com/home/kmath371.htm Cantor's Diagonal Proof] на MathPages
* {{MathWorld|title=Cantor Diagonal Method}}

{{Теорія множин}}
{{Математична логіка}}

[[Категорія:Аргументи]]
[[Категорія:Потужність множин]]
[[Категорія:Нескінченність]]
[[Категорія:Теорія множин]]
[[Категорія:Теореми засад математики]]