Десятая проблема Гильберта - Hilberts tenth problem

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

Например, диофантово уравнение ${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$ имеет целочисленное решение: ${\displaystyle x=1,\ y=2,\ z=-2}$. Напротив, диофантово уравнение ${\displaystyle x^{2}+y^{2}+1=0}$ такого решения нет.

Десятая проблема Гильберта решена, и ответ на нее отрицательный: такого общего алгоритма не существует. Это результат совместной работы Мартин Дэвис, Юрий Матиясевич, Хилари Патнэм и Джулия Робинсон который охватывает 21 год, Матиясевич завершил теорему в 1970 году.^[1] Теорема теперь известна как Теорема Матиясевича или теорема MRDP.

Фон

Оригинальная рецептура

Гильберт сформулировал проблему следующим образом:^[2]

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

Слова «процесс» и «конечное число операций» означают, что Гильберт просил алгоритм. Термин «рациональное целое число» просто относится к целым числам, положительным, отрицательным или нулевым: 0, ± 1, ± 2, .... Итак, Гильберт просил разработать общий алгоритм, чтобы решить, является ли данный многочлен Диофантово уравнение с целыми коэффициентами имеет решение в целых числах.

Проблема Гильберта не связана с поиском решений. Он только спрашивает, можем ли мы вообще решить, существует ли одно или несколько решений. Ответ на этот вопрос отрицательный, в том смысле, что «невозможно разработать процесс» для ответа на этот вопрос. Говоря современным языком, 10-я проблема Гильберта - это неразрешимая проблема. Хотя маловероятно, что Гильберт предполагал такую ​​возможность, прежде чем перейти к перечислению проблем, он прозорливо заметил:^[3]

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

Доказательство неразрешимости 10-й проблемы является правильным ответом даже в терминах Гильберта, поскольку это доказательство «невозможности решения».

Диофантовы множества

Основная статья: Диофантовый набор

В диофантовом уравнении есть два типа переменных: параметры и неизвестные. Диофантово множество состоит из параметров, для которых разрешимо диофантово уравнение. Типичный пример - линейное диофантово уравнение с двумя неизвестными,

${\displaystyle a_{1}x_{1}+a_{2}x_{2}=a_{3}}$,

где уравнение разрешимо, когда наибольший общий делитель из ${\displaystyle a_{1},a_{2}}$ разделяет ${\displaystyle a_{3}}$. Значения для ${\displaystyle a_{1},a_{2},a_{3}}$ которые удовлетворяют этому ограничению, являются диофантовым множеством, и приведенное выше уравнение является его диофантовым определением.

Диофантовы определения могут быть предоставлены как одновременными системами уравнений, так и отдельными уравнениями, поскольку система

${\displaystyle p_{1}=0,\ldots ,p_{k}=0}$

эквивалентно единственному уравнению

${\displaystyle p_{1}^{2}+\cdots +p_{k}^{2}=0.}$

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

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

Рекурсивно перечислимые множества

А рекурсивно перечислимый набор можно охарактеризовать как тот, для которого существует алгоритм это в конечном итоге прекратится, когда член набора будет предоставлен как вход, но может продолжаться бесконечно, если вход не является членом. Это было развитие теория вычислимости (также известная как теория рекурсии), которая предоставила точное объяснение интуитивного понятия алгоритмической вычислимости, тем самым сделав понятие рекурсивной перечислимости совершенно строгим. Очевидно, что диофантовы множества рекурсивно перечислимы. Это связано с тем, что можно расположить все возможные кортежи значений неизвестных в последовательности, а затем для данного значения параметра (ов) тестировать эти кортежи один за другим, чтобы увидеть, являются ли они решениями соответствующего уравнения. Неразрешимость десятой проблемы Гильберта является следствием того удивительного факта, что верно обратное:

Любое рекурсивно перечислимое множество диофантово.

Этот результат известен как Теорема Матиясевича (потому что он обеспечил решающий шаг, завершивший доказательство) и Теорема MRDP (за Юрий Матиясевич, Джулия Робинсон, Мартин Дэвис, и Хилари Патнэм ). Потому что существует рекурсивно перечислимое множество, которое не вычислимо, неразрешимость десятой проблемы Гильберта является непосредственным следствием. На самом деле можно сказать больше: существует многочлен

${\displaystyle p(a,x_{1},\ldots ,x_{n})}$

с целыми коэффициентами такими, что множество значений ${\displaystyle a}$ для которого уравнение

${\displaystyle p(a,x_{1},\ldots ,x_{n})=0}$

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

История

Год	События
1944	Эмиль Леон Пост заявляет, что десятая проблема Гильберта «требует доказательства неразрешимости».
1949	Мартин Дэвис использует Курт Гёдель метод применения Китайская теорема об остатках как трюк кодирования, чтобы получить его нормальную форму для рекурсивно перечислимых множеств: ${\displaystyle \left\{a\mid \exists y\forall k\leqslant y\exists x_{1},\ldots ,x_{n}:p\left(a,k,y,x_{1},\ldots ,x_{n}\right)=0\right\}}$ куда ${\displaystyle p}$ - многочлен с целыми коэффициентами. Чисто формально, только ограниченный универсальный квантор препятствует тому, чтобы это определение было диофантовым. Используя неконструктивное, но простое доказательство, он выводит в качестве следствия этой нормальной формы, что множество диофантовых множеств не замкнуто относительно дополнения, показывая, что существует диофантово множество, дополнение которого не является диофантовым. Поскольку рекурсивно перечислимые множества также не закрываются при дополнении, он предполагает, что эти два класса идентичны.
1950	Джулия Робинсон, не зная о работе Дэвиса, исследует связь экспоненциальной функции с проблемой и пытается доказать, что EXP, набор троек ${\displaystyle (a,b,c)}$ для которого ${\displaystyle a=b^{c}}$, является диофантовым. Не добившись успеха, она делает следующее гипотеза (позже назывался J.R.): Есть диофантовый набор ${\displaystyle D}$ пар ${\displaystyle (a,b)}$ такой, что ${\displaystyle (a,b)\in D\Rightarrow b<a^{a}}$ и за каждый позитив ${\displaystyle k,}$ Существует ${\displaystyle (a,b)\in D}$ такой, что ${\displaystyle b>a^{k}.}$ Используя свойства уравнения Пелла, она доказывает, что из J.R. следует, что EXP диофантово, а также биномиальные коэффициенты, факториал и простые числа.
1959	Работая вместе, Дэвис и Патнэм изучают экспоненциальные диофантовы множества: множества, определяемые диофантовыми уравнениями, в которых некоторые показатели могут быть неизвестны. Используя нормальную форму Дэвиса вместе с методами Робинсона и предполагая тогда недоказанную гипотезу, есть сколь угодно длинные арифметические прогрессии, состоящие из простых чисел, они доказывают, что каждое рекурсивно перечислимое множество экспоненциально диофантово. Они также доказывают в качестве следствия, что из J.R. следует, что каждое рекурсивно перечислимое множество является диофантовым, что, в свою очередь, означает неразрешимость десятой проблемы Гильберта.
1960	Робинсон упрощает доказательство условный результат для экспоненциальных диофантовых множеств и делает его независимым от гипотезы о простых числах и, следовательно, формальной теоремы. Это делает гипотезу Дж.Р. достаточным условием неразрешимости десятой проблемы Гильберта. Однако многие сомневаются, что J.R.[5]
1961–1969	В течение этого периода Дэвис и Патнэм находят различные предложения, которые подразумевают Дж. Р., и Робинсон, ранее показавший, что Дж. Р. подразумевает, что множество простых чисел является диофантовым множеством, доказывает, что это если и только если условие. Юрий Матиясевич публикует некоторые сокращения десятой проблемы Гильберта.
1970	Рисунок из недавно опубликованной работы Николай Воробьев на числах Фибоначчи,[6] Матиясевич доказывает, что множество ${\displaystyle P=\{(a,b)|a>0,b=F_{2a}\},}$ куда ${\displaystyle F_{n}}$ затем^th Число Фибоначчи, является диофантовым и демонстрирует экспоненциальный рост.[7] Это подтверждает гипотезу Дж.Р., которая к тому времени оставалась открытым вопросом в течение 20 лет. Объединение Дж. Р. с теоремой о том, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым, доказывает, что рекурсивно перечислимые множества диофантовы. Это делает десятую проблему Гильберта неразрешимой.

Приложения

Теорема Матиясевича / MRDP связывает два понятия - одно из теории вычислимости, другое из теории чисел - и имеет некоторые удивительные последствия. Возможно, самым удивительным является существование универсальный Диофантово уравнение:

Существует многочлен ${\displaystyle p(a,n,x_{1},\ldots ,x_{k})}$ такое, что для любого диофантова множества ${\displaystyle S}$ есть номер ${\displaystyle n_{0}}$ такой, что

${\displaystyle S=\{\,a\mid \exists x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.}$

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

Хилари Патнэм отметила, что для любого диофантова множества ${\displaystyle S}$ натуральных чисел, существует многочлен

${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})}$

