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