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

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

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

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

Георг Кантор опубликовал это доказательство в 1891 году. но это было не первое его доказательство несчетности действительных чисел , появившееся в 1874 году. Однако он демонстрирует общую технику, которая с тех пор использовалась в широком спектре доказательств. включая первую из теорем Гёделя о неполноте и ответ Тьюринга на проблему Entscheidungs . Аргументы диагонализации часто также являются источником противоречий, таких как парадокс Рассела. и парадокс Ричарда .

Бесчисленное множество

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

Если s ₁ , s ₂ , ... , sn _, ... — любое перечисление элементов из T , тогда можно построить элемент s из T , который не соответствует ни одному s _n в перечислении.

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

с 1 =	(0,	0,	0,	0,	0,	0,	0,	...)
s2 =	(1,	1,	1,	1,	1,	1,	1,	...)
с 3 =	(0,	1,	0,	1,	0,	1,	0,	...)
с 4 =	(1,	0,	1,	0,	1,	0,	1,	...)
с 5 =	(1,	1,	0,	1,	0,	1,	1,	...)
с 6 =	(0,	0,	1,	1,	0,	1,	1,	...)
с 7 =	(1,	0,	0,	0,	1,	0,	0,	...)
...

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

с 1	=	( 0 ,	0,	0,	0,	0,	0,	0,	...)
ss2	=	(1,	1 ,	1,	1,	1,	1,	1,	...)
с 3	=	(0,	1,	0 ,	1,	0,	1,	0,	...)
с 4	=	(1,	0,	1,	0 ,	1,	0,	1,	...)
с 5	=	(1,	1,	0,	1,	0 ,	1,	1,	...)
с 6	=	(0,	0,	1,	1,	0,	1 ,	1,	...)
ss7	=	(1,	0,	0,	0,	1,	0,	0 ,	...)
...
с	=	( 1 ,	0 ,	1 ,	1 ,	1 ,	0 ,	1 ,	...)

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

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

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

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

Реальные числа

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

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

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

showПостроение биекции между T и R

The function h: (0,1) → (−π/2,π/2) The function tan: (−π/2,π/2) → R This construction uses a method devised by Cantor that was published in 1878. He used it to construct a bijection between the closed interval [0, 1] and the irrationals in the open interval (0, 1). He first removed a countably infinite subset from each of these sets so that there is a bijection between the remaining uncountable sets. Since there is a bijection between the countably infinite subsets that have been removed, combining the two bijections produces a bijection between the original sets. Cantor's method can be used to modify the function f 2(t) = 0.t2 to produce a bijection from T to (0, 1). Because some numbers have two binary expansions, f 2(t) is not even injective. For example, f 2(1000...) = 0.1000...2 = 1/2 and f 2(0111...) = 0.0111...2 = 1/4 + 1/8 + 1/16 + ... = 1/2, so both 1000... and 0111... map to the same number, 1/2. To modify f2 (t), observe that it is a bijection except for a countably infinite subset of (0, 1) and a countably infinite subset of T. It is not a bijection for the numbers in (0, 1) that have two binary expansions. These are called dyadic numbers and have the form m / 2n where m is an odd integer and n is a natural number. Put these numbers in the sequence: r = (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...). Also, f2 (t) is not a bijection to (0, 1) for the strings in T appearing after the binary point in the binary expansions of 0, 1, and the numbers in sequence r. Put these eventually-constant strings in the sequence: s = (000..., 111..., 1000..., 0111..., 01000..., 00111..., 11000..., 10111..., ...). Define the bijection g(t) from T to (0, 1): If t is the nth string in sequence s, let g(t) be the nth number in sequence r ; otherwise, g(t) = 0.t2. To construct a bijection from T to R, start with the tangent function tan(x), which is a bijection from (−π/2, π/2) to R (see the figure shown on the right). Next observe that the linear function h(x) = πx – π/2 is a bijection from (0, 1) to (−π/2, π/2) (see the figure shown on the left). The composite function tan(h(x)) = tan(πx – π/2) is a bijection from (0, 1) to R. Composing this function with g(t) produces the function tan(h(g(t))) = tan(πg(t) – π/2), which is a bijection from T to R.

Общие наборы

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

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

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

Т знак равно { s ∈ S : s ∉ ж ( s ) }.

Для каждого s в S либо s находится в T , либо нет. Если s находится в T , то по определению T s f находится в f ( s ), поэтому T не равно s ( не ). С другой стороны, если s не находится в T по определению T s f находится в f ( s ), поэтому T снова не равно , то ( s ); ср. картина.Более полное изложение этого доказательства см. в теореме Кантора .

Последствия

Орден кардиналов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

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

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