В теории множеств парадокс Кантора утверждает, что не существует множества всех мощностей . Это вытекает из теоремы о том, что не существует наибольшего кардинального числа . В неформальных терминах парадокс заключается в том, что совокупность всех возможных «бесконечных размеров» не только бесконечна, но и настолько бесконечно велика, что ее собственный бесконечный размер не может быть ни одним из бесконечных размеров в совокупности. Трудность решается в аксиоматической теории множеств, когда объявляется, что эта совокупность не является множеством, а является собственным классом ; в теории множеств фон Неймана–Бернайса–Геделя из этого и аксиомы ограничения размера следует , что этот собственный класс должен находиться во взаимной однозначности с классом всех множеств. Таким образом, не только бесконечно много бесконечностей, но эта бесконечность больше любой из бесконечностей, которые она перечисляет.
Этот парадокс назван в честь Георга Кантора , которому часто приписывают его первое определение в 1899 году (или между 1895 и 1897 годами). Как и ряд «парадоксов», он на самом деле не является противоречивым, а лишь указывает на ошибочную интуицию, в данном случае о природе бесконечности и понятии множества. Иными словами, он парадоксален в рамках наивной теории множеств и, следовательно, демонстрирует, что небрежная аксиоматизация этой теории непоследовательна.
Для того, чтобы сформулировать парадокс, необходимо понять, что кардинальные числа полностью упорядочены , так что можно говорить о том, что одно больше или меньше другого. Тогда парадокс Кантора:
Этот факт является прямым следствием теоремы Кантора о мощности множества элементов.
Другим следствием теоремы Кантора является то, что кардинальные числа составляют правильный класс . То есть, они не могут быть собраны вместе как элементы одного множества. Вот несколько более общий результат.
Поскольку кардинальные числа вполне упорядочены индексацией с помощью порядковых чисел (см. Кардинальное число, формальное определение ), это также устанавливает, что не существует наибольшего порядкового числа; наоборот, последнее утверждение подразумевает парадокс Кантора. Применяя эту индексацию к парадоксу Бурали-Форти, мы получаем еще одно доказательство того, что кардинальные числа являются собственным классом, а не множеством, и (по крайней мере, в ZFC или в теории множеств фон Неймана–Бернайса–Геделя ) из этого следует, что существует биекция между классом кардиналов и классом всех множеств. Поскольку каждое множество является подмножеством этого последнего класса, а каждая мощность является мощностью множества (по определению!), это интуитивно означает, что «мощность» набора кардиналов больше мощности любого множества: она более бесконечна, чем любая истинная бесконечность. Такова парадоксальная природа «парадокса» Кантора.
Хотя обычно считается, что Кантор первым определил это свойство кардинальных множеств, некоторые математики приписывают эту честь Бертрану Расселу , который сформулировал похожую теорему в 1899 или 1901 году.