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

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

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

Предположим, что множество всех множеств $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$.

См. также

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