Диагональный аргумент Кантора

Доказательство в теории множеств

Иллюстрация диагонального аргумента Кантора (в системе счисления 2) для существования несчетных множеств . Последовательность внизу не может встречаться нигде в перечислении последовательностей выше.

Бесконечное множество может иметь ту же мощность , что и его собственное подмножество , как показывает изображенная биекция f ( x )=2 x от натурального числа к четным числам . Тем не менее, существуют бесконечные множества с различной мощностью, как показывает диагональный аргумент Кантора.

Диагональный аргумент Кантора (среди различных похожих названий ^{[примечание 1]} ) является математическим доказательством того, что существуют бесконечные множества , которые нельзя поставить в однозначное соответствие с бесконечным множеством натуральных чисел  – неформально, что существуют множества , которые в некотором смысле содержат больше элементов, чем положительных целых чисел. Такие множества теперь называются несчетными множествами , а размер бесконечных множеств рассматривается теорией кардинальных чисел , которую начал Кантор.

Георг Кантор опубликовал это доказательство в 1891 году, ^{[1] [2] : 20–  [3]} но это было не первое его доказательство несчетности действительных чисел , которое появилось в 1874 году. ^{[4] [5]} Однако оно демонстрирует общую технику, которая с тех пор использовалась в широком диапазоне доказательств, ^[6] включая первую из теорем Гёделя о неполноте ^[2] и ответ Тьюринга на Entscheidungsproblem . Аргументы диагонализации часто также являются источником противоречий, таких как парадокс Рассела ^{[7] [8]} и парадокс Ричарда . ^{[2] : 27}

Несчетное множество

Кантор рассмотрел множество T всех бесконечных последовательностей двоичных цифр (т.е. каждая цифра равна нулю или единице). ^{[примечание 2]} Он начинает с конструктивного доказательства следующей леммы :

Если s ₁ , s ₂ , ... , s _n , ... — это любое перечисление элементов из T , ^{[примечание 3]} то можно построить элемент s из T , который не будет соответствовать ни одному s _n в перечислении.

Доказательство начинается с перечисления элементов из T , например

Далее, последовательность s строится путем выбора 1-й цифры как дополнительной к 1-й цифре s ₁ (замена 0 на 1 и наоборот), 2-й цифры как дополнительной ко 2-й цифре s ₂ , 3-й цифры как дополнительной к 3-й цифре s ₃ , и, как правило, для каждого n , n ^-й цифры как дополнительной к n ^-й цифре s _n . Для приведенного выше примера это дает

По построению s является членом T , который отличается от каждого s _n , поскольку их n ^-ые цифры различаются (выделены в примере). Следовательно, s не может встречаться в перечислении.

Основываясь на этой лемме, Кантор затем использует доказательство от противного, чтобы показать, что:

Множество T несчетно.

Доказательство начинается с предположения, что T счетно . Тогда все его элементы можно записать в перечисление s ₁ , s ₂ , ... , s _n , ... . Применение предыдущей леммы к этому перечислению дает последовательность s , которая является членом T , но не находится в перечислении. Однако, если T перечислено, то каждый член T , включая этот s , находится в перечислении. Это противоречие означает, что исходное предположение ложно. Следовательно, T несчетно. ^[1]

Реальные цифры

Несчетность действительных чисел уже была установлена ​​первым доказательством несчетности Кантора , но она также следует из приведенного выше результата. Чтобы доказать это, будет построена инъекция из множества T бесконечных двоичных строк во множество R действительных чисел. Поскольку T несчетно, образ этой функции, являющийся подмножеством R , несчетен. Следовательно, R несчетно. Также, используя метод построения, разработанный Кантором, будет построена биекция между T и R. Следовательно, T и R имеют одинаковую мощность, которая называется « мощностью континуума » и обычно обозначается или . ${\displaystyle {\mathfrak {c}}}$ ${\displaystyle 2^{\aleph _{0}}}$

Инъекция из T в R осуществляется путем преобразования двоичных строк в T в десятичные дроби , например, путем преобразования t  = 0111... в десятичную дробь 0,0111.... Эта функция, определяемая как f  ( t ) = 0. t , является инъекцией, поскольку она преобразует различные строки в различные числа. ^{[примечание 4]}

Построение биекции между T и R немного сложнее. Вместо того, чтобы отображать 0111... в десятичное 0.0111..., его можно отобразить в число с основанием b : 0.0111... _b . Это приводит к семейству функций: f _b  ( t ) = 0. t _b . Функции f _b ( t )  являются инъекциями, за исключением f ₂ ( t )  . Эта функция будет изменена для создания биекции между T и R .

Общие наборы

