Счётная бесконечность: отель Гильберта

В полностью занятом отеле с бесконечным числом номеров всегда найдётся место ещё для одного гостя.

Счётное множество — бесконечное множество, элементы которого можно занумеровать натуральными числами $1, 2, 3, \dots$

Бесконечность ведёт себя совсем не так, как конечные числа. Чтобы прочувствовать это, Давид Гильберт придумал мысленный отель с бесконечным числом номеров. Этот образ показывает: с бесконечностью можно делать то, что немыслимо для конечных множеств.

Парадокс полного отеля

Отель имеет номера $1, 2, 3, \dots$ — по одному на каждое натуральное число, и все они заняты. Приходит новый гость. В обычном отеле ему откажут, но в отеле Гильберта попросим каждого жильца переехать из номера $n$ в номер $n+1$:

$$n \longmapsto n + 1.$$

Номер 1 освободится, и новый гость заселится. А если приедет бесконечный автобус с гостями $1, 2, 3, \dots$? Попросим каждого жильца переехать из $n$ в $2n$ — освободятся все нечётные номера, и в них поселятся новоприбывшие.

# Заселяем бесконечный автобус: старые гости в чётные, новые — в нечётные
print("Размещение бесконечного автобуса в полном отеле:")
for old_guest in range(1, 6):
    print(f"  старый гость из номера {old_guest} -> номер {2 * old_guest}")
for new_guest in range(1, 6):
    print(f"  новый гость {new_guest} -> номер {2 * new_guest - 1}")

Вывод:

Размещение бесконечного автобуса в полном отеле:
  старый гость из номера 1 -> номер 2
  старый гость из номера 2 -> номер 4
  старый гость из номера 3 -> номер 6
  старый гость из номера 4 -> номер 8
  старый гость из номера 5 -> номер 10
  новый гость 1 -> номер 1
  новый гость 2 -> номер 3
  новый гость 3 -> номер 5
  новый гость 4 -> номер 7
  новый гость 5 -> номер 9

Как работает под капотом

Фокус в том, что между всеми гостями (старыми и новыми) и номерами удаётся установить взаимно однозначное соответствие — биекцию. Раз такое соответствие есть, множеств «столько же». Это определяющая черта счётной бесконечности: множество чётных чисел, нечётных, целых и даже всех рациональных дробей — все они равномощны натуральным, хотя интуиция шепчет, что «дробей же больше». Парадокс отеля показывает: для бесконечных множеств «часть может равняться целому». Чётных чисел «столько же», сколько всех натуральных, потому что $n \mapsto 2n$ — биекция.

Частые ошибки

Не переносите интуицию конечного на бесконечное: «отель полон» не означает «мест нет», если номеров бесконечно много. Счётность — это про существование нумерации, а не про порядок: рациональные числа счётны, хотя их нельзя выписать «по возрастанию». И «бесконечно много» — не число, а свойство; арифметика вроде $\infty + 1 = \infty$ работает иначе.

Итог

• Счётное множество нумеруется натуральными числами.
• В полном отеле Гильберта всегда есть место: сдвиг $n \mapsto n+1$.
• Биекция $n \mapsto 2n$ освобождает бесконечно много номеров.
• Для бесконечности часть может быть равномощна целому.