Войти
Мощность множества { x, y, z } равна трем, в то время как в его наборе мощности восемь элементов (3 lt;2 3 = 8), здесь упорядоченных по включению. В элементарной теории множеств, теорема Кантора является фундаментальным результатом, который гласит, что для любого множества, множество всех подмножеств из ( булеано из, обозначаемого) имеет строго большую мощность, чем сам по себе. Для конечных множеств можно убедиться в истинности теоремы Кантора, просто перечислив количество подмножеств. Подсчитывая пустой набор как подмножество, набор с членами имеет всего подмножеств, так что если, то и теорема выполняется, потому что для всех неотрицательных целых чисел.
Гораздо более важным является открытие Кантором аргумента, применимого к любому множеству, которое показало, что теорема верна для бесконечных множеств, счетных или несчетных, а также конечных. Как особенно важное последствие, набор степеней множества натуральных чисел, счетно бесконечного множества с мощностью ℵ 0 = card ( N), является несчетным бесконечным и имеет тот же размер, что и множество действительных чисел, мощность больше, чем это множества натуральных чисел, которое часто называют мощностью континуума : 𝔠 = card ( R) = card (𝒫 ( N)). Связь между этими количественными числами часто символически выражается равенством и неравенством.
Теорема названа в честь немецкого математика Георга Кантора, который впервые сформулировал и доказал ее в конце 19 века. Теорема Кантора имела непосредственные и важные последствия для философии математики. Например, итеративно выбирая множество степеней бесконечного множества и применяя теорему Кантора, мы получаем бесконечную иерархию бесконечных кардиналов, каждый из которых строго больше предыдущего. Следовательно, из теоремы следует, что не существует наибольшего кардинального числа (в просторечии «не существует наибольшей бесконечности»).
Аргумент Кантора элегантен и удивительно прост. Полное доказательство представлено ниже с подробными пояснениями.
Теорема (Кантора) - Позвольте быть отображение от множества до его мощности. Тогда не сюръективно. Как следствие, верно для любого набора.
Доказательство -Рассмотрим набор. Предположим противное, что это сюръективно. Тогда существует такое, что. Но по конструкции. Получили противоречие. Таким образом, не может быть сюръективным. С другой стороны, определяется инъективным отображением. Следовательно, мы должны были иметь. QED
По определению мощности, мы имеем для любых двух множеств и тогда и только тогда, когда существует инъективная функция, но нет биективной функции от до. Достаточно показать, что сюрприз от к не существует. В этом суть теоремы Кантора: не существует сюръективной функции из любого набора для его набора мощности. Чтобы установить это, достаточно показать, что никакая функция f, отображающая элементы в подмножества, не может достичь всех возможных подмножеств, т. Е. Нам просто нужно продемонстрировать существование подмножества, которое не равно для любого ∈. (Напомним, что каждый является подмножеством.) Такое подмножество задается следующей конструкцией, которую иногда называют канторовым диагонали набор из:
По определению это означает, что для всех 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 предположение должно быть ложным. Таким образом, не существует ξ ∈ A такого, что f (ξ) = B ; другими словами, B не находится в образе f, и f не отображается в каждый элемент набора степеней A, т. е. f не сюръективен.
Наконец, чтобы завершить доказательство, нам нужно показать инъективную функцию из A в его множество степеней. Найти такую функцию просто: просто отобразите x в одноэлементный набор { x }. Рассуждение завершено, и мы установили строгое неравенство для любого множества A, что card ( A) lt;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) ложно. В каждом столбце записываются значения индикаторной функции набора, соответствующего столбцу. Индикаторная функция B совпадает с логически инвертированными (поменять местами «истина» и «ложь») входами главной диагонали. Таким образом, индикаторная функция B не согласуется ни с одним столбцом хотя бы в одной записи. Следовательно, столбец B не представляет.
Несмотря на простоту приведенного выше доказательства, автоматическому доказательству теорем довольно сложно его произвести. Основная трудность заключается в автоматическом обнаружении диагонального множества Кантора. Лоуренс Полсон отметил в 1992 году, что Оттер не могла этого сделать, в то время как Изабель могла, хотя и с определенной степенью руководства с точки зрения тактики, которую можно было бы считать обманом.
Рассмотрим доказательство для конкретного случая, когда это счетное. Без ограничения общности мы можем взять A = N = {1, 2, 3,…}, множество натуральных чисел.
Предположим, что N является equinumerous с установленной мощностью 𝒫 ( N). Давайте посмотрим на пример того, как выглядит 𝒫 ( N):
𝒫 ( N) содержит бесконечные подмножества N, например, множество всех четных чисел {2, 4, 6,...}, а также пустое множество.
Теперь, когда у нас есть представление о том, как выглядят элементы ( N), давайте попробуем разделить каждый элемент из N на каждый элемент из 𝒫 ( N), чтобы показать, что эти бесконечные множества равны. Другими словами, мы попытаемся объединить каждый элемент N в пару с элементом из бесконечного множества 𝒫 ( N), чтобы ни один элемент из любого бесконечного множества не оставался непарным. Такая попытка соединить элементы будет выглядеть так:
При таком соединении некоторые натуральные числа объединяются в пары с подмножествами, содержащими то же самое число. Например, в нашем примере число 2 связано с подмножеством {1, 2, 3}, которое содержит 2 в качестве члена. Назовем такие числа эгоистичными. Другие натуральные числа объединяются в пары с подмножествами, которые их не содержат. Например, в нашем примере число 1 сочетается с подмножеством {4, 5}, которое не содержит числа 1. Назовите эти числа неэгоистичными. Точно так же 3 и 4 не эгоистичны.
Используя эту идею, давайте построим специальный набор натуральных чисел. Этот набор даст искомое противоречие. Пусть B - множество всех неэгоистичных натуральных чисел. По определению, набор мощности 𝒫 ( N) содержит все наборы натуральных чисел, поэтому он содержит это множество B как элемент. Если отображение биективно, B должен быть спарен с некоторым натуральным числом, скажем b. Однако это вызывает проблему. Если б в B, то б эгоистично, потому что он находится в соответствующем наборе, что противоречит определению B. Если б не в B, то он не является эгоистичным и он должен вместо того, чтобы быть членом B. Следовательно, такой элемент b, который отображается в B, существовать не может.
Поскольку не существует натурального числа, которое может быть спарено с B, мы противоречили нашему первоначальному предположению, что существует биекция между N и ( N).
Обратите внимание, что набор B может быть пустым. Это означало бы, что каждое натуральное число x отображается в подмножество натуральных чисел, которое содержит x. Затем каждое число отображается в непустое множество, и никакое число не отображается в пустой набор. Но пустое множество является членом ( N), поэтому отображение по-прежнему не покрывает 𝒫 ( N).
Благодаря этому доказательства от противного, мы доказали, что мощность из N и 𝒫 ( N) не может быть равна. Мы также знаем, что мощность из 𝒫 ( N) не может быть меньше, чем мощность от N, так как 𝒫 ( N) содержит все синглтонов, по определению, и эти одноэлементные образуют «копию» N внутри 𝒫 ( N). Таким образом, остается только одна возможность, и в том, что мощность из 𝒫 ( N) строго больше, чем мощность из N, доказав теорему Кантора.
Теорема Кантора и ее доказательство тесно связаны с двумя парадоксами теории множеств.
Парадокс Кантора - это название противоречия, вытекающего из теоремы Кантора вместе с предположением, что существует множество, содержащее все множества, универсальное множество. Чтобы отличить этот парадокс от следующего, обсуждаемого ниже, важно отметить, в чем состоит это противоречие. По теореме Кантора для любого множества. С другой стороны, все элементы представляют собой наборы, и, таким образом, содержащиеся в, поэтому.
Другой парадокс может быть получен из доказательства теоремы Кантора путем создания экземпляра функции f с тождественной функцией ; это превращает диагональное множество Кантора в то, что иногда называют множеством Рассела данного множества A:
Доказательство теоремы Кантора напрямую адаптировано, чтобы показать, что если предположить, что множество всех множеств U существует, то рассмотрение его множества Рассела R U приводит к противоречию:
Этот аргумент известен как парадокс Рассела. Для тонкости представленная здесь версия парадокса Рассела на самом деле является теоремой Цермело ; Из полученного противоречия можно сделать вывод, что мы должны отвергнуть гипотезу о том, что R U ∈ U, тем самым опровергнув существование множества, содержащего все множества. Это стало возможным, потому что мы использовали ограниченное понимание (как показано в ZFC ) в определении R A выше, что, в свою очередь, повлекло за собой то, что
Если бы мы использовали неограниченное понимание (как, например, в системе Фреге ), определяя множество Рассела просто как, тогда сама система аксиом привела бы к противоречию, без необходимости в дополнительных гипотезах.
Несмотря на синтаксическое сходство между множеством Рассела (в любом варианте) и диагональным множеством Кантора, Алонзо Черч подчеркнул, что парадокс Рассела не зависит от соображений мощности и лежащих в основе его понятий, таких как взаимно однозначное соответствие.
Кантор, по сути, дал это доказательство в статье, опубликованной в 1891 году «Über eine elementare Frage der Mannigfaltigkeitslehre», где также впервые появляется диагональный аргумент в пользу несчетности действительных чисел ( ранее он доказал несчетность действительных чисел другими методами ). Версия этого аргумента, которую он привел в той статье, была сформулирована в терминах индикаторных функций на множестве, а не в подмножествах набора. Он показал, что если 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 теория множеств.
Теорема Кантора была обобщена на любую категорию с продуктами.