Иллюстрация обобщенного диагонального аргумента: множество T = { n ∈ : n ∉ f ( n )} внизу не может встречаться нигде в диапазоне f : → P ( ). Пример отображения f соответствует примеру перечисления s на рисунке выше. ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

Обобщенная форма диагонального аргумента была использована Кантором для доказательства теоремы Кантора : для любого множества S множество мощности S — то есть множество всех подмножеств S (здесь записанное как P ( S )) — не может находиться во взаимно однозначном соответствии с самим S. Это доказательство проводится следующим образом:

Пусть f — любая функция из S в P ( S ). Достаточно доказать, что f не может быть сюръективной . Это означает, что некоторый элемент T из P ( S ), т.е. некоторое подмножество S , не находится в образе f . В качестве кандидата рассмотрим множество:

Т = { 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 ); см. рисунок. Для более полного изложения этого доказательства см. теорему Кантора .

Последствия

Порядок кардиналов

С равенством, определенным как существование биекции между их базовыми множествами, Кантор также определяет бинарный предикат мощностей и в терминах существования инъекций между и . Он обладает свойствами предпорядка и здесь записывается как " ". Можно встроить натуральные числа в бинарные последовательности, тем самым явно доказав различные утверждения о существовании инъекций , так что в этом смысле , где обозначает функциональное пространство . Но, следуя из аргумента в предыдущих разделах, нет сюръекции и, следовательно, нет и биекции, т. е. множество несчетно. Для этого можно написать , где " " понимается как означающее существование инъекции вместе с доказанным отсутствием биекции (в отличие от альтернатив, таких как отрицание предпорядка Кантора или определение в терминах назначенных ординалов ). Также в этом смысле, как было показано, и в то же время это имеет место, что , для всех множеств . ${\displaystyle |S|}$ ${\displaystyle |T|}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle \leq }$ ${\displaystyle |{\mathbb {N} }|\leq |2^{\mathbb {N} }|}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }\to \{0,1\}}$ ${\displaystyle |{\mathbb {N} }|<|2^{\mathbb {N} }|}$ ${\displaystyle <}$ ${\displaystyle |S|<|{\mathcal {P}}(S)|}$ ${\displaystyle \neg (|{\mathcal {P}}(S)|\leq |S|)}$ ${\displaystyle S}$

Предполагая закон исключенного третьего , характеристические функции сюръективны на множествах степеней, а затем . Таким образом, несчетное также не является перечислимым и также может быть отображено на . Классически теорема Шредера–Бернштейна верна и гласит, что любые два множества, которые находятся в инъективном образе друг друга, также находятся в биекции. Здесь каждое неограниченное подмножество тогда находится в биекции с самим собой, и каждое подсчетное множество (свойство в терминах сюръекций) тогда уже счетно, т. е. находится в сюръективном образе . В этом контексте возможности затем исчерпываются, делая " " нестрогим частичным порядком или даже полным порядком при предположении выбора . Таким образом, диагональный аргумент устанавливает, что, хотя оба рассматриваемых множества бесконечны, на самом деле существует больше бесконечных последовательностей единиц и нулей, чем натуральных чисел. Результат Кантора также подразумевает, что понятие множества всех множеств противоречиво: если бы было множеством всех множеств, то было бы одновременно больше и подмножеством . ${\displaystyle |2^{S}|=|{\mathcal {P}}(S)|}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle \leq }$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}(S)}$ ${\displaystyle S}$ ${\displaystyle S}$

При отсутствии исключенного третьего

Также в конструктивной математике нет сюръекции из полной области на пространство функций или на набор подмножеств , то есть эти два набора несчетны. Снова используя " " для доказанного существования инъекции в сочетании с отсутствием биекции, имеем и . Далее, , как было отмечено ранее. Аналогично, , и конечно , также в конструктивной теории множеств . ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle {\mathcal {P}}({\mathbb {N} })}$ ${\displaystyle <}$ ${\displaystyle {\mathbb {N} }<2^{\mathbb {N} }}$ ${\displaystyle S<{\mathcal {P}}(S)}$ ${\displaystyle \neg ({\mathcal {P}}(S)\leq S)}$ ${\displaystyle 2^{\mathbb {N} }\leq {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle 2^{S}\leq {\mathcal {P}}(S)}$ ${\displaystyle S\leq S}$

Однако конструктивно упорядочить порядковые и кардинальные числа сложнее или невозможно. Например, теорема Шредера–Бернштейна требует закона исключенного третьего. ^[10] Фактически, стандартное упорядочение действительных чисел, расширяющее упорядочение рациональных чисел, также не обязательно разрешимо. Также не разрешимы большинство свойств интересных классов функций по теореме Райса , то есть множество счетных чисел для подсчетных множеств может не быть рекурсивным и, таким образом, не быть счетным. Сложная совокупность подмножеств множества конструктивно не заменяется совокупностью его характеристических функций. В ином конструктивном контексте (в котором закон исключенного третьего не принимается как аксиома) последовательно принимать неклассические аксиомы, которые противоречат следствиям закона исключенного третьего. Несчетные множества, такие как или могут быть заявлены как подсчетные . ^{[11] [12]} Это понятие размера, которое является избыточным в классическом контексте, но в остальном не обязательно подразумевает счетность. Существование инъекций из несчетного или в здесь также возможно. ^[13] Таким образом, кардинальное отношение не может быть антисимметричным . Следовательно, также при наличии множеств функционального пространства, которые даже классически несчетны, интуиционисты не принимают это отношение как составляющее иерархию трансфинитных размеров. ^[14] Когда аксиома powerset не принимается, в конструктивной структуре даже подсчетность всех множеств тогда является последовательной. При всем при этом, в общих теориях множеств несуществование множества всех множеств также уже следует из предикативного разделения . ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }}$

