Теорема Кантора

Каждый набор меньше своего набора мощности

Мощность множества { x , y , z } равна трем, в то время как его множество содержит восемь элементов (3 < 2 ³ = 8), здесь упорядоченных по включению .

В математической теории множеств теорема Кантора является фундаментальным результатом, который утверждает, что для любого множества множество всех подмножеств , известное как множество мощности , имеет строго большую мощность, чем оно само. ${\displaystyle A}$ ${\displaystyle A,}$ ${\displaystyle A,}$ ${\displaystyle A}$

Для конечных множеств теорема Кантора может быть верна простым перечислением числа подмножеств. Считая пустое множество подмножеством, множество с элементами имеет общее число подмножеств, и теорема верна, поскольку для всех неотрицательных целых чисел . ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}>n}$

Гораздо более значимым является открытие Кантором аргумента, который применим к любому множеству, и показывает, что теорема верна также и для бесконечных множеств. Как следствие, мощность действительных чисел , которая совпадает с мощностью множества целых чисел , строго больше мощности целых чисел; см. Мощность континуума для получения подробной информации.

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

Доказательство

Аргумент Кантора элегантен и удивительно прост. Полное доказательство представлено ниже, с подробными пояснениями.

Теорема (Кантор)  —  Пусть — отображение множества в его мощность . Тогда не является сюръективным . Как следствие, справедливо для любого множества . ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {P}}(A)}$ ${\displaystyle f:A\to {\mathcal {P}}(A)}$ ${\displaystyle \operatorname {card} (A)<\operatorname {card} ({\mathcal {P}}(A))}$ ${\displaystyle A}$

Доказательство

${\displaystyle B=\{x\in A\mid x\notin f(x)\}}$существует через схему аксиом спецификации , и поскольку . Предположим , что сюръективно. Тогда существует такое, что . Из   для всех в мы выводим    через универсальную инстанциацию . Предыдущий вывод дает противоречие вида , поскольку . Следовательно, не является сюръективным, через reductio ad absurdum . Мы знаем, что инъективные отображения из существуют . Например, функция такая, что . Следовательно, . ∎ ${\displaystyle B\in {\mathcal {P}}(A)}$ ${\displaystyle B\subseteq A}$
${\displaystyle f}$
${\displaystyle \xi \in A}$ ${\displaystyle f(\xi )=B}$
${\displaystyle x}$ ${\displaystyle A\ [x\in B\iff x\notin f(x)]}$ ${\displaystyle \xi \in B\iff \xi \notin f(\xi )}$
${\displaystyle \varphi \Leftrightarrow \lnot \varphi }$ ${\displaystyle f(\xi )=B}$
${\displaystyle f}$
${\displaystyle A}$ ${\displaystyle {\mathcal {P}}(A)}$ ${\displaystyle g:A\to {\mathcal {P}}(A)}$ ${\displaystyle g(x)=\{x\}}$
${\displaystyle \operatorname {card} (A)<\operatorname {card} ({\mathcal {P}}(A))}$

По определению мощности, для любых двух множеств и тогда и только тогда, когда существует инъективная функция , но нет биективной функции из в . Достаточно показать, что нет сюръекции из в . Это суть теоремы Кантора: нет сюръективной функции из любого множества в его степенное множество. Чтобы установить это, достаточно показать, что никакая функция (которая отображает элементы в в подмножества ) не может достичь каждого возможного подмножества, т. е. нам просто нужно продемонстрировать существование подмножества , которое не равно ни для одного . Вспоминая, что каждое является подмножеством , такое подмножество задается следующей конструкцией, иногда называемой диагональным множеством Кантора : ^[1] [ ^2] ${\displaystyle \operatorname {card} (X)<\operatorname {card} (Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle f(x)}$ ${\displaystyle x\in A}$ ${\displaystyle f(x)}$ ${\displaystyle A}$ ${\displaystyle f}$

${\displaystyle B=\{x\in A\mid x\not \in f(x)\}.}$

Это означает, по определению, что для всех , тогда и только тогда, когда . Для всех множеств и не могут быть равны, так как были построены из элементов, образы которых под не включали себя. Для всех либо , либо . Если то не может быть равно, так как по предположению и по определению. Если то не может быть равно, так как по предположению и по определению . ${\displaystyle x\in A}$ ${\displaystyle x\in B}$ ${\displaystyle x\notin f(x)}$ ${\displaystyle x}$ ${\displaystyle B}$ ${\displaystyle f(x)}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle x\in A}$ ${\displaystyle x\in f(x)}$ ${\displaystyle x\notin f(x)}$ ${\displaystyle x\in f(x)}$ ${\displaystyle f(x)}$ ${\displaystyle B}$ ${\displaystyle x\in f(x)}$ ${\displaystyle x\notin B}$ ${\displaystyle x\notin f(x)}$ ${\displaystyle f(x)}$ ${\displaystyle B}$ ${\displaystyle x\notin f(x)}$ ${\displaystyle x\in B}$ ${\displaystyle B}$

