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

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

Диофантово множество это подмножество S — $\mathbb {N} ^{j}$, набор всех j - наборов натуральных чисел, так что для некоторого диофантова уравнения P ( x , y ) = 0,

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

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

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

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

Примеры

В следующих примерах натуральные числа относятся к набору положительных целых чисел.

Уравнение

$x=(y_{1}+1)(y_{2}+1)$

является примером диофантова уравнения с параметром x и неизвестными y ₁ и y ₂ . Уравнение имеет решение относительно y ₁ и y ₂ именно тогда, когда x можно выразить как произведение двух целых чисел, больших 1, другими словами, x является составным числом . А именно, это уравнение дает диофантово определение множества

{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

состоящее из составных чисел.

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

• Уравнение $x=y_{1}^{2}+y_{2}^{2}$ с параметром x и неизвестными y ₁ , y ₂ имеет решения только в $\mathbb {N}$ когда x представляет собой сумму двух полных квадратов . Диофантова система уравнения равна {2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}.
• Уравнение $y_{1}^{2}-xy_{2}^{2}=1$ с параметром x и неизвестными y ₁ , y ₂ . Это уравнение Пелля , то есть оно имеет решения только в $\mathbb {N}$ когда x не является точным квадратом. Диофантово множество — это {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}.
• Уравнение $x_{1}+y=x_{2}$ представляет собой диофантово уравнение с двумя параметрами x ₁ , x ₂ и неизвестным y , которое определяет набор пар ( x ₁ , x ₂ ) таких, что x ₁ < x ₂ .

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

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

Всякое вычислимо перечислимое множество диофантово, и наоборот.

Множество S целых чисел является вычислимо перечислимым, если существует такой алгоритм, что: Для каждого целочисленного входного числа n , если n является членом S , то алгоритм в конечном итоге останавливается; в противном случае он работает вечно. что существует алгоритм, который работает вечно и перечисляет члены S. Это эквивалентно утверждению , Множество S является диофантовым в точности, если существует некоторый многочлен с целыми коэффициентами f ( n , x ₁ , ..., x _k )такое, что целое число n принадлежит S тогда и только тогда, когда существуют некоторые целые числа х ₁ , ..., х _к такой, что 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 имеет решениев х ₁ , ..., х _к .

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

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

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

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

Уточнения

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

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

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

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

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

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

Ссылки

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

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

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