В теории множеств моделируются теории математики . Более слабые логические аксиомы означают меньше ограничений и, таким образом, допускают более богатый класс моделей. Множество может быть идентифицировано как модель поля действительных чисел , когда оно удовлетворяет некоторым аксиомам действительных чисел или их конструктивной перефразировке . Были изучены различные модели, такие как числа Коши или числа Дедекинда , среди прочих. Первые относятся к факторам последовательностей, в то время как последние являются хорошо ведущими себя разрезами, взятыми из множества сил, если они существуют. При наличии исключенного третьего все они изоморфны и несчетны. В противном случае варианты действительных чисел Дедекинда могут быть счетными ^[15] или вводиться в натуральные числа, но не совместно. При предположении счетного выбора конструктивные действительные числа Коши даже без явного модуля сходимости тогда являются полными по Коши ^[16], а действительные числа Дедекинда упрощаются так, чтобы стать им изоморфными. Действительно, здесь выбор также способствует диагональным построениям, и при его допущении полные по Коши модели действительных чисел несчетны.

Открытые вопросы

Мотивированный пониманием того, что множество действительных чисел «больше», чем множество натуральных чисел, мы задаемся вопросом, существует ли множество, мощность которого находится «между» мощностью целых чисел и мощностью действительных чисел. Этот вопрос приводит к знаменитой гипотезе континуума . Аналогично, вопрос о том, существует ли множество, мощность которого находится между | S | и | P ( S )| для некоторого бесконечного S, приводит к обобщенной гипотезе континуума .

Диагонализация в более широком контексте

Парадокс Рассела показал, что теория множеств, включающая неограниченную схему понимания , противоречива. Обратите внимание, что существует сходство между конструкцией T и множеством в парадоксе Рассела. Поэтому, в зависимости от того, как мы изменяем аксиоматическую схему понимания, чтобы избежать парадокса Рассела, такие аргументы, как несуществование множества всех множеств, могут оставаться или не оставаться верными.

Аналоги диагонального аргумента широко используются в математике для доказательства существования или несуществования определенных объектов. Например, общепринятое доказательство неразрешимости проблемы остановки по сути является диагональным аргументом. Кроме того, диагонализация изначально использовалась для доказательства существования произвольно сложных классов сложности и играла ключевую роль в ранних попытках доказать, что P не равно NP .

Версия для новых основ Куайна

Вышеприведенное доказательство не работает для теории множеств (NF) " Новых оснований " У. В. Куайна . В NF наивная аксиоматическая схема понимания модифицируется, чтобы избежать парадоксов, путем введения своего рода "локальной" теории типов . В этой аксиоматической схеме,

{ s ∈ S : s ∉ f ( s ) }

не является множеством — т.е. не удовлетворяет схеме аксиом. С другой стороны, мы могли бы попытаться создать модифицированный диагональный аргумент, заметив, что

{ s ∈ S : s ∉ f ({ s }) }

является множеством в NF. В этом случае, если P ₁ ( S ) является множеством одноэлементных подмножеств S , а f является предложенной биекцией из P ₁ ( S ) в P ( S ), можно использовать доказательство от противного, чтобы доказать, что | P ₁ ( S )| < | P ( S )|.

Доказательство следует из того факта, что если бы f действительно была отображением на P ( S ), то мы могли бы найти r в S , такое, что f ({ r }) совпадало бы с модифицированным диагональным множеством, указанным выше. Мы бы пришли к выводу, что если r не принадлежит f ({ r }), то r принадлежит f ({ r }) и наоборот.