Эквивалентно и немного более формально, мы только что доказали, что существование такого, что подразумевает следующее противоречие : ${\displaystyle \xi \in A}$ ${\displaystyle f(\xi )=B}$

${\displaystyle {\begin{aligned}\xi \in B&\iff \xi \notin f(\xi )&&{\text{(by definition of }}B{\text{)}};\\\xi \in B&\iff \xi \in f(\xi )&&{\text{(by assumption that }}f(\xi )=B{\text{)}}.\\\end{aligned}}}$

Следовательно, путем сведения к абсурду , предположение должно быть ложным. ^[3] Таким образом, не существует такого, что  ; другими словами, не является образом и не отображается на каждый элемент множества степеней , т. е. не является сюръективным. ${\displaystyle \xi \in A}$ ${\displaystyle f(\xi )=B}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle f}$

Наконец, чтобы завершить доказательство, нам нужно продемонстрировать инъективную функцию из в ее множество мощности. Найти такую ​​функцию тривиально: просто отобразить в синглтон-множество . Теперь аргумент завершен, и мы установили строгое неравенство для любого множества , которое . ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle \{x\}}$ ${\displaystyle A}$ ${\displaystyle \operatorname {card} (A)<\operatorname {card} ({\mathcal {P}}(A))}$

Другой способ представить доказательство заключается в том, что , пустой или непустой, всегда находится в силовом множестве . Для того , чтобы быть на , некоторый элемент из должен отображаться на . Но это приводит к противоречию: ни один элемент из не может отображаться на , поскольку это противоречило бы критерию членства в , таким образом, элемент, отображаемый на , не должен быть элементом из , что означает, что он удовлетворяет критерию членства в , еще одно противоречие. Таким образом, предположение о том, что элемент из отображается на , должно быть ложным; и не может отображаться на . ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f}$

Из-за двойного появления в выражении " ", это диагональный аргумент . Для счетного (или конечного) множества аргумент приведенного выше доказательства можно проиллюстрировать, построив таблицу, в которой каждая строка помечена уникальным из , в этом порядке. предполагается, что допускает линейный порядок , так что такую ​​таблицу можно построить. Каждый столбец таблицы помечен уникальным из множества мощности ; столбцы упорядочены аргументом по , т. е. метки столбцов равны , ..., в этом порядке. Пересечение каждой строки и столбца записывает бит true/false, является ли . Учитывая порядок, выбранный для меток строк и столбцов, главная диагональ этой таблицы, таким образом, записывает, является ли для каждого . Набор, построенный в предыдущих абзацах, совпадает с метками строк для подмножества записей на этой главной диагонали, где таблица записывает, что является ложным. ^[3] Каждый столбец записывает значения индикаторной функции набора, соответствующего столбцу. Индикаторная функция совпадает с логически отрицаемыми (поменяйте местами "истина" и "ложь") записями главной диагонали. Таким образом, индикаторная функция не согласуется ни с одним столбцом хотя бы в одной записи. Следовательно, ни один столбец не представляет . ${\displaystyle x}$ ${\displaystyle x\in f(x)}$ ${\displaystyle x}$ ${\displaystyle A=\{x_{1},x_{2},\ldots \}}$ ${\displaystyle A}$ ${\displaystyle y}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle f(x_{1}),f(x_{2})}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\in y}$ ${\displaystyle D}$ ${\displaystyle x\in f(x)}$ ${\displaystyle x\in A}$ ${\displaystyle B}$ ${\displaystyle D}$ ${\displaystyle x\in f(x)}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$

