Кантор предсказал Wi-Fi за век до его изобретения? Как 150-летняя теория бесконечности объясняет работу интернета

Современная математика держится на тонком, но надёжном фундаменте — теории множеств. Обычно об этом почти не вспоминают: исследователи работают с функциями, операторами, вероятностями и структурами, полагаясь на хорошо знакомые аксиомы. Но существует направление, где сами свойства бесконечных объектов становятся центральной темой. Дескриптивная теория множеств изучает конструкции, которые многие математики предпочитают не трогать, — особенно необычные бесконечности, не укладывающиеся в привычные представления.

В 2023 году Антон Бернштейн, ныне сотрудник Калифорнийского университета в Лос-Анджелесе, обнаружил редкую и неожиданную связь: задачи о сложных бесконечных множествах можно переформулировать как вопросы о том, как взаимодействуют узлы в распределённых вычислительных системах. Две области, обычно живущие по разным правилам, внезапно пересеклись. Для логиков и информатиков это стало сюрпризом: первые работают с несчётными структурами и логическими схемами, вторые — с конечными сетями и алгоритмами. Но оказалось, что в ряде случаев оба подхода описывают одну и ту же ситуацию.

Само направление берёт начало в работах Георга Кантора. В 1874 году он показал, что бесконечности бывают разного масштаба: множество целых чисел и множество всех дробей равны по мощности, но оба меньше множества действительных чисел. Такие идеи восприняли неоднозначно, поэтому математики разработали другой подход к размеру — основанный не на подсчёте элементов, а на измерении длины, площади или объёма. Так возникли разные типы мер.

Например, отрезки [0,1] и [0,10] содержат одинаковое количество точек — они равны по количеству элементов, хотя один отрезок длиннее другого. Более сложные множества требуют других способов измерения. Некоторые настолько запутаны, что для них невозможно определить длину или площадь — такие называют неизмеримыми.

Дескриптивная теория множеств постепенно создала обширную карту подобных объектов. На верхних уровнях находятся самые понятные множества, ниже — структуры, настолько сложные, что доступные методы перестают работать. Эта иерархия помогает выбирать инструменты для задач в смежных областях — будь то теория вероятностей, динамические системы или анализ групповых действий.

В своих работах Бернштейн занимался графами — абстрактными структурами, состоящими из точек (узлов) и соединяющих их линий (рёбер). Его интересовали особенно сложные случаи, когда узлов бесконечно много и сама структура разбита на бесконечное количество отдельных компонентов. Такие графы не придуманы искусственно: они естественно возникают, когда математики изучают процессы, где что-то повторяется бесконечно — например, вращения фигур на плоскости, периодические явления или поведение динамических систем, которые со временем проходят через похожие состояния.

Один из наиболее наглядных примеров — окружность. Представим, что на ней выбрана точка. Если каждый шаг перемещать эту точку на фиксированную дугу, получится цепочка новых положений. При шаге, который можно записать в виде дроби (рациональное число), движение рано или поздно вернётся в исходную точку — возникает замкнутый цикл. Если же шаг выражается числом, не представимым в виде дроби (иррациональное число), повторений не будет: мы получим бесконечную последовательность точек, равномерно разбросанных по окружности.

Если начать такой процесс с другой начальной точки, получится новая последовательность, полностью независимая от первой. На окружности таких начальных точек бесконечно много, и каждая создаёт свою собственную цепочку. В итоге вся структура распадается на несчётное множество отдельных последовательностей, не пересекающихся друг с другом.

В такой системе встаёт классическая задача раскраски: каждому узлу нужно назначить цвет так, чтобы связанные ребром точки имели разные цвета. Самый простой путь — выбрать стартовый узел и чередовать цвета дальше. Но этот метод опирается на скрытую предпосылку: можно выбрать “первую точку” для каждой бесконечной цепочки. Это возможно лишь если использовать аксиому выбора — правило, позволяющее делать бесконечное количество независимых выборов. Проблема в том, что такая раскраска даёт несвязные, рассыпанные множества точек, длину которых невозможно определить в привычном смысле. Они не образуют непрерывных участков и поэтому не измеримы.

Чтобы получить структуры, с которыми можно работать как с геометрическими объектами, нужно красить не отдельные точки, а целые дуги между ними. Тогда каждая цветовая область превращается в непрерывный отрезок окружности, для которого можно вычислить длину. Однако здесь двух цветов уже недостаточно: в любом компоненте последний закрашиваемый участок неминуемо «примыкает» к предыдущему, и произойдёт совпадение цветов. Приходится вводить третий цвет, который устраняет эту коллизию и делает раскраску согласованной. Благодаря этому все цветовые области становятся измеримыми.

Бернштейн много лет разбирал такие задачи. А затем одно событие полностью изменило направление его мыслей. На докладе о распределённых алгоритмах — моделях, описывающих работу больших сетей, где каждый узел действует локально и видит только ближайших соседей, — обсуждали, как именно устройства договариваются между собой. В подобных системах каждый элемент сначала выбирает себе состояние, сообщает о нём окружающим, анализирует их ответы и решает, менять ли свой выбор. Затем цикл повторяется, пока вся сеть не придёт к устойчивой конфигурации.

В докладе говорилось о том, сколько таких шагов — «раундов» — требуется алгоритму, чтобы добиться корректной раскраски графа, например, чтобы соседние устройства использовали разные частоты связи. Именно эти пороги эффективности и поразили Бернштейна: они удивительно напоминали ограничения, которые встречаются в задачах об измеримых раскрасках бесконечных графов. Оказалось, что в обоих случаях изучают одно и то же явление — как локальная информация шаг за шагом распространяется по структуре. Только в одном случае структура конечная, а в другом — бесконечная.

Чтобы перенести идею локального алгоритма на граф с континуумом узлов, оставалась одна трудность: бесконечно плотной структуре невозможно назначить уникальные метки. Но допускается повторение, если в пределах заданного расстояния метки различаются. Бернштейн доказал, что такую схему маркировки можно построить всегда — независимо от того, насколько большой считается «локальная область» и сколько разных меток разрешено. Это открытие позволило перенести любой локальный алгоритм на бесконечный граф и тем самым получить измеримую раскраску, с которой можно работать методами теории меры.

Результат поразил и математиков, и специалистов по распределённым системам. Он показал прямую связь между вычислительными методами и свойствами сложных множеств. После публикации исследователи начали использовать эту связь по-новому. В одних проектах удалось получить результаты о деревьях и связанных динамических системах, рассматривая их как сетевые задачи. В других — методы теории множеств помогли уточнить оценки сложности некоторых алгоритмов.

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