Теоретики дескриптивной теории множеств изучают узкоспециализированную математику бесконечности. Теперь они показали, что их проблемы можно переформулировать на конкретном языке алгоритмов.
Иллюстрация: Валентин Ткач для журнала QuantaСохранить эту историю Сохранить эту историю
Оригинальная версия этой статьи была опубликована в журнале Quanta Magazine.
Вся современная математика построена на фундаменте теории множеств — науки об организации абстрактных совокупностей объектов. Но в целом, математикам-исследователям не нужно об этом задумываться при решении своих задач. Они могут принять как должное, что множества ведут себя так, как они ожидают, и продолжать свою работу.
Исключением являются специалисты по дескриптивной теории множеств. Это небольшое сообщество математиков никогда не прекращало изучать фундаментальную природу множеств, особенно странные бесконечные множества, которые другие математики игнорируют.
Их область исследований стала намного менее изолированной. В 2023 году математик Антон Бернштейн опубликовал глубокую и удивительную связь между отдаленной математической областью дескриптивной теории множеств и современной информатикой.
Он показал, что все проблемы, касающиеся определённых типов бесконечных множеств, можно переформулировать как проблемы взаимодействия компьютерных сетей. Мост, соединяющий эти дисциплины, удивил исследователей с обеих сторон. Теоретики множеств используют язык логики, специалисты по информатике — язык алгоритмов. Теория множеств имеет дело с бесконечным, информатика — с конечным. Нет никаких оснований полагать, что их проблемы должны быть связаны, тем более эквивалентны.
«Это что-то действительно странное, — сказал Вацлав Рожон, специалист по информатике из Карлова университета в Праге. — Такого вообще не должно быть».
После результатов Бернштейна его коллеги начали исследовать, как перемещаться по этому мосту туда и обратно, чтобы доказывать новые теоремы по обе стороны, и как расширить этот мост на новые классы задач. Некоторые теоретики дескриптивных множеств даже начинают применять идеи из области информатики, чтобы реорганизовать ландшафт всей своей области и переосмыслить свое понимание бесконечности.
Антон Бернштейн занимается выявлением и изучением важных связей между теорией множеств и более прикладными областями, такими как информатика и динамические системы.
Фотография: Сиири Кивимаки«Всё это время мы работали над очень похожими проблемами, не общаясь напрямую друг с другом», — сказал Клинтон Конли, специалист по дескриптивной теории множеств из Университета Карнеги-Меллона. «Это просто открывает двери для всех этих новых форм сотрудничества».
Разбитые множества
Бернштейн был студентом, когда впервые услышал о дескриптивной теории множеств — как о примере области, которая когда-то имела значение, а затем пришла в упадок. Прошло больше года, прежде чем он понял, что профессор ошибался.
В 2014 году, будучи студентом первого курса магистратуры в Иллинойсском университете, Бернштейн посещал курс логики у Ануш Церунян, которая впоследствии стала одним из его научных руководителей. Она развеяла это заблуждение. «Вся заслуга в том, что я оказался в этой области, принадлежит ей», — сказал он. «Она действительно показала, что логика и теория множеств — это связующее звено, объединяющее все различные разделы математики».
Теория описательных множеств восходит к Георгу Кантору, который в 1874 году доказал существование бесконечности разных размеров. Множество целых чисел (0, 1, 2, 3, …), например, имеет тот же размер, что и множество всех дробей, но меньше, чем множество всех действительных чисел.
Ануш Церунян рассматривает дескриптивную теорию множеств как связующее звено, объединяющее различные разделы математики.
Фотография: Предоставлено Ануш Церунян.В то время математики испытывали глубокий дискомфорт от этого многообразия различных бесконечностей. «В это трудно поверить», — сказал Бернштейн, который сейчас работает в Калифорнийском университете в Лос-Анджелесе.
Отчасти в ответ на это неудобство математики разработали другое понятие размера — такое, которое описывает, например, длину, площадь или объем, которые может занимать множество, а не количество содержащихся в нем элементов. Это понятие размера известно как «мера» множества (в отличие от понятия размера Кантора, которое представляет собой «мощность» множества). Один из простейших типов меры — мера Лебега — количественно определяет длину множества. Хотя множество действительных чисел от нуля до 1 и множество действительных чисел от нуля до 10 являются бесконечными и имеют одинаковую мощность, первое имеет меру Лебега, равную 1, а второе — меру Лебега, равную 10.
Георг Кантор обнаружил, что математическая бесконечность может принимать множество различных форм и размеров.
Фотография: Визуальный архив Эмилио Сегре.Для изучения более сложных множеств математики используют другие типы мер. Чем сложнее множество, тем меньше способов его измерения. Теоретики описательной теории множеств задают вопросы о том, какие множества можно измерить в соответствии с различными определениями «меры». Затем они располагают их в иерархии на основе ответов на эти вопросы. На вершине находятся множества, которые можно легко построить и изучить, используя любое желаемое понятие меры. Внизу находятся «неизмеримые» множества, которые настолько сложны, что их вообще нельзя измерить. «Часто используется слово „патологические“», — сказал Бернштейн. «Неизмеримые множества действительно плохи. Они противоречат интуиции и ведут себя плохо».
Эта иерархия не только помогает теоретикам множеств составить карту своей области, но и дает им представление о том, какие инструменты они могут использовать для решения более типичных задач в других областях математики. Математикам в некоторых областях, таких как динамические системы, теория групп и теория вероятностей, необходима информация о размере используемых ими множеств. Положение множества в иерархии определяет, какие инструменты они могут использовать для решения своей задачи.
Таким образом, специалисты по дескриптивной теории множеств подобны библиотекарям, ухаживающим за огромной полкой с различными типами бесконечных множеств (и различными способами их измерения). Их задача — взять проблему, определить, насколько сложным является множество для её решения, и поместить её на соответствующую полку, чтобы другие математики могли её заметить.
Сделать выбор
Бернштейн принадлежит к группе библиотекарей, занимающихся задачами, связанными с бесконечными множествами узлов, соединенных ребрами, называемыми графами. В частности, он изучает графы, имеющие бесконечное множество отдельных частей, каждая из которых содержит бесконечное множество узлов. Большинство теоретиков графов не изучают такие графы; вместо этого они сосредотачиваются на конечных. Но такие бесконечные графы могут представлять и предоставлять информацию о динамических системах и других важных типах множеств, что делает их важной областью интереса для теоретиков дескриптивных множеств.
Вот пример бесконечного графа, который могли бы изучать Бернштейн и его коллеги. Начнём с круга, содержащего бесконечное множество точек. Выберем одну точку: это будет ваш первый узел. Затем переместимся на фиксированное расстояние по окружности. Это даст вам второй узел. Например, вы можете переместиться на одну пятую часть окружности. Соединим два узла ребром. Переместимся на такое же расстояние к третьему узлу и соединим его с предыдущим. И так далее.
Если каждый раз проходить одну пятую часть окружности, то для возвращения в исходную точку потребуется пять шагов. В общем случае, если расстояние можно выразить в виде дроби, узлы образуют замкнутый контур. Но если расстояние нельзя выразить в виде дроби, процесс будет продолжаться бесконечно. В результате получится бесконечное количество соединенных узлов.
Иллюстрация: Марк Белан/Quanta MagazineНо это еще не все: эта бесконечно длинная последовательность образует лишь первую часть вашего графа. Хотя она содержит бесконечное количество узлов, она не включает все точки на окружности. Чтобы сгенерировать остальные части графа, начните с одной из этих других точек. Теперь перемещайтесь на каждом шаге на такое же расстояние, как и в первой части. В итоге вы построите вторую бесконечную последовательность соединенных узлов, полностью не связанных с первой.
Фотография: Марк Белан/Quanta MagazineПовторите это для каждой возможной новой начальной точки на окружности. В результате вы получите граф, состоящий из бесконечного множества отдельных частей, каждая из которых будет состоять из бесконечного числа узлов.
Математики могут задаться вопросом, возможно ли раскрасить узлы в этом графе так, чтобы они подчинялись определенным правилам. Например, используя всего два цвета, можно ли раскрасить каждый узел в графе так, чтобы никакие два соединенных узла не были одного цвета? Решение может показаться простым. Посмотрите на первый участок вашего графа, выберите узел и раскрасьте его синим цветом. Затем раскрасьте остальные узлы этого участка в чередующемся порядке: желтый, синий, желтый, синий. Сделайте то же самое для каждого участка вашего графа: выберите узел, раскрасьте его синим цветом, затем чередуйте цвета. В конечном итоге, для решения вашей задачи вам понадобятся всего два цвета.
Иллюстрация: Марк Белан/Quanta MagazineНо для достижения такой раскраски приходилось полагаться на скрытое предположение, которое теоретики множеств называют аксиомой выбора. Это один из девяти фундаментальных строительных блоков, из которых строятся все математические утверждения. Согласно этой аксиоме, если начать с множества множеств, можно выбрать по одному элементу из каждого из этих множеств, чтобы создать новое множество — даже если у вас бесконечно много множеств на выбор. Эта аксиома полезна тем, что позволяет математикам доказывать всевозможные интересующие утверждения. Но она также приводит к странным парадоксам. Теоретики описательных множеств избегают её.
Ваш граф состоял из бесконечного множества элементов. Это соответствует бесконечному множеству множеств. Вы выбрали по одному элементу из каждого множества — первую точку, которую вы решили раскрасить синим цветом в каждом из элементов. Все эти синие точки образовали новое множество. Вы использовали аксиому выбора.
Это приводит к проблеме, когда вы раскрашиваете остальные узлы чередующимися синими и желтыми цветами. Вы раскрасили каждый узел (который имеет нулевую длину) отдельно, не понимая, как узлы связаны друг с другом, когда они находятся в разных частях графа. Это означает, что вы не можете описать множество всех синих узлов графа или множество всех его желтых узлов с точки зрения длины. Другими словами, эти множества неизмеримы. Математики не могут сказать о них ничего полезного.
Для теоретиков дескриптивного теории множеств это неудовлетворительно. Поэтому они хотят найти способ раскрасить граф непрерывным образом — способ, который не использует аксиому выбора и позволяет получить измеримые множества.
Для этого вспомните, как вы построили первую часть графа: вы выбрали узел на окружности и соединили его со вторым узлом, расположенным на некотором расстоянии. Теперь раскрасьте первый узел синим цветом, второй — жёлтым, а всю дугу между ними — синим. Аналогично, раскрасьте дугу между вторым и третьим узлами жёлтым. Раскрасьте третью дугу синим. И так далее.
Иллюстрация: Марк Белан/Quanta MagazineВскоре вы почти полностью обойдете круг — это значит, что вы присвоили цвет всем узлам вашего графа, кроме тех, которые попадают в небольшой оставшийся сегмент. Допустим, последняя раскрашенная вами дуга была желтой. Как раскрасить этот последний, меньший сегмент? Вы не можете использовать синий цвет, потому что эти узлы будут соединяться с узлами исходной дуги, которую вы раскрасили синим. Но вы также не можете использовать желтый цвет, потому что эти узлы соединяются с желтыми узлами из предыдущей дуги.
Чтобы завершить раскрашивание, вам нужно добавить третий цвет — например, зеленый.
Тем не менее, полученные в итоге наборы синих, желтых и зеленых узлов представляют собой лишь части окружности, а не разбросанные точки, как это было при использовании аксиомы выбора. Длину этих наборов можно вычислить. Они измеримы.
Поэтому теоретики описательной теории множеств помещают двухцветную версию проблемы на самый нижний уровень своей иерархии (для неизмеримых множеств), в то время как трехцветная проблема находится на гораздо более высоком уровне — среди задач, где можно применять множество понятий измерения.
Бернштейн посвятил годы учебы в аспирантуре изучению подобных задач раскрашивания, откладывая их одну за другой. Затем, вскоре после окончания учебы, он наткнулся на потенциальный способ отложить их все сразу — и показать, что эти задачи имеют гораздо более глубокую и математически значимую структуру, чем кто-либо предполагал.
Раунд за раундом
Время от времени Бернштейн с удовольствием посещает доклады по информатике, где графы являются конечными и представляют собой сети компьютеров.
В 2019 году одна из этих лекций изменила ход его карьеры. Она была посвящена «распределенным алгоритмам» — наборам инструкций, которые одновременно выполняются на нескольких компьютерах в сети для выполнения задачи без центрального координатора.
Предположим, в здании находится множество Wi-Fi-роутеров. Находящиеся рядом роутеры могут создавать помехи друг другу, если используют один и тот же частотный канал связи. Поэтому каждому роутеру необходимо выбрать канал, отличный от тех, которые используют его непосредственные соседи.
Специалисты по информатике могут переформулировать эту задачу как задачу раскраски графа: представим каждый маршрутизатор как узел и соединим соседние ребрами. Используя всего два цвета (представляющие два разных частотных канала), найдем способ раскрасить каждый узел так, чтобы никакие два соединенных узла не были одного цвета.
Но есть один нюанс: узлы могут взаимодействовать только со своими ближайшими соседями, используя так называемые локальные алгоритмы. Сначала каждый узел запускает один и тот же алгоритм и присваивает себе цвет. Затем он взаимодействует со своими соседями, чтобы узнать, как окрашены другие узлы в небольшой области вокруг него. После этого он снова запускает алгоритм, чтобы решить, сохранить ли свой цвет или изменить его. Этот шаг повторяется до тех пор, пока вся сеть не получит правильную раскраску.
Специалистов по информатике интересует, сколько шагов требуется для того или иного алгоритма. Например, любой локальный алгоритм, способный решить задачу маршрутизации, используя всего два цвета, должен быть невероятно неэффективным, но можно найти очень эффективный локальный алгоритм, если разрешено использовать три цвета.
На лекции, которую посещал Бернштейн, докладчик обсуждал эти пороговые значения для различных типов задач. Один из пороговых значений, как он понял, очень похож на пороговое значение, существующее в мире дескриптивной теории множеств — количество цветов, необходимых для измеримой раскраски определенных бесконечных графов.
Для Бернштейна это было не просто совпадением. Дело было не только в том, что специалисты по информатике похожи на библиотекарей, расставляющих задачи в зависимости от эффективности работы алгоритмов. Дело было не только в том, что эти задачи также можно было представить в виде графов и раскрасок.
Возможно, подумал он, у этих двух книжных полок было больше общего, чем просто это. Возможно, связь между этими двумя областями гораздо, гораздо глубже.
Возможно, все книги и их полки были идентичны, просто написаны на разных языках и нуждались в переводчике.
Открывая дверь
Бернштейн поставил перед собой задачу явно обозначить эту связь. Он хотел показать, что любой эффективный локальный алгоритм можно превратить в измеримый по Лебегу способ раскраски бесконечного графа (удовлетворяющий некоторым дополнительным важным свойствам). То есть, один из важнейших разделов в информатике эквивалентен одному из важнейших разделов в теории множеств (находящемуся высоко в иерархии).
Он начал с рассмотрения сетевых задач из лекции по информатике, сосредоточившись на их главном правиле — алгоритм любого заданного узла использует информацию только о его локальном окружении, независимо от того, содержит ли граф тысячу узлов или миллиард.
Для корректной работы алгоритму достаточно присвоить каждому узлу в заданной окрестности уникальный номер, чтобы он мог регистрировать информацию о соседних узлах и давать им инструкции. В конечном графе это сделать довольно легко: достаточно присвоить каждому узлу в графе свой уникальный номер.
Компьютерный учёный Вацлав Рожон использует недавно обнаруженную связь между теорией множеств и наукой о сетях для решения интересующих его задач. Фотография: Томаш Принц, Карлов университет.Если бы Бернштейн смог применить тот же алгоритм к бесконечному графу, это означало бы, что он мог бы раскрасить граф измеримым способом — решив задачу раскраски графов в рамках теории множеств. Но была проблема: эти бесконечные графы являются «несчётно» бесконечными. Нет способа однозначно пометить все их узлы.
Задача, стоявшая перед Бернштейном, заключалась в том, чтобы найти более оригинальный способ маркировки графиков.
Он понимал, что ему придётся повторно использовать метки. Но это было приемлемо, пока соседние узлы были помечены по-разному. Был ли способ присваивать метки, не используя случайно одну и ту же метку в одном и том же районе?
Бернштейн показал, что всегда есть способ — независимо от того, сколько меток вы решите использовать и сколько узлов находится в вашем локальном окружении. Это означает, что вы всегда можете безопасно расширить алгоритм из области информатики на область теории множеств. «Любой алгоритм в нашей схеме соответствует способу измеримой раскраски любого графа в рамках дескриптивной теории множеств», — сказал Рожон.
Доказательство стало неожиданностью для математиков. Оно продемонстрировало глубокую связь между вычислениями и определимостью, а также между алгоритмами и измеримыми множествами. Сейчас математики изучают, как использовать открытие Бернштейна. Например, в статье, опубликованной в этом году, Рожон и его коллеги выяснили, что можно раскрасить специальные графы, называемые деревьями, рассматривая ту же проблему в контексте информатики. Результат также показал, какие инструменты математики могли бы использовать для изучения соответствующих динамических систем деревьев. «Это очень интересный опыт — попытка доказать результаты в области, где я не понимаю даже базовых определений», — сказал Рожон.
Математики также работают над тем, чтобы переводить задачи в обратном направлении. В одном случае они использовали теорию множеств для доказательства новой оценки сложности решения определенного класса задач.
Мост Бернштейна — это не просто новый инструментарий для решения отдельных задач. Он также позволил теоретикам множеств получить более ясное представление о своей области. Было много проблем, которые они не знали, как классифицировать. Во многих случаях ситуация изменилась, потому что у теоретиков множеств теперь есть более организованные ресурсы, как у специалистов по информатике, которые могут их направлять.
Бернштейн надеется, что эта растущая область исследований изменит взгляд работающих математиков на работу теоретиков множеств — что они перестанут воспринимать её как далёкую и оторванную от реального математического мира. «Я пытаюсь это изменить, — сказал он. — Я хочу, чтобы люди привыкли думать о бесконечности».
Оригинальная статья перепечатана с разрешения журнала Quanta Magazine, независимого издания Фонда Саймонса, миссия которого заключается в повышении осведомленности общественности о науке путем освещения научных разработок и тенденций в области математики, физических и биологических наук.
Источник: www.wired.com
