Давайте поговорим о бесконечности. Она постоянно присутствует в математике как абстракция. Вспомним число е, про которое подробнее я уже писал. Оно получается как предел --- бегай в банк много раз, и получишь хорошее приближение. Число "пи" тоже может быть получено, как предел длины правильного многоугольника, вписанного в окружность единичного диаметра. Никакой многоугольник окружностью не является (хоть и похож), но предел существует.
Давайте для начала вспомним забавный пример бесконечной гостиницы. Пусть есть бесконечная гостиница с номерами 1, 2, 3 и так далее. Она вся заполнена. Можно ли поселить туда постояльца?
Можно. Для этого надо переселить постояльца из номера 1 в номер 2, из 2 в 3 и так далее. Всем хватит места.
И да, если каждый день брать в долг 10 рублей и отдавать один, то "после" завершения бесконечного процесса все довольны: i-ый рубль был отдан в i-ый день.
Можно разместить даже всех пассажиров бесконечного автобуса в полностью заполненной бесконечной гостинице, освободив нечетные номера путем переселения постояльца из номера n в номер 2n.
А что, если в гостиницу приехало бесконечно много бесконечных автобусов? Можно всех разместить?
Можно! Правда, здесь важно, чтобы автобусы имели номера и сиденья в них тоже были пронумерованы. Пусть гостиница для простоты пустая --- это просто еще один автобус. Итак, расселим сначала первых двух пассажиров первых двух автобусов. Потом первых трех из первых трех (за вычетом тех, кого уже поселили). И так далее. Ясно, что каждый пассажир через конечное число шагов получит номер.
А вот если автобусы не пронумерованы и все стоят в них без мест, то сначала надо упорядочить и автобусы, и пассажиров --- а чтобы сделать это, надо использовать аксиому выбора, о которой как нибудь в другой раз.
Может возникнуть впечатление, что бесконечные множества все счетные --- у всех элементы можно пересчитать. Но это не так. Применительно к гостинице, предположим, что она вся заполнена и постояльцев попросили нарисовать разные планы расселения --- пометить нулями и единицами список номеров --- по одному плану на постояльца.
Легко доказать, что все планы нарисованы не будут. Возьмем план из первой комнаты и посмотрим, что стоит против первого номера. Если ноль, поставим единицу, а если единица --- поставим ноль. Далее определим аналогично символ для номера два, три и так далее. Получим некий план расселения, но его никто не мог нарисовать. В самом деле, его не мог нарисовать постоялец из номера 42, например, потому что у 42 комнаты разные символы. И это касается любого номера.
Метод любопытен и носит название диагонального. С его помощью, например, доказывается теорема Гёделя о неполноте.
Теперь почему это важно --- ведь не бывает бесконечных гостиниц. Рассмотрим пространство C непрерывных функций на отрезке. Нормой (аналог модуля или длины вектора) является максимум абсолютной величины функции на отрезке. Сферой называется множество всех функций с нормой 1.
Можно ли сферу стянуть по себе в точку? Интуиция подсказывает, что нельзя. Но в C --- можно. В три этапа:
- Берем функцию f(x) и преобразуем так: на отрезке [0,t] функция равна f(tx), на отрезке [t,1] она равна f(1). Параметр t плавно мерняем от 1 до 0.5. Норма остается единицей --- все точки сферы по ней и движутся.
- Берем полученную функцию и не меняем ее на отрезке [0.0.5], а на отрезке [0.5,1] меняем линейно: y= f(1)+(2x-1)(t-f(1)), t от f(1) до 1. При этом левый конец "приклеен" к графику f, а правых поднимается до единицы. Норма остается опять же единичной. Полученную функцию обозначим g(x).
- Теперь стягиваем функцию к константе, равной единице: t+(1-t)g(x), t от 0 до 1.
То есть любая точка сферы, плавно двигаясь по сфере, прибывает в одну и ту же точку. Сфера стягивается в точку. По себе. Без разрывов.
Теперь возвращаемся в гостиницу. Планы расселения --- это двоичные функции на множестве натуральных чисел, или вещественные числа из отрезка [0,1] в двоичной записи, или подмножества натурального ряда. Все это --- примеры множеств мощности континуума. То есть функций натурального аргумента, вещественных чисел и подмножеств принципиально больше, чем натуральных чисел.
Задачка: у царя непустое множество подданных, каждое непустое подмножество является тайным обществом. Царь хочет завербовать в каждом обществе агента, но один подданный может освещать только одно общество. Доказать, что царю не хватит подданных для агентуры.
Однако вычислимых функций --- тех, для вычисления которых можно написать программу --- счетное множество, ведь все тексты можно пересчитать, а программы --- лишь часть всех текстов. Получается, что почти все функции невычислимы.
Более того, почти все числа на отрезке [0,1] невычислимы. Вычислимое число --- это то, знаки которого выдает по их номерам вычислимая функция. Получается, что все числа, которые вы можете назвать, указать как решение уравнения, некоторой предел, алгоритм генерации цифр или еще как-то описать число текстом --- лишь ничтожная часть всех чисел.
И это удивительно.