такой, что ${\displaystyle S}$ состоит в точности из положительных чисел среди значений, принимаемых ${\displaystyle q}$ как переменные

${\displaystyle x_{0},x_{1},\ldots ,x_{n}}$

диапазон по всем натуральным числам. Это можно увидеть следующим образом: Если

${\displaystyle p(a,y_{1},\ldots ,y_{n})=0}$

дает диофантово определение ${\displaystyle S}$, то достаточно положить

${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].}$

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

Другие приложения касаются того, что логики называют ${\displaystyle \Pi _{1}^{0}}$ предложения, иногда также называемые предложениями Тип Гольдбаха.^[8] Это как Гипотеза Гольдбаха, утверждая, что все натуральные числа обладают определенным свойством, которое алгоритмически проверяется для каждого конкретного числа.^[9] Теорема Матиясевича / MRDP подразумевает, что каждое такое предложение эквивалентно утверждению, которое утверждает, что какое-то конкретное диофантово уравнение не имеет решений в натуральных числах.^[10] Ряд важных и знаменитых проблем имеют такую ​​форму: в частности, Последняя теорема Ферма, то Гипотеза Римана, а Теорема четырех цветов. Кроме того, утверждение, что в частности формальные системы такие как арифметика Пеано или ZFC согласованы можно выразить как ${\displaystyle \Pi _{1}^{0}}$ фразы. Идея в том, чтобы следовать Курт Гёдель при кодировании доказательств натуральными числами таким образом, чтобы свойство быть числом, представляющим доказательство, можно было алгоритмически проверить.

