Как сравнить «яблоки» в «апельсины» математически? Ответив на этот вопрос, исследователи показали, что классификация групп чисел, называемых «абелевыми группами без кручения» — это предельно сложная задача. Подробностями о доказательстве делимся к старту флагманского курса по Data Science.

Если вы проводите перепись всех растений региона, вместо того чтобы подсчитывать каждое растение, вы можете упорядочить их по видам. Сделать это на некоторых участках побережья Тосканы не слишком сложно, говорит математик из Туринского университета Джанлука Паолини, потому что там в основном встречается одно растение — морская сосна (Pinus pinaster). Если бы вы оказались в тропических лесах Амазонки, то, напротив, столкнулись бы с гораздо большей проблемой в попытке разобраться в названиях и количестве всех видов. Сделать это в полном объёме, по всей вероятности, будет невозможно.

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

На протяжении десятилетий одна проблема классификации, связанная с определенным набором бесконечно больших объектов, которые называются абелевыми группами без кручения (далее — TFAB), ставила исследователей в тупик. Впервые эта проблема была поднята в 1989 году математиками Харви Фридманом и Ли Стэнли в работе, которая, по словам Паолини, «представила новый способ сравнения сложности проблем классификации для счётных структур, указывающий, что некоторые вещи сложнее других».

В опубликованной в начале года статье Паолини и его бывший постдокторант Сахарон Шелах из Еврейского университета Иерусалима решили вопрос о TFAB окончательно.

«Это, безусловно, важная работа, которая решает проблему более чем 30-летней давности», — утверждает Александр Кехрис из Калифорнийского технологического института.

Джанлука Паолини из Туринского университета (верхнее фото) и Сахарон Шелах из Еврейского университета Иерусалима ответили на вопрос, который уже несколько десятилетий не даёт покоя. Насколько сложно классифицировать определённые математические объекты, известные как абелевы группы без кручения. «[Их стратегия демонстрирует] невероятную сообразительность в преобразовании сложной проблемы в нечто более простое», — добавил Крис Ласковски из Университета Мэриленда, сотрудничавший с Шелахом над примерно 10 работами (но не над этой). Многие пытались и не добились успеха. Здорово, что всё улажено».

Счётные бесконечности

Поставленная Фридманом и Стэнли проблема включает класс бесконечных счётных структур, это помогает понять, как математики работают с такими, казалось бы, громоздкими величинами. Что для коллекции структур означает «счётность»? Натуральные числа (0, 1, 2, 3 …) бесконечны, но всё же считаются счётными, по этой же причине их иногда называют счётными числами. Называя эти числа последовательно, вы посчитаете их, затем они будут считаться самостоятельно. Количество элементов во множестве натуральных чисел, или его «кардинальность», обозначается алеф-ноль. Математики считают счётным любое множество того же размера, что и бесконечное множество натуральных чисел.

В отличие от них действительные числа, которые содержат натуральные, а также рациональные и иррациональные числа, также бесконечны, но они классифицируются как несчётные. Главная причина — их просто слишком много. С конца 1800-х годов мы знаем, что между 0 и 1 помещается больше действительных чисел, чем существует натуральных чисел: бесконечности не равны. Множество действительных чисел более кардинальны, чем натуральные числа, потому что и действительных чисел больше. Любое счётное множество чисел либо конечное, либо, если оно бесконечно, имеет кардинальность алеф-ноль.

Что же математики могут сделать с этими идеями? В работе Фридмана — Стэнли, а также в новой работе Паолини и Шелаха основное внимание уделялось изоморфизму (отношению эквивалентности) между структурами. Посмотрим на две бесконечные, но счётные группы чисел:

… −3, −2, −1, 0, 1, 2, 3 …  
… −6, −4, −2, 0, 2, 4, 6 …

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

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

Насколько сложным является сложное?

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

Один из рассмотренных Фридманом и Стэнли случаев касался семейства графов, каждый из которых имеет бесконечное и счётное число вершин. Для изоморфности графов необходимо, чтобы между вершинами одного графа и вершинами другого графа наблюдалось соответствие 1 к 1. И если две вершины соединены ребром в одном графе, то соответствующие вершины в другом графе также должны быть соединены ребром.

Фридман и Стэнли показали, что ответ на вопрос об изоморфности графов предельно сложен — настолько, насколько это вообще возможно. Это квалифицирует семейство всех счётных графов как «полнота Бореля» (они ввели этот термин в работе 1989 года из-за использования так называемой функции Бореля, разработанной математиком Эмилем Борелем).

Фридман и Стэнли задались вопросом: какие ещё классы счётных объектов обладают полнотой Бореля? Этот простой вопрос, как утверждает Ласковски, — «одна из центральных тем дескриптивной теории множеств».

Если у нас есть две [счётные] абелевы группы без кручения и мы спрашиваем, изоморфны ли они, какова сложность этого вопроса?

