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

Решение некоторого диофантова уравнения

В математике диофантово уравнение — это уравнение вида P ( x1 ,..., xj , _y1 ,..., yk ) = 0 (обычно сокращенно P ( x , y )=0), где P ( x , y ) — _{многочлен} с _целыми коэффициентами , где x1 _, ..., xj _— параметры, а y1 _, ..., _{yk —} неизвестные .

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

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

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

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

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

Примеры

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

Уравнение

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

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

Теорема Матиясевича, также называемая теоремой Матиясевича – Робинсона – Дэвиса – Патнэма или теоремой 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 целочисленных переменных ( Чжи Вэй Сунь , 1992).

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

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

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

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

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

Примечания

1. "Диофантово множество". Энциклопедия математики . Получено 11 марта 2022 г.
2. Pheidas, Thanases; Zahidi, Karim (2008). «Проблемы принятия решений в алгебре и аналоги десятой проблемы Гильберта». Теория моделей с приложениями к алгебре и анализу. Том 2. Серия заметок лекций Лондонского математического общества. Том 350. Cambridge University Press. С. 207–235. doi :10.1017/CBO9780511735219.007. ISBN 978-0-521-70908-8. МР  2436143.
3. Теорема была установлена ​​в 1970 году Матиясевичем и поэтому также известна как теорема Матиясевича. Однако доказательство, данное Матиясевичем, во многом опиралось на предыдущие работы по этой проблеме, и математическое сообщество перешло к названию результата эквивалентности теоремой MRDP или теоремой Матиясевича–Робинсона–Дэвиса–Патнэма, название, которое отдает должное всем математикам, внесшим значительный вклад в эту теорему.
4. Давид Гильберт сформулировал эту проблему в своем знаменитом списке из выступления 1900 года на Международном конгрессе математиков .
5. Точнее, дана -формула, представляющая набор гёделевских чисел предложений , которые рекурсивно аксиоматизируют непротиворечивую теорию, расширяющую арифметику Робинсона . ${\displaystyle \Sigma _{1}^{0}}$

Ссылки

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

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

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