В элементарной теории множеств , теорема Кантора является фундаментальным результатом , который гласит , что для любого набора , Множество всех подмножеств из( силовой агрегат из, обозначаемый ) имеет строго большую мощность, чемсам. Для конечных множеств можно убедиться в истинности теоремы Кантора, просто перечислив количество подмножеств. Считая пустой набор как подмножество, набор с членов в общей сложности подмножества, так что если тогда , и теорема верна, поскольку для всех неотрицательных целых чисел .
Гораздо более важным является открытие Кантором аргумента, применимого к любому множеству, которое показало, что теорема верна для бесконечных множеств, счетных или несчетных, а также конечных. Как особенно важное следствие, набор степеней множества натуральных чисел , счетно бесконечного множества с мощностью ℵ 0 = card (ℕ), является несчетным бесконечным и имеет тот же размер, что и набор действительных чисел , мощность больше, чем это множества натуральных чисел, которое часто называют мощностью континуума : 𝔠 = card (ℝ) = card (𝒫 (ℕ)). Связь между этими количественными числами часто символически выражается равенством и неравенством..
Теорема названа в честь немецкого математика Георга Кантора , который впервые сформулировал и доказал ее в конце 19 века. Теорема Кантора имела непосредственные и важные последствия для философии математики . Например, итеративно выбирая множество степеней бесконечного множества и применяя теорему Кантора, мы получаем бесконечную иерархию бесконечных кардиналов, каждый из которых строго больше предыдущего. Следовательно, из теоремы следует, что не существует наибольшего кардинального числа (в просторечии «не существует наибольшей бесконечности»).
Доказательство
Аргумент Кантора элегантен и удивительно прост. Полное доказательство представлено ниже с подробными пояснениями.
Теорема (Кантора). Позволять быть картой из набора к его мощности . потомне сюръективно . Как следствие, справедливо для любого набора .
Доказательство. Рассмотрим множество. Предположим противное, чтосюръективно. Тогда существует такой, что . Но по построению. Получили противоречие. Таким образом,не может быть сюръективным. С другой стороны, определяется является инъективным отображением. Следовательно, мы должны иметь.
По определению мощности имеем для любых двух наборов а также тогда и только тогда, когда существует инъективная функция, но нет биективной функции из к . Достаточно показать, что сюрприз от к . В этом суть теоремы Кантора: не существует сюръективной функции из любого множества.к его мощности. Чтобы установить это, достаточно показать, что никакая функция f , отображающая элементы в к подмножествам может достичь всех возможных подмножеств, т.е. нам просто нужно продемонстрировать существование подмножества это не равно для любой ∈ . (Напомним, что каждый это подмножество .) Такое подмножество задается следующей конструкцией, которую иногда называют канторовым диагонали множество из: [1] [2]
По определению это означает, что для всех x ∈ A , x ∈ B тогда и только тогда, когда x ∉ f ( x ). Для всех x множества B и f ( x ) не могут быть одинаковыми, потому что B был построен из элементов A , изображения которых (под f ) не включали самих себя. Более конкретно, рассмотрим любой x ∈ A , тогда либо x ∈ f ( x ), либо x ∉ f ( x ). В первом случае, е ( х ) не может равняться B , так как х ∈ F ( х ) по предположению и х ∉ B по построению B . В последнем случае, F ( х ) не может равняться Б , поскольку х ∉ е ( х ) и по предположению х ∈ B по построению B .
Эквивалентно и чуть более формально мы только что доказали, что существование ξ ∈ A такого, что f (ξ) = B, влечет следующее противоречие :
Следовательно, путем reductio ad absurdum предположение должно быть ложным. [3] Таким образом, не существует ξ ∈ A такого, что f (ξ) = B ; другими словами, B не находится в образе f, и f не отображается в каждый элемент набора степеней A , т. е. f не сюръективен.
Наконец, чтобы завершить доказательство, нам нужно показать инъективную функцию из A в его множество степеней. Найти такую функцию просто: просто отобразите x в одноэлементный набор { x }. Рассуждение завершено, и мы установили строгое неравенство для любого множества A, что card ( A )
Другой способ думать доказательства состоит в том, что B , пусто или не пусто, всегда в наборе мощности A . Для F , чтобы быть на , некоторый элемент А должен отображаться на B . Но это приводит к противоречию: ни один элемент B не может отображаться в B, потому что это противоречило бы критерию членства в B , таким образом, отображение элемента в B не должно быть элементом B, что означает, что он удовлетворяет критерию членства в B , еще одно противоречие. Итак, предположение, что элемент A отображается в B, должно быть ложным; и f не может быть на.
Поскольку x в выражении « x ∉ f ( x )» встречается дважды , это диагональный аргумент . Для счетного (или конечного) множества аргументы приведенного выше доказательства можно проиллюстрировать построением таблицы, в которой каждая строка помечена уникальным x из A = { x 1 , x 2 , ...} в этом заказывать. Предполагается, что A допускает линейный порядок, так что такая таблица может быть построена. Каждый столбец таблицы помечен уникальным y из набора степеней A ; столбцы упорядочены по аргументу f , т. е. метки столбцов - f ( x 1 ), f ( x 2 ), ..., в этом порядке. На пересечении каждой строки x и столбца y записывается бит истинно / ложно, независимо от того, является ли x ∈ y . Учитывая порядок , выбранный для строки и столбца меток, главная диагональ D из этой таблицы , таким образом , фиксирует ли х ∈ F ( х ) для каждого х ∈ . Множество B, построенное в предыдущих абзацах, совпадает с метками строк для подмножества записей на этой главной диагонали D, где в таблице записано, что x ∈ f ( x ) ложно. [3] В каждом столбце записываются значения индикаторной функции набора, соответствующего столбцу. Индикаторная функция B совпадает с логически инвертированными (поменять местами «истина» и «ложь») входами главной диагонали. Таким образом, индикаторная функция B не согласуется ни с одним столбцом хотя бы в одной записи. Следовательно, столбец B не представляет .
Несмотря на простоту приведенного выше доказательства, автоматическому доказательству теорем довольно сложно его произвести. Основная трудность заключается в автоматическом обнаружении диагонального множества Кантора. Лоуренс Полсон отметил в 1992 году, что Оттер не могла этого сделать, в то время как Изабель могла, хотя и с определенной степенью руководства с точки зрения тактики, которую можно было бы считать обманом. [2]
Когда счетно бесконечен
Рассмотрим доказательство для конкретного случая, когда является счетно бесконечным . Без ограничения общности мы можем взять= ℕ = {1, 2, 3, ...}, множество натуральных чисел .
Предположим, что равнозначно своему множеству степеней 𝒫 ( ℕ ). Давайте посмотрим, как выглядит 𝒫 ( ℕ ):
𝒫 ( ℕ ) содержит бесконечные подмножества ℕ , например, множество всех четных чисел {2, 4, 6, ...}, а также пустое множество .
Теперь, когда мы имеем представление о том , что элементы 𝒫 ( ℕ ) выглядят как, давайте попытаемся соединить каждый отдельный элемент из ℕ с каждым элементом 𝒫 ( ℕ ) , чтобы показать , что эти бесконечные множества equinumerous. Другими словами, мы попытаемся объединить каждый элемент в пару с элементом из бесконечного множества 𝒫 ( ℕ ), чтобы ни один элемент из любого бесконечного множества не оставался непарным. Такая попытка объединить элементы в пары будет выглядеть так:
При таком соединении некоторые натуральные числа объединяются в пары с подмножествами , содержащими то же самое число. Например, в нашем примере число 2 связано с подмножеством {1, 2, 3}, которое содержит 2 в качестве члена. Назовем такие числа эгоистичными . Другие натуральные числа объединяются в пары с подмножествами, которые их не содержат. Например, в нашем примере число 1 сочетается с подмножеством {4, 5}, которое не содержит числа 1. Назовите эти числа неэгоистичными . Точно так же 3 и 4 не эгоистичны.
Используя эту идею, давайте построим специальный набор натуральных чисел. Этот набор даст искомое противоречие . Пусть B - множество всех неэгоистичных натуральных чисел. По определению, набор мощности 𝒫 ( ℕ ) содержит все наборы натуральных чисел, и поэтому он содержит это множество B как элемент. Если отображение биективно, B должен быть спарен с некоторым натуральным числом, скажем b . Однако это вызывает проблему. Если б в B , то б эгоистично , потому что он находится в соответствующем наборе, что противоречит определению B . Если б не в B , то он не является эгоистичным и он должен вместо того, чтобы быть членом B . Следовательно, такой элемент b, который отображается в B, существовать не может.
Поскольку не существует натуральное число , которое может быть в паре с B , мы противоречили наше изначальное предположение, что существует взаимно однозначное соответствие между ℕ и 𝒫 ( ℕ ).
Обратите внимание, что набор B может быть пустым. Это означало бы, что каждое натуральное число x отображается в подмножество натуральных чисел, которое содержит x . Затем каждое число отображается в непустое множество, и никакое число не отображается в пустой набор. Но пустое множество является членом ( ℕ ), поэтому отображение по-прежнему не покрывает 𝒫 ( ℕ ).
Благодаря этому доказательство от противного , мы доказали , что мощность из ℕ и 𝒫 ( ℕ ) не могут быть равны. Мы также знаем , что мощность из 𝒫 ( ℕ ) не может быть меньше , чем мощность в ℕ потому 𝒫 ( ℕ ) содержит все синглтонов , по определению, и эти одноэлементные образуют «копию» ℕ внутри 𝒫 ( ℕ ). Таким образом, остается только одна возможность, и в том , что мощность из 𝒫 ( ℕ ) строго больше , чем мощность в ℕ , доказав теорему Кантора.
Связанные парадоксы
Теорема Кантора и ее доказательство тесно связаны с двумя парадоксами теории множеств .
Парадокс Кантора - это название противоречия, вытекающего из теоремы Кантора вместе с предположением, что существует множество, содержащее все множества, универсальное множество . Чтобы отличить этот парадокс от следующего, обсуждаемого ниже, важно отметить, в чем заключается это противоречие. По теореме Кантора для любого набора . С другой стороны, все элементы являются множествами и, таким образом, содержатся в , следовательно . [1]
Другой парадокс может быть получен из доказательства теоремы Кантора путем создания экземпляра функции f с тождественной функцией ; это превращает диагональное множество Кантора в то, что иногда называют множеством Рассела данного множества A : [1]
Доказательство теоремы Кантора напрямую адаптировано, чтобы показать, что если предположить, что множество всех множеств U существует, то рассмотрение его множества Рассела R U приводит к противоречию:
Этот аргумент известен как парадокс Рассела . [1] В качестве тонкости, версия парадокса Рассела, которую мы здесь представили, на самом деле является теоремой Цермело ; [4] из полученного противоречия можно заключить, что мы должны отвергнуть гипотезу о том, что R U ∈ U , тем самым опровергнув существование множества, содержащего все множества. Это стало возможным, потому что мы использовали ограниченное понимание (как в ZFC ) в определении R A выше, что, в свою очередь, повлекло за собой то, что
Если бы мы использовали неограниченное понимание (как, например, в системе Фреге ), определяя множество Рассела просто как, то сама система аксиом привела бы к противоречию, без дополнительных гипотез. [4]
Несмотря на синтаксическое сходство между множеством Рассела (в любом варианте) и диагональным множеством Кантора, Алонзо Черч подчеркнул, что парадокс Рассела не зависит от соображений мощности и лежащих в основе понятий, таких как взаимно однозначное соответствие. [5]
История
Кантор представил это доказательство в статье, опубликованной в 1891 г. «Über eine elementare Frage der Mannigfaltigkeitslehre» [6], где впервые появляется диагональный аргумент в пользу несчетности действительных чисел ( ранее он доказал несчетность действительных чисел другими методами ). . Версия этого аргумента, которую он привел в той статье, была сформулирована в терминах индикаторных функций на множестве, а не в подмножествах набора. Он показал, что если f - функция, определенная на X , значения которой являются двузначными функциями на X , то двузначная функция G ( x ) = 1 - f ( x ) ( x ) не находится в диапазоне f .
Бертран Рассел приводит очень похожее доказательство в Принципах математики (1903, раздел 348), где он показывает, что пропозициональных функций больше, чем объектов. «Действительно , пусть корреляция всех объектов и некоторые пропозициональных функции были затронуты, и пусть phi- х будут коррелят х . Тогда„не-phi- х ( х ),“то есть» phi- х не имеет из й «является пропозициональной функцией, не содержащейся в этой корреляции; поскольку она истинна или ложна для x, в зависимости от того, является ли ph- x ложным или истинным для x , и поэтому она отличается от phi- x для каждого значения x ». Он приписывает идею доказательства Кантору.
У Эрнста Цермело есть теорема (которую он называет «теоремой Кантора»), которая идентична форме, приведенной выше в статье, которая стала основой современной теории множеств («Untersuchungen über die Grundlagen der Mengenlehre I»), опубликованной в 1908 году. См. Zermelo теория множеств .
Обобщения
Теорема Кантора была обобщена на любую категорию с продуктами . [7]
Смотрите также
- Теорема Шредера – Бернштейна.
- Первое доказательство несчетности Кантора
- Споры по теории Кантора
Рекомендации
- ^ а б в г Абхиджит Дасгупта (2013). Теория множеств: введение в наборы реальных точек . Springer Science & Business Media . С. 362–363. ISBN 978-1-4614-8854-5.
- ^ а б Лоуренс Полсон (1992). Теория множеств как вычислительная логика (PDF) . Компьютерная лаборатория Кембриджского университета. п. 14.
- ^ а б Грэм Прист (2002). За пределами мысли . Издательство Оксфордского университета. С. 118–119. ISBN 978-0-19-925405-7.
- ^ а б Хайнц-Дитер Эббингаус (2007). Эрнст Цермело: подход к его жизни и работе . Springer Science & Business Media. стр. 86 -87. ISBN 978-3-540-49553-6.
- ^ Черч, A. [1974] "Теория множеств с универсальным набором". в материалах Тарского симпозиума. Труды симпозиумов по чистой математике XXV, изд. Л. Хенкин, Провиденс Р.И., Издание второе с дополнениями, 1979, с. 297−308. ISBN 978-0-8218-7360-1 . Также опубликовано в International Logic Review, 15 стр. 11–23.
- ^ Кантор, Георг (1891), "Über eine elementare Frage der Mannigfaltigskeitslehre" , Jahresber. der DMV (на немецком языке), 1 : 75–78, также у Георга Кантора, Gesammelte Abhandlungen Mathematischen und Philophischen Inhalts , E. Zermelo, 1932.
- ^ Ф. Уильям Ловер; Стивен Х. Шануэль (2009). Концептуальная математика: первое введение в категории . Издательство Кембриджского университета. Сессия 29. ISBN 978-0-521-89485-2.
- Халмос, Пол , Наивная теория множеств . Принстон, Нью-Джерси: D. Van Nostrand Company, 1960. Перепечатано Springer-Verlag , Нью-Йорк, 1974. ISBN 0-387-90092-6 (издание Springer-Verlag). Перепечатано Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (издание в мягкой обложке).
- Jech, Thomas (2002), Теория множеств , Монографии Springer по математике (изд. 3-го тысячелетия), Springer, ISBN 3-540-44085-2
Внешние ссылки
- "Теорема Кантора" , Математическая энциклопедия , EMS Press , 2001 [1994]
- Вайсштейн, Эрик В. «Теорема Кантора» . MathWorld .