Несмотря на простоту приведенного выше доказательства, для автоматизированного доказательного устройства теорем его создание довольно затруднительно. Основная трудность заключается в автоматизированном обнаружении диагонального множества Кантора. Лоуренс Полсон заметил в 1992 году, что Оттер не мог этого сделать, тогда как Изабель могла, хотя и с определенным количеством указаний в плане тактики, которую, возможно, можно было бы считать мошенничеством. ^[2]

КогдаАсчетно бесконечно

Рассмотрим доказательство для частного случая, когда счетно бесконечно . Без потери общности можно взять множество натуральных чисел . ${\displaystyle A}$ ${\displaystyle A=\mathbb {N} =\{1,2,3,\ldots \}}$

Предположим, что это равновелико с его множеством мощности . Давайте посмотрим на пример того, что выглядит так: ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$

${\displaystyle {\mathcal {P}}(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.}$

${\displaystyle {\mathcal {P}}(\mathbb {N} )}$содержит бесконечные подмножества , например, множество всех положительных четных чисел , а также пустое множество . ${\displaystyle \mathbb {N} }$ ${\displaystyle \{2,4,6,\ldots \}=\{2k:k\in \mathbb {N} \}}$ ${\displaystyle \varnothing }$

Теперь, когда у нас есть представление о том, что такое элементы из , давайте попробуем сопоставить каждый элемент с каждым элементом из , чтобы показать, что эти бесконечные множества равночисленны. Другими словами, мы попытаемся сопоставить каждый элемент с элементом из бесконечного множества , так что ни один элемент из любого бесконечного множества не останется непарным. Такая попытка сопоставить элементы будет выглядеть следующим образом: ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$

${\displaystyle \mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}{\mathcal {P}}(\mathbb {N} ).}$

При таком сопряжении некоторые натуральные числа образуют пары с подмножествами , содержащими то же самое число. Например, в нашем примере число 2 образует пару с подмножеством {1, 2, 3}, которое содержит 2 в качестве члена. Назовем такие числа эгоистичными . Другие натуральные числа образуют пары с подмножествами , которые их не содержат. Например, в нашем примере число 1 образует пару с подмножеством {4, 5}, которое не содержит число 1. Назовем эти числа неэгоистичными . Аналогично, 3 и 4 являются неэгоистичными.

Используя эту идею, давайте построим специальный набор натуральных чисел. Этот набор даст нам искомое противоречие . Пусть будет набором всех неэгоистичных натуральных чисел. По определению, множество степеней содержит все наборы натуральных чисел, и поэтому оно содержит этот набор как элемент. Если отображение биективно, должно быть сопряжено с некоторым натуральным числом, скажем . Однако это вызывает проблему. Если находится в , то является эгоистичным, поскольку находится в соответствующем наборе, что противоречит определению . Если не находится в , то он является неэгоистичным и вместо этого должен быть членом . Следовательно, не может существовать такой элемент , который отображается в . ${\displaystyle B}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle B}$ ${\displaystyle b}$ ${\displaystyle B}$ ${\displaystyle b}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle b}$ ${\displaystyle B}$

Поскольку не существует натурального числа, которое можно было бы поставить в пару с , мы противоречим нашему первоначальному предположению о том, что между и существует биекция . ${\displaystyle B}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$

Обратите внимание, что множество может быть пустым. Это означало бы, что каждое натуральное число отображается в подмножество натуральных чисел, которое содержит . Тогда каждое число отображается в непустое множество, и ни одно число не отображается в пустое множество. Но пустое множество является членом , поэтому отображение все еще не покрывает . ${\displaystyle B}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$

