Парадокс Кантора

Парадо́кс Ка́нтора — парадокс теории множеств, который демонстрирует, что предположение о существовании множества всех множеств ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.

Формулировка

Предположим, что множество всех множеств $V=\{x\mid x=x\}$ существует. В этом случае справедливо $\forall x\forall T(x\in T\rightarrow x\in V)$, то есть всякое множество $T$ является подмножеством $V$. Но из этого следует $\forall T\;|T|\leqslant |V|$ — мощность любого множества не превосходит мощности $V$.

Но в силу аксиомы существования множества всех подмножеств для $V$, как и любого множества, существует множество всех подмножеств ${\mathcal {P}}(V)$, и по теореме Кантора $|{\mathcal {P}}(V)|=2^{|V|}>|V|$, что противоречит предыдущему утверждению. Следовательно, $V$ не может существовать, что вступает в противоречие с «наивной» гипотезой о том, что любое синтаксически корректное логическое условие определяет множество, то есть что $\exists y\forall z(z\in y\leftrightarrow A)$ для любой формулы $A$, не содержащей $y$ свободно.

Другая формулировка

Не существует максимального кардинального числа. В самом деле: пусть оно существует и равно $\mu$. Тогда по теореме Кантора $2^{\mu }>\mu$.

Выводы

Этот парадокс, открытый Кантором около 1899 года, обнаружил необходимость пересмотра «наивной теории множеств» (парадокс Рассела был открыт несколько позднее, около 1901 года) и стимулировал разработку строгой аксиоматики теории множеств. Схема аксиом $\exists y\forall z(z\in y\leftrightarrow A)$ отвергнута как противоречивая, вместо этого была разработана система ограничений на вид условия, задаваемого формулой $A$.

См. также

• Парадокс Бурали-Форти
• Парадокс всемогущества
• Парадокс Рассела