Диофантовый набор - Diophantine set

В математике , А диофантово уравнение является уравнением вида Р ( х ₁ , ..., х _J , у ₁ , ..., у _к ) = 0 (обычно сокращенно P ( х , у ) = 0) , где Р ( x , y ) - многочлен с целыми коэффициентами , где x ₁ , ..., x _j обозначают параметры, а y ₁ , ..., y _k обозначают неизвестные.

Диофанты множество является подмножество S из N ^J так , что в течение некоторого уравнения диофантов Р ( х , у ) = 0,

${\ displaystyle {\ bar {n}} \ in S \ iff (\ exists {\ bar {m}} \ in \ mathbb {N} ^ {k}) (P ({\ bar {n}}, {\ bar {m}}) = 0).}$

То есть значение параметра находится в диофантовом множестве S тогда и только тогда, когда соответствующее диофантово уравнение удовлетворяемо при этом значении параметра. Использование натуральных чисел как в S, так и в квантификации существования просто отражает обычные приложения в вычислимости и теории моделей. С таким же успехом мы можем говорить о диофантовых наборах целых чисел и свободно заменять количественную оценку натуральных чисел на количественную оценку целых чисел. Также достаточно предположить, что P является полиномом, и умножить P на соответствующие знаменатели, чтобы получить целые коэффициенты. Однако, может ли количественная оценка по рациональным числам также быть заменой количественной оценки по целым числам, является общеизвестно трудной открытой проблемой. ${\ displaystyle \ mathbb {Q}}$

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

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

Примеры

Уравнение Пелла

${\ displaystyle x ^ {2} -d (y + 1) ^ {2} = 1}$

является примером диофантова уравнения с параметром. Уравнение имеет решение с неизвестными точно тогда, когда параметр равен 0 или не является точным квадратом . А именно, это уравнение дает диофантово определение множества ${\ displaystyle x, y}$${\ displaystyle d}$

{0,2,3,5,6,7,8,10, ...}

состоящий из 0 и натуральных чисел, не являющихся полными квадратами.

Другие примеры диофантовых определений следующие:

• Уравнение имеет решения только в том случае, если a не является степенью двойки.${\ displaystyle a = (2x + 3) y}$${\ Displaystyle \ mathbb {N}}$
• Уравнение имеет решения только тогда, когда a больше 1 и не является простым числом .${\ Displaystyle а = (х + 2) (у + 2)}$${\ Displaystyle \ mathbb {N}}$
• Уравнение определяет набор пар таких, что${\ displaystyle a + x = b}$${\ Displaystyle (а \ ,, \, Ь)}$${\ displaystyle a \ leq b.}$

Теорема Матиясевича

Теорема Матиясевича, также называемая теоремой Матиясевича - Робинсона - Дэвиса - Патнэма или MRDP, гласит:

Каждое вычислимо перечислимое множество диофантово и наоборот.

Набор целых чисел S вычислимо перечислим, если существует такой алгоритм, что: для каждого целочисленного входа n , если n является членом S , алгоритм в конечном итоге останавливается; в противном случае он работает вечно. Это равносильно тому, существует алгоритм , который работает навсегда и список членов S . Множество S является диофантовым в точности, если существует некоторый многочлен с целыми коэффициентами f ( n , x ₁ , ..., x _k ) такой, что целое число n находится в S тогда и только тогда, когда существуют некоторые целые числа x ₁ , ... , x _k такие, что f ( n , x ₁ , ..., x _k ) = 0.

И наоборот, каждое диофантово множество вычислимо перечислимо : рассмотрим диофантово уравнение f ( n , x ₁ , ..., x _k ) = 0. Теперь мы создаем алгоритм, который просто пробует все возможные значения для n , x ₁ , ... , x _k (скажем, в некотором простом порядке, совместимом с порядком возрастания суммы их абсолютных значений), и печатает n каждый раз, когда f ( n , x ₁ , ..., x _k ) = 0. Этот алгоритм будет очевидно, работать вечно и будет перечислять именно те n, для которых f ( n , x ₁ , ..., x _k ) = 0 имеет решение в x ₁ , ..., x _k .

Техника доказательства

Юрий Матиясевич использовал метод, включающий числа Фибоначчи , которые растут экспоненциально , чтобы показать, что решения диофантовых уравнений могут расти экспоненциально . Более ранняя работа Джулии Робинсон , Мартина Дэвиса и Хилари Патнэм - следовательно, MRDP - показала, что этого достаточно, чтобы показать, что каждое вычислимо перечислимое множество диофантово.

Приложение к десятой проблеме Гильберта

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

Доработки

Более поздняя работа показала, что вопрос о разрешимости диофантова уравнения неразрешим, даже если уравнение имеет только 9 натуральных числовых переменных (Матиясевич, 1977) или 11 целочисленных переменных ( Zhi Wei Sun , 1992).

Дальнейшие приложения

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

Из результата Матиясевича можно также вывести следующую более сильную форму первой теоремы Гёделя о неполноте :

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

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

Примечания

использованная литература

• Матиясевич, Юрий В. (1970). Диофантовость перечислимых множеств[Перечислимые множества диофантовы]. Доклады Академии Наук СССР . 191 : 279–282. Руководство по ремонту  0258744 .Английский перевод по советской математике 11 (2), стр. 354–357.
• Дэвис, Мартин (1973). «Десятая проблема Гильберта неразрешима». Американский математический ежемесячник . 80 : 233–269. DOI : 10.2307 / 2318447 . ISSN  0002-9890 . Zbl  0277.02008 .
• Матиясевич, Юрий В. (1993). 10-я проблема Гильберта . Серия MIT Press по основам вычислений. Предисловие Мартина Дэвиса и Хилари Патнэм. Кембридж, Массачусетс: MIT Press. ISBN 0-262-13295-8. Zbl  0790.03008 .
• Шлапентох, Александра (2007). Десятая проблема Гильберта. Диофантовы классы и расширения глобальных полей . Новые математические монографии. 7 . Кембридж: Издательство Кембриджского университета . ISBN 0-521-83360-4. Zbl  1196.11166 .
• Сунь Чжи-Вэй (1992). «Редукция неизвестных в диофантовых представлениях» (PDF) . Наука Китайская математика . 35 (3): 257–269. Zbl  0773.11077 .

внешние ссылки

• Статья о теореме Матиясевича в Scholarpedia .
• Статья о Диофантовом множестве на PlanetMath .