${\displaystyle \Pi _{1}^{0}}$ предложения обладают особым свойством: если они ложны, этот факт можно доказать в любой из обычных формальных систем. Это потому, что ложность сводится к существованию контрпримера, который можно проверить простой арифметикой. Так что если ${\displaystyle \Pi _{1}^{0}}$ предложение таково, что ни оно, ни его отрицание не могут быть доказаны ни в одной из этих систем, это предложение должно быть истинным.^{[нужна цитата ]}

Особенно яркая форма Теорема Гёделя о неполноте также является следствием теоремы Матиясевича / MRDP:

Позволять

${\displaystyle p(a,x_{1},\ldots ,x_{k})=0}$

дать диофантово определение невычислимого множества. Позволять ${\displaystyle A}$ быть алгоритмом, который выводит последовательность натуральных чисел ${\displaystyle n}$ такое, что соответствующее уравнение

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0}$

не имеет решений в натуральных числах. Тогда есть номер ${\displaystyle n_{0}}$ который не выводится ${\displaystyle A}$ в то время как на самом деле уравнение

${\displaystyle p(n_{0},x_{1},\ldots ,x_{k})=0}$

не имеет решений в натуральных числах.

Чтобы убедиться в истинности теоремы, достаточно заметить, что если бы такого числа не было ${\displaystyle n_{0}}$, можно было бы алгоритмически проверить принадлежность числа ${\displaystyle n}$ в этом невычислимом множестве, одновременно выполняя алгоритм ${\displaystyle A}$ чтобы увидеть, есть ли ${\displaystyle n}$ выводится, а также проверяет все возможные ${\displaystyle k}$-наборы натуральных чисел, ищущие решение уравнения

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0.}$

