Почему одни бесконечности больше других

Одна из самых красивых идей в математике звучит парадоксально: одни бесконечности больше других. В 1870-х годах Георг Кантор строго доказал, что действительных чисел больше, чем натуральных, хотя и тех и других бесконечно много.

Чтобы сравнить размеры двух множеств, Кантор предложил искать взаимно однозначное соответствие между элементами. Если элементы можно разбить на пары без остатка, множества равны по размеру. Для натуральных и чётных чисел такое соответствие строится легко, поэтому их поровну, хотя чётные и кажутся «половиной» натуральных.

С действительными числами такой фокус не проходит. Кантор применил диагональный аргумент. Предположим, что все действительные числа удалось выписать в пронумерованный список. Тогда можно построить новое число, у которого первый знак отличается от первого числа списка, второй знак от второго числа, и так далее. Такого числа в списке заведомо нет, а значит, перечислить все действительные числа невозможно.

Дальше Кантор обобщил результат. Для любого множества множество всех его подмножеств строго больше исходного. Значит, самой большой бесконечности не существует: за каждой из них всегда идёт ещё большая. Так выстраивается бесконечная лестница мощностей.

Для разработчиков важно, что диагональный метод оказался не только красивым, но и рабочим инструментом. Алан Тьюринг применил ту же идею, чтобы доказать неразрешимость проблемы остановки: невозможно написать универсальный алгоритм, который для любой программы заранее определит, завершится ли она. Идея Кантора о разных размерах бесконечности стала основой теории вычислимости.

Источник: https://x.com/Math_files/status/2066755148777439382