Благодаря этому доказательству от противного мы доказали, что мощность и не может быть равна . Мы также знаем, что мощность не может быть меньше мощности , поскольку содержит все синглтоны , по определению, и эти синглтоны образуют «копию» внутри . Таким образом, остается только одна возможность, а именно, что мощность строго больше мощности , что доказывает теорему Кантора. ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \mathbb {N} }$

Связанные парадоксы

Теорема Кантора и ее доказательство тесно связаны с двумя парадоксами теории множеств .

Парадокс Кантора — это название противоречия, вытекающего из теоремы Кантора вместе с предположением, что существует множество, содержащее все множества, универсальное множество . Чтобы отличить этот парадокс от следующего, обсуждаемого ниже, важно отметить, в чем заключается это противоречие. По теореме Кантора для любого множества . С другой стороны, все элементы из являются множествами, и, таким образом, содержатся в , следовательно . ^[1] ${\displaystyle V}$ ${\displaystyle |{\mathcal {P}}(X)|>|X|}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}(V)}$ ${\displaystyle V}$ ${\displaystyle |{\mathcal {P}}(V)|\leq |V|}$

Другой парадокс можно вывести из доказательства теоремы Кантора, конкретизировав функцию f с помощью функции тождества ; это превращает диагональное множество Кантора в то, что иногда называют множеством Рассела данного множества A : ^[1]

${\displaystyle R_{A}=\left\{\,x\in A:x\not \in x\,\right\}.}$

Доказательство теоремы Кантора легко адаптируется для того, чтобы показать, что если предположить, что множество всех множеств U существует, то рассмотрение его множества Рассела R _U приводит к противоречию:

${\displaystyle R_{U}\in R_{U}\iff R_{U}\notin R_{U}.}$

Этот аргумент известен как парадокс Рассела . ^[1] В качестве тонкости, версия парадокса Рассела, которую мы здесь представили, на самом деле является теоремой Цермело ; ^[4] мы можем заключить из полученного противоречия, что мы должны отвергнуть гипотезу, что R _U ∈ U , тем самым опровергнув существование множества, содержащего все множества. Это стало возможным, поскольку мы использовали ограниченное понимание (как показано в ZFC ) в определении R _A выше, что, в свою очередь, влекло за собой, что

${\displaystyle R_{U}\in R_{U}\iff (R_{U}\in U\wedge R_{U}\notin R_{U}).}$

Если бы мы использовали неограниченное понимание (как, например, в системе Фреге), просто определив множество Рассела как , то сама система аксиом повлекла бы за собой противоречие, и не потребовалось бы никаких дополнительных гипотез. ^[4] ${\displaystyle R=\left\{\,x:x\not \in x\,\right\}}$

Несмотря на синтаксическое сходство между множеством Рассела (в любом варианте) и диагональным множеством Кантора, Алонзо Чёрч подчеркнул, что парадокс Рассела не зависит от соображений мощности и лежащих в его основе понятий, таких как взаимно-однозначное соответствие. ^[5]

История

Кантор по существу дал это доказательство в статье, опубликованной в 1891 году "Über eine elementare Frage der Mannigfaltigkeitslehre", ^[6] , где также впервые появляется диагональный аргумент в пользу несчетности действительных чисел (ранее он доказал несчетность действительных чисел другими методами ). Версия этого аргумента, которую он дал в этой статье, была сформулирована в терминах индикаторных функций на множестве, а не подмножествах множества. ^[7] Он показал, что если f — функция, определенная на X , значения которой являются двузначными функциями на X , то двузначная функция G ( x ) = 1 − f ( x )( x ) не принадлежит области значений f .

