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

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

Исключением являются специалисты по дескриптивной теории множеств. Это небольшое сообщество математиков продолжает изучать фундаментальную природу множеств, особенно странные бесконечные множества, которые другие математики игнорируют. 

В последнее время их область исследований привлекает всё больше внимания. В 2023 году математик Антон Бернштейн опубликовал статью о глубокой и удивительной связи между дескриптивной теорией множеств и современной информатикой. 

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

«Это что-то действительно странное, — сказал Вацлав Рожон, специалист по информатике из Карлова университета в Праге. — Такого вообще не должно быть». 

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

«Всё это время мы работали над очень похожими проблемами, не общаясь напрямую друг с другом», — сказал Клинтон Конли, специалист по дескриптивной теории множеств из Университета Карнеги-Меллона. «Это открывает двери для новых форм сотрудничества». 

Странные множества

Бернштейн был студентом, когда впервые услышал о дескриптивной теории множеств — как о примере области, которая когда-то имела значение, а затем пришла в упадок. Прошло больше года, прежде чем он понял, что это широко распространённое мнение было ошибочным. 

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

Дескриптивная теория множеств восходит к Георгу Кантору, который в 1874 году доказал существование бесконечностей разных размеров. Множество целых чисел (0, 1, 2, 3, …) имеет тот же размер, что и множество всех рациональных дробей, но оно меньше, чем множество всех вещественных чисел.

В XIX веке математики испытывали глубокий дискомфорт от многообразия различных бесконечностей. 

Отчасти в ответ на это неудобство математики разработали другое понятие размера — такое, которое описывает, например, длину, площадь или объем, занимаемые множеством, а не количество содержащихся в нем элементов. Это понятие размера известно как «мера» множества (в отличие от понятия размера Кантора, которое представляет собой «мощность» множества). Один из простейших типов меры — мера Лебега — количественно определяет длину множества. Хотя множество действительных чисел от нуля до 1 и множество действительных чисел от нуля до 10 — бесконечные и имеют одинаковую мощность, первое имеет меру Лебега, равную 1, а второе — меру Лебега, равную 10. 

Для изучения более сложных множеств математики используют другие типы мер. Чем сложнее множество, тем меньше способов его измерить. Специалисты по теории дескриптивных множеств пытаются выяснить, какие множества можно измерить в соответствии с различными определениями «меры». Затем они располагают их в иерархии на основе ответов на эти вопросы. На вершине находятся множества, которые можно легко построить и изучить, используя любое желаемое понятие меры. Внизу — сложные неизмеримые множества. «Часто используется слово „патологические“», — сказал Бернштейн. «Неизмеримые множества действительно плохи. Они противоречат интуиции и ведут себя плохо». 

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

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

Совершая выбор

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

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

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

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

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

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

Но для получения такого решения приходилось полагаться на скрытое предположение, которое специалисты по теории множеств называют аксиомой выбора. Это один из девяти фундаментальных строительных блоков аксиоматической теории множеств (известной также как теория Цермело-Френкеля). Согласно этой аксиоме, можно выбрать по одному элементу из набора множеств, чтобы создать новое множество — даже если у вас бесконечно много множеств на выбор. Эта аксиома позволяет математикам доказывать всевозможные утверждения. Но она также приводит к странным парадоксам. Приведем пример. 

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

Это приводит к проблеме, когда вы красите остальные узлы чередующимися синими и жёлтыми цветами. Вы раскрасили каждый узел (который имеет нулевую длину) отдельно, не понимая, как узлы связаны друг с другом, когда они находятся в разных частях графа. Это означает, что вы не можете описать множество всех синих узлов графа или множество всех его жёлтых узлов с точки зрения длины. Другими словами, эти множества неизмеримы. Математики не могут сказать о них ничего полезного. 

Для специалистов по дескриптивной теории множеств это неприемлемо. Поэтому они хотят найти способ раскрасить граф непрерывным образом — способ, который не использует аксиому выбора и позволяет получить измеримые множества. 

Для этого вспомните, как вы построили первую часть графа: вы выбрали узел на окружности и соединили его со вторым узлом, расположенным на некотором расстоянии. Теперь раскрасьте первый узел синим цветом, второй — жёлтым, а всю дугу между ними — синим. Аналогично, раскрасьте дугу между вторым и третьим узлами жёлтым. Раскрасьте третью дугу синим. И так далее. 

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

Чтобы завершить раскрашивание, вам нужно добавить третий цвет — например, зелёный. 

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

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

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

Круг за кругом

Время от времени Бернштейн с удовольствием посещает конференции по информатике, где графы являются конечными и представляют собой сети компьютеров. 

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

Предположим, в здании находится множество Wi-Fi роутеров. Находящиеся рядом роутеры могут создавать помехи друг другу, если используют одну и ту же частоту. Поэтому каждому роутеру необходимо выбрать частоту, отличную от тех, которые используют его непосредственные соседи. 

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

Но есть один нюанс: узлы могут взаимодействовать только с ближайшими соседями, используя так называемые локальные алгоритмы. Сначала каждый узел запускает один и тот же алгоритм и присваивает себе цвет. Затем он опрашивает соседние узлы своих соседей, чтобы узнать, как они окрашены. После этого он снова запускает алгоритм, чтобы решить, сохранить ли свой цвет или изменить его. Этот шаг повторяется до тех пор, пока вся сеть не получит правильную раскраску. 

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

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

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

Возможно, подумал он, у этих двух проблем было больше общего. Возможно, связь между этими двумя областями гораздо, гораздо глубже. 

Возможно, их «книги» были идентичны, просто написаны на разных языках — и нуждались в переводчике. 

Открывая дверь

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

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

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

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

Задача заключалась в том, чтобы найти более оригинальный способ маркировки графов. 

Он понимал, что ему придётся повторно использовать метки. Но это было приемлемо, пока соседние узлы были помечены по-разному. Был ли способ присваивать метки, не используя случайно одну и ту же метку в одном и том же районе? 

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

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

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

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

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

Автор перевода @arielf

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.