Мы можем связать алгоритм ${\displaystyle A}$ с любой из обычных формальных систем, таких как Арифметика Пеано или же ZFC позволяя ему систематически генерировать следствия аксиом, а затем выводить число ${\displaystyle n}$ всякий раз, когда предложение формы

${\displaystyle \neg \exists x_{1},\ldots ,x_{k}[p(n,x_{1},\ldots ,x_{k})=0]}$

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

Дальнейшие результаты

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

Уже в 1920-е гг. Торальф Сколем показал, что любое диофантово уравнение эквивалентно одному из степеней 4 или меньше. Его уловка заключалась в том, чтобы ввести новые неизвестные, задав уравнения, равные квадрату неизвестного или произведению двух неизвестных. Повторение этого процесса приводит к системе уравнений второй степени; тогда уравнение степени 4 получается суммированием квадратов. Итак, любое диофантово множество тривиально имеет степень 4 или меньше. Неизвестно, насколько возможен такой результат.

Юлия Робинсон и Юрий Матиясевич показали, что каждое диофантово множество имеет размерность не больше 13. Позже Матиясевич отточил свои методы, чтобы показать, что достаточно 9 неизвестных. Хотя вполне может быть, что это не самый лучший результат, дальнейшего прогресса нет.^[11] Так, в частности, не существует алгоритма проверки диофантовых уравнений с 9 или менее неизвестными на разрешимость в натуральных числах. Для случая рациональных целочисленных решений (как первоначально сформулировал Гильберт) трюк с четырьмя квадратами показывает, что не существует алгоритма для уравнений с не более чем 36 неизвестными. Но Чжи Вэй Сунь показал, что задача для целых чисел неразрешима даже для уравнений с не более чем 11 неизвестными.

Мартин Дэвис изучал алгоритмические вопросы, связанные с числом решений диофантова уравнения. Десятая проблема Гильберта спрашивает, равно ли это число 0. Пусть${\displaystyle A=\{0,1,2,3,\ldots ,\aleph _{0}\}}$ и разреши ${\displaystyle C}$ быть собственным непустым подмножеством ${\displaystyle A}$. Дэвис доказал, что не существует алгоритма проверки данного диофантова уравнения, чтобы определить, является ли количество его решений членом множества. ${\displaystyle C}$. Таким образом, не существует алгоритма определения того, является ли число решений диофантова уравнения конечным, нечетным, полным квадратом, простым числом и т. Д.

Доказательство теоремы MRDP было формализовано в Coq.^[12]

Расширения десятой проблемы Гильберта

Александра Шлапентох (в центре) в 2003 году

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

По десятой проблеме Гильберта для колец целых чисел полей алгебраических чисел было проведено много работы. Основываясь на более ранней работе Ян Денеф и Леонардом Липшицем, и используя теорию полей классов, Гарольд Н. Шапиро и Александра Шлапентох смогли доказать:

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

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

Проблема для кольца целых чисел полей алгебраических чисел, отличных от тех, которые охвачены приведенными выше результатами, остается открытой. Точно так же, несмотря на большой интерес, проблема для уравнений над рациональными числами остается открытой. Барри Мазур предположил, что для любого разнообразие над рациональными числами топологическое замыкание вещественных чисел множества решений имеет лишь конечное число компонент.^[13] Эта гипотеза подразумевает, что целые числа не являются диофантовыми над рациональными числами, и поэтому, если эта гипотеза верна, отрицательный ответ на десятую проблему Гильберта потребует другого подхода, чем тот, который используется для других колец.

Примечания