Невозможно поставить P ₁ ( S ) во взаимно-однозначное отношение с S , поскольку они имеют разные типы, и поэтому любая функция, определенная таким образом, нарушила бы правила типизации для схемы включения .

Смотрите также

• Первое доказательство несчетности Кантора
• Споры по поводу теории Кантора
• Диагональная лемма

Примечания

1. Аргумент диагонализации , аргумент диагональной косой черты , антидиагональный аргумент , диагональный метод и доказательство диагонализации Кантора
2. Кантор использовал « m» и « w » вместо «0» и «1», « M » вместо « T » и « E _i » вместо « s _i ».
3. Кантор не предполагает, что каждый элемент T находится в этом перечислении.
4. В то время как 0,0111... и 0,1000... были бы равны, если бы их интерпретировали как двоичные дроби (уничтожая инъективность), они различны, если их интерпретировать как десятичные дроби, как это делает f . С другой стороны, поскольку t является двоичной строкой, равенство 0,0999... = 0,1000... десятичных дробей здесь не имеет значения.

Ссылки

1. Георг Кантор (1891). «Ueber eine elementare Frage der Mannigfaltigkeitslehre». Jahresbericht der Deutschen Mathematiker-Vereinigung . 1 : 75–78.Перевод на английский язык: Эвальд, Уильям Б., ред. (1996). От Иммануила Канта до Дэвида Гильберта: Учебник по основам математики, том 2. Oxford University Press. стр. 920–922. ISBN 0-19-850536-1.
2. Кит Симмонс (30 июля 1993 г.). Универсальность и лжец: эссе об истине и диагональном аргументе. Cambridge University Press. ISBN 978-0-521-43069-2.
3. Рудин, Уолтер (1976). Принципы математического анализа (3-е изд.). Нью-Йорк: McGraw-Hill. стр. 30. ISBN 0070856133.
4. Грей, Роберт (1994), «Георг Кантор и трансцендентные числа» (PDF) , American Mathematical Monthly , 101 (9): 819–832, doi :10.2307/2975129, JSTOR  2975129
5. Блох, Итан Д. (2011). Действительные числа и действительный анализ . Нью-Йорк: Springer. С. 429. ISBN 978-0-387-72176-7.
6. Шеппард, Барнаби (2014). Логика бесконечности (иллюстрированное издание). Cambridge University Press. стр. 73. ISBN 978-1-107-05831-6.Выдержка из страницы 73
7. Парадокс Рассела. Стэнфордская энциклопедия философии. 2021.
8. Бертран Рассел (1931). Принципы математики . Нортон. С. 363–366.
9. См. страницу 254 Георга Кантора (1878), «Ein Beitrag zur Mannigfaltigkeitslehre», Journal für die Reine und Angewandte Mathematik , 84 : 242–258.. Это доказательство обсуждается в книге Джозефа Даубена (1979), Георг Кантор: его математика и философия бесконечности , издательство Гарвардского университета, ISBN 0-674-34871-0, стр. 61–62, 65. На странице 65 Добен доказывает результат, который сильнее результата Кантора. Он позволяет « φ _ν обозначать любую последовательность рациональных чисел в [0, 1]». Кантор позволяет φ _ν обозначать последовательность, перечисляющую рациональные числа в [0, 1], что является видом последовательности, необходимой для его построения биекции между [0, 1] и иррациональными числами в (0, 1).
10. Прадич, Пьер; Браун, Чад Э. (2019). «Кантор-Бернштейн подразумевает исключенное среднее». arXiv : 1904.09193 [math.LO].
11. Белл, Джон Л. (2004), «Парадокс Рассела и диагонализация в конструктивном контексте» (PDF) , в Link, Godehard (ред.), Сто лет парадокса Рассела , De Gruyter Series in Logic and its Applications, т. 6, de Gruyter, Берлин, стр. 221–225, MR  2104745
12. Ратьен, М. «Принципы выбора в конструктивных и классических теориях множеств», Труды коллоквиума по логике, 2002 г.
13. Бауэр, А. "Инъекция из N^N в N", 2011
14. Этторе Карруччо (2006). Математика и логика в истории и современной мысли . Transaction Publishers. стр. 354. ISBN 978-0-202-30850-0.
15. Бауэр; Хансон (2024). «Счетные действительные числа». arXiv : 2404.01256 [math.LO].
16. Роберт С. Любарский, О полноте Коши конструктивных вещественных чисел Коши, июль 2015 г.

Внешние ссылки

• Диагональное доказательство Кантора на MathPages
• Вайсштейн, Эрик В. «Метод диагонали Кантора». MathWorld .