Новые исследования о пределах математической истины и границах математического знания

Данная статья является переводом. Оригинал здесь. Мне очень нравится делать переводы научных и научно-популярных статей, потому что, во-первых, так я и сам узнаю много нового, а во-вторых, несмотря на значительное развитие ИИ в последнее время, машинные переводы научных текстов всё еще оставляют желать лучшего, так что роботы, как мне кажется, еще очень не скоро заменят живых переводчиков. Статья на мой взгляд, очень интересна и имеет глубокие философские связи не только с Гильбертом и Гёделем, как и написано в самой статье, но также и с интуиционизмом Брауэра и его идеей об отказе от закона исключенного третьего, о чем в статье не написано. Эти моменты можем обсудить в комментариях, ну а сейчас: приятного чтения!

Работая над расширенной версией знаменитой 10-й проблемы Гильберта, две группы математиков расширили и область математического неизвестного.

Мир математики полон неразрешимых задачи. Теперь еще на одну такую задачу стало больше.

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

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

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

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

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

Главной среди них была его 10-я проблема. Она касается диофантовых уравнений: многочленов с целочисленными коэффициентами, таких как x² + y² = 5. Эти привычные для многих людей уравнения являются весьма важными объектами для исследований в математике. На протяжении тысячелетий математики искали целочисленные решения для них. В данном примере одно из решений — x = 1, y = 2 (поскольку 1² + 2² = 5). Другое решение — x = 2, y = -1.

Другие диофантовы уравнения, такие как x² + y² = 3, не имеют целочисленных решений. Десятая задача Гильберта заключалась в том, возможно ли всегда определить, имеет ли данное диофантово уравнение целочисленные решения. Существует ли алгоритм, который может это определить для каждого уравнения, или проблема неразрешима? Может быть, нет надежды на полный и систематический подход ко всей математике, или даже ко всем 23 проблемам Гильберта, но он может существовать, когда дело доходит до диофантовых уравнений, образуя своего рода микрокосм его оригинальной программы. "Эта проблема является естественной версией той мечты", — сказал Питер Койманс из Утрехтского университета.

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

Даже в самом простом виде математики скрывается неведомое.

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

"Проблема неразрешима для целых чисел, а затем, когда вы переходите к более сложным системам чисел, вы получаете разрешимость внезапно," — сказал Барри Мазур из Гарвардского университета и добавил: "Но где проходит рубеж между тем, что неразрешимо и тем, что внезапно становится разрешимым?"

В течение 50 лет после получения результатов Матиясевичем по 10-ой проблеме Гильберта, математики искали этот рубеж. Теперь Койманс и его давний коллега Карло Пагано из Университета Конкордия в Монреале, а также другая группа исследователей, работающая независимо, сделали важный шаг к достижению этой цели. Обе группы доказали, что для огромного и весьма значительного набора условий за пределами целых чисел также не существует общего алгоритма, чтобы определить, имеет ли любое данное диофантово уравнение решение. Работа не только позволяет математикам получить более точное представление о том, что они могут и не могут знать, но и дает им совершенно новый уровень контроля над одним из самых центральных объектов в математике.

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

Если начать с чисел 1 и -1, их можно комбинировать по-разному, чтобы получить все остальные целые числа. Но представьте, что вы начинаете с другого конечного набора чисел — например, 1, -1 и √2. Вы можете комбинировать эти числа различными способами, чтобы получить новую систему чисел, называемую кольцом целых чисел (такое название используют даже тогда, когда кольцо не содержит только целых чисел). Другие кольца целых чисел можно построить из наборов чисел, которые включают, например, квадратный корень из -1 (мнимая единица), или кубический корень из 2. Существует ли алгоритм, который может всегда определить, имеет ли данное диофантово уравнение решения, которые принадлежат одному из этих колец целых чисел?

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

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

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

Диофантовы уравнения также можно рассмотреть, как вычислительные устройства. Возьмите уравнение y = x². У него бесконечно много целочисленных решений. Если подставить различные целые числа для x и решить для y, значения, которые вы получите, будут принадлежать известному множеству целых чисел: совершенным квадратам. Легко представить компьютерную программу (то есть машину Тьюринга), которая выполняет аналогичную задачу: "Вычислить последовательность совершенных квадратов."

Другие диофантовы уравнения могут «кодировать» другие виды вычислений.

Чтобы решить оригинальную проблему Гильберта, математики опирались именно на эту идею. В работе, начатой Джулией Робинсон и другими около 1950 года и завершенной результатом Матиясевича в 1970 году, было показано, что для каждой машины Тьюринга существует соответствующее диофантово уравнение. "Это было полностью неожиданно," — сказал Гектор Пастен из Католического университета в Чили. "Диофантовых уравнений над целыми числами достаточно, чтобы определить, практически, все, что можно себе представить."

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

Иными словами, 10-ая проблема Гильберта неразрешима.

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

Полезная связь между машинами Тьюринга и диофантовыми уравнениями разрушается, когда уравнения допускают решения, отличные от целых чисел. Например, снова рассмотрим уравнение y = x². Если вы работаете в кольце целых чисел, которое включает √2, то получите новые решения, такие как x = √2, y = 2. Уравнение больше не соответствует машине Тьюринга, вычисляющей совершенные квадраты — и, более общо, диофантовы уравнения больше не могут кодировать проблему остановки.

Но в 1988 году аспирант Нью-Йоркского университета по имени Александра Шлапентох начала экспериментировать с идеями о том, как обойти эту проблему. К 2000 году она и другие сформулировали план. Предположим, что вы добавляете множество дополнительных членов к уравнению вроде y = x², которые магическим образом заставляют x снова быть целым числом, даже в другой системе чисел. Тогда вы можете восстановить соответствие машине Тьюринга. Можно ли сделать то же самое для всех диофантовых уравнений? Если да, это бы означало, что проблема Гильберта могла бы закодировать в себе проблему остановки в новой системе чисел.

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

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

С момента своей учебы в университете Коиманс размышлял о десятой проблеме Гильберта. На протяжении всего периода учебы в аспирантуре и всего своего сотрудничества с Пагано, она продолжала его привлекать. "Я проводил несколько дней каждый год, думая об этом и ужасно застревая. Я пробовал разные вещи, но всё было тщетно," — сказал Коиманс.

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

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

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

Они застряли. "У меня было это темное чувство," — сказал Коиманс. "Я начал подозревать, что мы что-то упускаем."

Затем, летом 2024 года, работая над другой проблемой, эти ученые снова использовали квадратичные повороты. Однажды ночью, в процессе этого исследования, Коиманс не мог уснуть, не переставая думать о десятой проблеме Гильберта.

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

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

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

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

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

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

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

Все знания имеют пределы. "Это напоминает нам, что есть вещи, которые просто недостижимы," — сказал Гранвилл. "Не важно, кто вы или что вы."

Мой научно-философский проект