1. С. Барри Купер, Теория вычислимости, п. 98
2. Гильберт 1902, п. 458. Ошибка sfn: нет цели: CITEREFHilbert1902 (помощь)
3. Гильберт 1902, п. 444. ошибка sfn: цель отсутствует: CITEREFHilbert1902 (помощь)
4. Юрий Матиясевич (1993). 10-я проблема Гильберта. MIT Press.
5. Обзор совместной публикации Дэвиса, Патнэма и Робинсона в Математические обзоры (МИСТЕР0133227 ) предположил, что J.R. был ложным.
6. Матиясевич, Юрий (1992). «Мое сотрудничество с Джулией Робинсон». Математический интеллект. 14 (4): 38–45. Дои:10.1007 / bf03024472.
7. Мешки, Джеральд Э. (2003). Математическая логика в ХХ веке. World Scientific. С. 269–273.
8. ${\displaystyle \Pi _{1}^{0}}$ предложения находятся на одном из низших уровней так называемого арифметическая иерархия.
9. Таким образом, сама гипотеза Гольдбаха может быть выражена следующим образом: для каждого натурального числа ${\displaystyle n}$ номер ${\displaystyle 2n+4}$ это сумма двух простых чисел. Конечно, существует простой алгоритм для проверки данного числа на предмет суммы двух простых чисел.
10. Фактически эквивалентность доказуема в Арифметика Пеано.
11. На данный момент даже 3 не могут быть исключены как абсолютная верхняя граница.
12. Доминик Ларчи-Вендлинг и Янник Форстер (2019). Десятая проблема Гильберта в Coq (PDF) (Технический отчет). Саарский университет.
13. http://www-math.mit.edu/~poonen/papers/subrings.pdf

Рекомендации

• Дэвид Гильберт (1901). "Математическая проблема". Archiv der Mathematik und Physik, 3-я сер. (на немецком). 1: 44–63, 213–247.
• Дэвид Гильберт (июль 1902 г.). «Математические задачи». Бык. Амер. Математика. Soc. 8 (10): 437–479.
• Юрий Васильевич Матиясевич, Десятая проблема Гильберта, MIT Press, Кембридж, Массачусетс, 1993.
• Дэвис, Мартин; Матиясевич Юрий; Робинсон, Джулия (1976). «Десятая проблема Гильберта: диофантовы уравнения: положительные аспекты отрицательного решения». В Феликс Э. Браудер (ред.). Математические разработки, возникающие из проблем Гильберта. Труды симпозиумов по чистой математике. XXVIII.2. Американское математическое общество. С. 323–378. ISBN  0-8218-1428-1. Zbl  0346.02026. Перепечатано в Собрание сочинений Джулии Робинсон, Соломон Феферман, редактор, стр. 269–378, Американское математическое общество, 1996 г.
• Мартин Дэвис, «Десятая проблема Гильберта неразрешима», Американский математический ежемесячный журнал, том 80 (1973), стр. 233–269; перепечатано как приложение у Мартина Дэвиса, Вычислимость и неразрешимость, Dover репринт 1982.
• Дэвис, Мартин; Херш, Рувим (1973). «10-я проблема Гильберта». Scientific American. 229: 84–91. Дои:10.1038 / scientificamerican1173-84.
• Ян Денеф, Леонард Липшиц, Танас Фейдас, Ян ван Гил, редакторы, "Десятая проблема Гильберта: семинар в Гентском университете, Бельгия, 2–5 ноября 1999 г." Современная математика т. 270 (2000), Американское математическое общество.
• М. Рам Мурти и Брэндон Фодден: «Десятая проблема Гильберта: введение в логику, теорию чисел и вычислимость», Americal Mathematical Society, ISBN  978-1-4704-4399-3 (Июнь, 2019).

дальнейшее чтение

• Шлапентох, Александра (2007). Десятая проблема Гильберта. Диофантовы классы и расширения глобальных полей. Новые математические монографии. 7. Кембридж: Издательство Кембриджского университета. ISBN  0-521-83360-4. Zbl  1196.11166.

внешняя ссылка

• Десятая проблема Гильберта: история математических открытий
• Страница десятой проблемы Гильберта!
• Чжи Вэй Сунь: О десятой проблеме Гильберта и смежных темах
• Трейлер к "Десятой проблеме Джулии Робинсон и Гильберта" на YouTube