Математическая логика
Бесконечность и кардиналы
Бесконечностей много - и одни из них «больше» других. Кантор был первым, кто строго это показал. Его диагональный метод стал одним из самых мощных инструментов математики - и прямым предшественником теорем Гёделя и неразрешимости Тьюринга.
- Сжатие данных: не все файлы можно сжать (счётно программ, несчётно файлов)
- Реляционные базы данных - счётные структуры; вещественные числа - несчётны
- Случайные числа: большинство вещественных чисел не вычислимы
Кантор и бесконечность
Георг Кантор разработал теорию множеств и трансфинитных чисел в 1870-90-х годах. Коллеги встретили его работы с недоверием: Кронекер называл Кантора «развратителем молодёжи», Пуанкаре - «болезнью». Сам Кантор страдал от депрессии. Посмертно его работы были признаны основой математики.
Счётные множества
Множество A счётно, если оно конечно или находится в биекции с ℕ. Бесконечное счётное множество имеет мощность ℵ₀. Примеры: ℤ, ℚ, все алгебраические числа, все конечные слова над конечным алфавитом.
Является ли ℚ (множество рациональных чисел) счётным?
Несчётные множества
Диагональный аргумент Кантора (1891): ℝ несчётно. Допустим, можно перечислить все вещественные числа в [0,1]. Строим число, отличающееся от n-го числа в n-й цифре. Оно не совпадает ни с одним числом в перечислении. Противоречие.
Диагональный аргумент - один из самых переиспользуемых в математике. Он доказывает несчётность ℝ, невыразимость предиката истины (Тарский), неразрешимость проблемы остановки (Тьюринг) и теоремы Гёделя о неполноте. Везде - одна и та же структура самореференции.
Какой инструмент использует диагональный аргумент Кантора для доказательства несчётности ℝ?
Теорема Кантора и иерархия бесконечностей
Теорема Кантора: для любого множества A выполняется |A| < |P(A)|. Это означает, что не существует наибольшего кардинала: ℵ₀ < 2^ℵ₀ < 2^(2^ℵ₀) < ... Бесконечностей бесконечно много.
Что следует из теоремы Кантора |A| < |P(A)|?
Гипотеза континуума
Гипотеза континуума (CH): не существует кардинала κ такого, что ℵ₀ < κ < 2^ℵ₀. То есть 2^ℵ₀ = ℵ₁ - мощность континуума равна следующему после ℵ₀ кардиналу.
Форсинг Коэна - революционный метод в теории множеств. Он позволяет систематически добавлять в модель ZFC новые множества, не нарушая аксиом. С тех пор форсинг стал основным инструментом для доказательства независимости утверждений от ZFC.
Независимость CH означает, что она ложна (или бессмысленна)
Независимость означает: ни CH, ни ¬CH не противоречат ZFC. Это не значит, что CH «не имеет ответа» - просто аксиомы ZFC недостаточно сильны для её решения. Можно принять дополнительные аксиомы (large cardinals), и вопрос может стать разрешимым.
Ситуация аналогична пятому постулату Евклида: он независим от остальных аксиом геометрии. Принимая его или отрицая, мы получаем разные, но одинаково непротиворечивые геометрии.
Гипотеза континуума?
Review the concept above.
Бесконечность и кардиналы: ключевые идеи
- Счётные множества: |A| = ℵ₀, биекция с ℕ; ℚ и ℤ счётны
- Диагональный аргумент: ℝ несчётно; тот же метод в теоремах Тарского, Гёделя, Тьюринга
- Теорема Кантора: |A| < |P(A)| - иерархия бесконечностей бесконечна
- Мощность континуума: 2^ℵ₀ = |ℝ| - где именно она стоит в иерархии ℵ?
- CH независима от ZFC (Гёдель 1938, Коэн 1963) - форсинг как метод
К рекурсивным функциям
Диагональный аргумент Кантора возвращается в теории вычислений: функций из ℕ в ℕ несчётно, а алгоритмов счётно - большинство функций невычислимы. Следующий урок строит теорию вычислимости.
- ml-10 — Related lesson
Вопросы для размышления
- Вычислимых вещественных чисел счётно много. Что это означает для практических вычислений?
- Если CH независима от ZFC, есть ли физический смысл в вопросе о существовании кардинала между ℵ₀ и |ℝ|?
- Форсинг Коэна позволяет добавлять в модель новые вещественные числа. Что значит «добавить» вещественное число, которого «раньше не было»?