Парадокс Кантора
 | Для улучшения этой статьи желательно: |
Парадо́кс Ка́нтора — парадокс теории множеств, который демонстрирует, что предположение о существовании множества всех множеств ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.
Формулировка
Предположим, что множество всех множеств [math]\displaystyle{ V = \{x \mid x = x\} }[/math] существует. В этом случае справедливо [math]\displaystyle{ \forall x \forall T (x \in T \rightarrow x \in V) }[/math], то есть всякое множество [math]\displaystyle{ T }[/math] является подмножеством [math]\displaystyle{ V }[/math]. Но из этого следует [math]\displaystyle{ \forall T\; |T| \leqslant |V| }[/math] — мощность любого множества не превосходит мощности [math]\displaystyle{ V }[/math].
Но в силу аксиомы множества всех подмножеств, для [math]\displaystyle{ V }[/math], как и любого множества, существует множество всех подмножеств [math]\displaystyle{ \mathcal P(V) }[/math], и по теореме Кантора [math]\displaystyle{ |\mathcal P (V)| = 2^{|V|} \gt |V| }[/math], что противоречит предыдущему утверждению. Следовательно, [math]\displaystyle{ V }[/math] не может существовать, что вступает в противоречие с «наивной» гипотезой о том, что любое синтаксически корректное логическое условие определяет множество, то есть что [math]\displaystyle{ \exists y \forall z (z \in y \leftrightarrow A) }[/math] для любой формулы [math]\displaystyle{ A }[/math], не содержащей [math]\displaystyle{ y }[/math] свободно.
Другая формулировка
Не существует максимального кардинального числа. В самом деле: пусть оно существует и равно [math]\displaystyle{ \mu }[/math]. Тогда по теореме Кантора [math]\displaystyle{ 2^\mu \gt \mu }[/math].
Выводы
Этот парадокс, открытый Кантором около 1899 года, обнаружил необходимость пересмотра «наивной теории множеств» (парадокс Рассела был открыт несколько позднее, около 1901 года) и стимулировал разработку строгой аксиоматики теории множеств. Схема аксиом [math]\displaystyle{ \exists y \forall z (z \in y \leftrightarrow A) }[/math] отвергнута как противоречивая, вместо этого была разработана система ограничений на вид условия, задаваемого формулой [math]\displaystyle{ A }[/math].