У Бертрана Рассела есть очень похожее доказательство в «Принципах математики» (1903, раздел 348), где он показывает, что пропозициональных функций больше , чем объектов. «Ибо предположим, что была затронута корреляция всех объектов и некоторых пропозициональных функций, и пусть phi- x будет коррелятом x . Тогда «не-phi- x ( x )», т. е. «phi- x не имеет места относительно x », является пропозициональной функцией, не содержащейся в этой корреляции; поскольку она истинна или ложна относительно x в зависимости от того, насколько phi- x истинен или ложен относительно x , и, следовательно, она отличается от phi- x для каждого значения x ». Он приписывает идею доказательства Кантору.

У Эрнста Цермело есть теорема (которую он называет «Теоремой Кантора»), которая идентична приведенной выше формулировке в статье, которая стала основой современной теории множеств («Untersuchungen über die Grundlagen der Mengenlehre I»), опубликованной в 1908 году. См. Теория множеств Цермело .

Обобщения

Теорема Ловера о неподвижной точке обеспечивает широкое обобщение теоремы Кантора на любую категорию с конечными произведениями следующим образом: ^[8] пусть будет такой категорией, и пусть будет конечным объектом в . Предположим, что является объектом в и что существует эндоморфизм , который не имеет неподвижных точек; то есть не существует морфизма , который удовлетворяет . Тогда не существует объекта из , такого, что морфизм может параметризовать все морфизмы . Другими словами, для каждого объекта и каждого морфизма попытка записать отображения как отображения вида должна исключить по крайней мере одно отображение . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle 1}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle Y}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \alpha :Y\to Y}$ ${\displaystyle y:1\to Y}$ ${\displaystyle \alpha \circ y=y}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle f:T\times T\to Y}$ ${\displaystyle T\to Y}$ ${\displaystyle T}$ ${\displaystyle f:T\times T\to Y}$ ${\displaystyle T\to Y}$ ${\displaystyle f(-,x):T\to Y}$ ${\displaystyle T\to Y}$

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

• Теорема Шредера–Бернштейна
• Первое доказательство несчетности Кантора
• Споры по поводу теории Кантора

Ссылки

1. Абхиджит Дасгупта (2013). Теория множеств: с введением в действительные точечные множества . Springer Science & Business Media . стр. 362–363. ISBN 978-1-4614-8854-5.
2. Lawrence Paulson (1992). Теория множеств как вычислительная логика (PDF) . Компьютерная лаборатория Кембриджского университета. стр. 14.
3. Грэм Прист (2002). За пределами мысли . Oxford University Press. С. 118–119. ISBN 978-0-19-925405-7.
4. Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work . Springer Science & Business Media. стр. 86–87. ISBN 978-3-540-49553-6.
5. Чёрч, А. [1974] "Теория множеств с универсальным множеством". в Трудах симпозиума Тарского. Труды симпозиумов по чистой математике XXV, под ред. Л. Хенкина, Providence RI, Второе издание с дополнениями 1979 г., стр. 297–308. ISBN 978-0-8218-7360-1 . Также опубликовано в International Logic Review 15 стр. 11–23. 
6. Кантор, Георг (1891), «Über eine elementare Frage der Mannigfaltigskeitslehre», Jahresbericht der Deutschen Mathematiker-Vereinigung (на немецком языке), 1 : 75–78, также в Георге Канторе, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts , E. Zermelo, 1932.
7. А. Канамори, «Пустое множество, синглтон и упорядоченная пара», стр. 276. Бюллетень символической логики, т. 9, № 3 (2003). Доступ 21 августа 2023 г.
8. Ф. Уильям Ловер; Стивен Х. Шануэль (2009). Концептуальная математика: первое введение в категории . Cambridge University Press. Сессия 29. ISBN 978-0-521-89485-2.

• Halmos, Paul , Naive Set Theory . Princeton, NJ: D. Van Nostrand Company, 1960. Перепечатано Springer-Verlag , New York, 1974. ISBN 0-387-90092-6 (издание Springer-Verlag). Перепечатано Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (издание в мягкой обложке).  
• Йех, Томас (2002), Теория множеств , Springer Monographs in Mathematics (3-е тысячелетие), Springer, ISBN 3-540-44085-2

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

• «Теорема Кантора», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Теорема Кантора». MathWorld .