Новый мост связывает странную математику бесконечности с компьютерной наукой

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сделать выбор

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

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

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

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

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

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

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

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

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

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

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

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

Для завершения раскрашивания вам придется использовать третий цвет, например, зеленый.

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

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

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

Раунд за раундом

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

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

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

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

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

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

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

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

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

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

Открытие двери

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

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

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

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

Задачей Бернштейна было найти более умный способ маркировки графиков.

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

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

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

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

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

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

Источник: www.quantamagazine.org