Сахарон Шелах, Еврейский университет Иерусалима

За прошедшие годы Фридман, Стэнли и другие выделили несколько классов математических объектов, удовлетворяющих критериям полноты Бореля, включая упрощённый вид графа — деревья и линейные порядки, набор чисел (натуральных или вещественных), буквально расположенных по порядку, подобно числам на числовой прямой.

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

Группы TFAB — это по сути группы чисел. Каждая TFAB состоит из счётного подмножества действительных чисел, которое следует определённым правилам группы, например является замкнутым при сложении и вычитании (так что для любых чисел p и q в этой группе p + q и p - q также появляются в группе). Он также подчиняется коммутативному закону (означающему, что p + q = q + p), отличительному признаку абелевых групп. Наконец, термин «без кручения» подразумевает, что если g — ненулевой элемент группы, то g + g никогда не равно нулю, так же как и g + g + g, g + g + g + g и так далее.

30 лет, рассказывает Шелах, математики задавались этим вопросом: «Если у нас есть две [счётные] абелевы группы без кручения и мы спрашиваем, изоморфны ли они, простой этот вопрос, умеренной сложности или сложный?»

По словам Кехриса, из всех проблем, поднятых в работе Фридмана-Стэнли, эта потребовала больше всего времени для решения. «Поэтому разумно назвать его самым сложным». Прежде чем уступить, нужно было попробовать новый подход.

В начале этого года Шелах и Паолини наконец-то нашли способ прорваться.

Трансформации между структурами

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

«Если вы хотите выяснить, является ли человек самым высоким в мире, как сделать это разумно? — спросил Паолини. —  Вместо того чтобы проверять всех на Земле, вы идёте к человеку, который считается самым высоким, и смотрите, кто выше».

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

Функция f должна удовлетворять такому соотношению: два счётных графа, G и H, изоморфны друг другу тогда и только тогда, когда f(G) и f(H) являются счётными TFAB, которые также изоморфны друг другу.

Задача была непростой: не существовало никакой доступной «технологии», которую математики могли бы использовать для соединения таких разных математических объектов; им пришлось изобрести эту технологию специально для этой проблемы.

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

Опять же, на самом деле сравниваются бесконечные группы яблок с бесконечными группами апельсинов. К счастью, сказал Шелах, учёные нашли способ упрощения. «Вместо того, чтобы иметь дело со всеми графами, можно [использовать] один универсальный граф» — столь огромный, что подграфы в нём содержат все возможные счётные графы.

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

Так Паолини и Шелах построили необходимую функцию, продемонстрировав, что графы и TFAB находятся в равных условиях. «Мы нашли способ связать абелевы группы без кручения с графами так, чтобы изоморфизм сохранялся», — рассказывает Паолини.

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

Новые джунгли исследований

Может ли этот результат привести к чему-то более общему? «Это ещё предстоит увидеть, — считает Кехрис, — но это вполне возможно». Паолини и Шелах на самом деле уже рассматривают возможность обобщения. Разрешив случай со счётными TFAB, они исследуют более широкий набор несчётных TFAB, которые, по словам Шелаха, «могут иметь другой ответ».

Есть основания полагать, что этот ответ исследователи могут узнать. «У Шела есть теория, — делится Ласковски, — что некоторые вопросы становятся проще, поднимаясь до более высокой кардинальности» — более высоких уровней бесконечности — потому что когда числа становятся действительно большими, расстояние между важными числами, такими как простые числа и квадраты целых чисел, увеличивается. В результате, сказал Шелах Ласковски, «воздух становится чище», что потенциально облегчает математикам восприятие вещей.

Статья о счётных TFAB уже имеет прямые практические последствия. «Теперь мы знаем, что вы ограничены в своих действиях», — сказал Шелах. Например, вы никогда не найдёте отличительных свойств (называемых инвариантами) этого семейства групп, которые автоматически скажут, изоморфны ли две TFAB. Это прямое следствие борелевской полноты TFAB.

«Мы доказали, что вообще не существует простого способа определения [изоморфизмов], — сказал Паолини. — Нет никакой середины. Это настолько сложно, насколько возможно».

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

Заглядывая в будущее, можно предположить, что математики откроют другие классы бесконечных, счётных структур, таких как графы и TFAB, которые максимально сложны при определении изоморфизмов.

Паолини заявил: «Вполне возможно, что мы найдём на Земле другие джунгли, столь же сложные, как Амазонка». Но, конечно, в этой аналогии ни одна из таких областей не будет сложнее другой.

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

Если вам интересна математика и то, как ИИ работает изнутри, то вы можете обратить внимание на курс математики для Data Science или наш флагманский курс по науке о данных. Также вы можете перейти на страницы каталога, чтобы увидеть, как мы готовим специалистов в других направлениях IT.