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

Эта статья содержит специальные символы . Без надлежащей поддержки рендеринга вы можете увидеть вопросительные знаки, прямоугольники и другие символы .

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

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

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

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

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

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

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

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

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

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

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

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

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

{\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 ]} Таким образом, нет $\xi \in A$ такой, что $f(\xi )=B$ ; другими словами, $B$ не в образе $f$ и $f$ не отображается на каждый элемент набора мощности $A$ , то есть, $f$ не является сюръективным.

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

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

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

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

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

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

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

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

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

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

\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 неэгоистичны.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

По сути, Кантор дал это доказательство в статье, опубликованной в 1891 году «К элементарному вопросу теории многообразия». ^{[ 6 ]} где также впервые появляется диагональный аргумент в пользу несчетности вещественных чисел ( ранее он доказал неисчислимость вещественных чисел другими методами ). Версия этого аргумента, которую он привел в этой статье, была сформулирована в терминах индикаторных функций на множестве, а не на его подмножествах. ^{[ 7 ]} Он показал, что если f — функция, определенная на X , значения которой являются двузначными функциями на X , то двузначная функция G ( x ) = 1 — f ( x )( x ) не находится в диапазоне f .

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

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

Обобщения

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

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Абхиджит Дасгупта (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 .
^ Черч, А. [1974] «Теория множеств с универсальным множеством». в материалах симпозиума Тарского. Труды симпозиумов по чистой математике XXV, изд. Л. Хенкин, Провиденс, Род-Айленд, второе издание с дополнениями, 1979 г., стр. 297–308. ISBN 978-0-8218-7360-1 . Также опубликовано в International Logic Review 15, стр. 11–23.
^ Кантор, Георг (1891), «Об элементарном вопросе теории многообразия» , Годовой отчет Немецкой ассоциации математиков (на немецком языке), 1 : 75–78 , т.е. в Георге Канторе, Сборник трактатов математического и философского содержания , Э. Цермело, 1932 год.
^ А. Канамори, « Пустое множество, синглтон и упорядоченная пара », стр.276. Бюллетень символической логики, том. 9, нет. 3, (2003). По состоянию на 21 августа 2023 г.
^ Ф. Уильям Ловер; Стивен Х. Шануэль (2009). Концептуальная математика: первое введение в категории . Издательство Кембриджского университета. Сессия 29. ISBN 978-0-521-89485-2 .

Халмос, Пол , Наивная теория множеств . Принстон, Нью-Джерси: Компания Д. Ван Ностранда, 1960. Перепечатано Springer-Verlag , Нью-Йорк, 1974. ISBN 0-387-90092-6 (издание Springer-Verlag). Перепечатано издательством Martino Fine Books, 2011 г. ISBN 978-1-61427-131-4 (издание в мягкой обложке).
Джех, Томас (2002), Теория множеств , Монографии Спрингера по математике (изд. 3-го тысячелетия), Springer, ISBN 3-540-44085-2

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

[Dasgupta2013-1] Перейти обратно: ^а ^б ^с ^д Абхиджит Дасгупта (2013). Теория множеств: введение в наборы реальных точек . Springer Science & Business Media . стр. 362–363. ISBN 978-1-4614-8854-5 .

[Paulson1992-2] Перейти обратно: ^а ^б Лоуренс Полсон (1992). Теория множеств как вычислительная логика (PDF) . Компьютерная лаборатория Кембриджского университета. п. 14.

[Priest2002-3] Перейти обратно: ^а ^б Грэм Прист (2002). За пределами мысли . Издательство Оксфордского университета. стр. 118–119. ISBN 978-0-19-925405-7 .

[Ebbinghaus2007-4] Перейти обратно: ^а ^б Хайнц-Дитер Эббингауз (2007). Эрнст Цермело: подход к его жизни и творчеству . Springer Science & Business Media. стр. 86–87 . ISBN 978-3-540-49553-6 .

[5] Черч, А. [1974] «Теория множеств с универсальным множеством». в материалах симпозиума Тарского. Труды симпозиумов по чистой математике XXV, изд. Л. Хенкин, Провиденс, Род-Айленд, второе издание с дополнениями, 1979 г., стр. 297–308. ISBN 978-0-8218-7360-1 . Также опубликовано в International Logic Review 15, стр. 11–23.

[6] Кантор, Георг (1891), «Об элементарном вопросе теории многообразия» , Годовой отчет Немецкой ассоциации математиков (на немецком языке), 1 : 75–78 , т.е. в Георге Канторе, Сборник трактатов математического и философского содержания , Э. Цермело, 1932 год.

[7] А. Канамори, « Пустое множество, синглтон и упорядоченная пара », стр.276. Бюллетень символической логики, том. 9, нет. 3, (2003). По состоянию на 21 августа 2023 г.

[LawvereSchanuel2009-8] Ф. Уильям Ловер; Стивен Х. Шануэль (2009). Концептуальная математика: первое введение в категории . Издательство Кембриджского университета. Сессия 29. ISBN 978-0-521-89485-2 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

v т и Теория множеств
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo