Введение

Бесконечное множество, которое не счетно

В математике несчетное множество, неформально, — это бесконечное множество, содержащее слишком много элементов, чтобы их можно было пересчитать. Несчетность множества тесно связана с его кардинальным числом: множество несчетно, если его кардинальное число больше алеф-нуль, кардинальности натуральных чисел.

Характеристики

Существует множество эквивалентных характеристик несчетности. Множество X несчетно тогда и только тогда, когда выполняется одно из следующих условий:
Не существует инъективной функции (следовательно, не существует биекции) из X в множество натуральных чисел. X непусто и для любой ω-последовательности элементов X существует хотя бы один элемент X, не входящий в неё. Иными словами, X непусто и не существует сюръективной функции из натуральных чисел в X. Кардинальность X не является конечной и не равна ℵ₀ (алеф-нуль). Кардинальность X строго больше ℵ₀.
Первые три из этих характеристик могут быть доказаны эквивалентными в теории множеств Цермело — Френкеля без аксиомы выбора, но эквивалентность третьей и четвертой не может быть доказана без дополнительных принципов выбора.

Свойства

Если неисчислимое множество X является подмножеством множества Y, то множество Y неисчислимо.

Примеры

Наиболее известным примером неисчислимого множества является множество R всех действительных чисел; диагональный аргумент Кантора показывает, что это множество неисчислимо. Метод доказательства диагонализацией также может быть использован для демонстрации неисчислимости других множеств, таких как множество всех бесконечных последовательностей натуральных чисел и множество всех подмножеств множества натуральных чисел. Кардинальность R часто называют кардинальностью континуума и обозначают , или , или (бет один). Множество Кантора является неисчислимым подмножеством R. Множество Кантора — это фрактал, имеющий размерность Хаусдорфа больше нуля, но меньше единицы (R имеет размерность один). Это пример следующего факта: любое подмножество R с размерностью Хаусдорфа строго больше нуля должно быть неисчислимым. Другим примером неисчислимого множества является множество всех функций из R в R. Это множество даже "более неисчислимо", чем R, в том смысле, что его кардинальность равна (бет два), что больше, чем .
Более абстрактным примером неисчислимого множества является множество всех счётных ординальных чисел, обозначаемое Ω или ω1. Кардинальность Ω обозначается (алеф один). Можно показать, используя аксиому выбора, что это наименьшее неисчислимое кардинальное число. Следовательно, либо , кардинальность действительных чисел, равна , либо она строго больше. Георг Кантор первым поставил вопрос о том, равна ли в 1900 году Давид Гильберт сформулировал этот вопрос как первую из своих 23 проблем. Утверждение о том, что , теперь называется гипотезой континуума и известно, что оно независимо от аксиом Цермело — Френкеля для теории множеств (включая аксиому выбора).