реферат найти 10-я проблема Гильберта

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

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

а1Икс1 а2Икс2знак равноа3{ displaystyle a_ {1} x_ {1} a_ {2} x_ {2} = a_ {3}},

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

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

п1знак равно0,…,пkзнак равно0{ Displaystyle p_ {1} = 0, ldots, p_ {k} = 0}

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

п12 ⋯ пk2знак равно0.{ displaystyle p_ {1} ^ {2} cdots p_ {k} ^ {2} = 0.}

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

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

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

История

Год	События
1944 г.	Эмиль Леон Пост заявляет, что десятая проблема Гильберта «требует доказательства неразрешимости».
1949 г.	Мартин Дэвис использует метод Курта Гёделя для применения китайской теоремы об остатках в качестве уловки кодирования, чтобы получить свою нормальную форму для рекурсивно перечислимых множеств: {а∣∃у∀k⩽у∃Икс1,…,Иксп:п(а,k,у,Икс1,…,Иксп)знак равно0}{ 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, набор троек для которых является диофантовым. Не добившись успеха, она выдвигает следующую гипотезу (позже названную JR):(а,б,c){ Displaystyle (а, б, в)}азнак равнобc{ displaystyle a = b ^ {c}} Существует такое диофантово множество пар , что и для каждого положительного существует такое, чтоD{ displaystyle D}(а,б){ Displaystyle (а, б)}(а,б)∈D⇒б<аа{ displaystyle (a, b) in D Rightarrow b <a ^ {a}}k,{ displaystyle k,}(а,б)∈D{ displaystyle (a, b) in D}б>аk.{ displaystyle b> a ^ {k}.} Используя свойства уравнения Пелла, она доказывает, что из JR следует, что EXP диофантово, а также биномиальные коэффициенты, факториал и простые числа.
1959 г.	Работая вместе, Дэвис и Патнэм изучают экспоненциальные диофантовы множества : множества, определяемые диофантовыми уравнениями, в которых некоторые из показателей могут быть неизвестны. Используя нормальную форму Дэвиса вместе с методами Робинсона и предполагая тогда недоказанную гипотезу о том, что существуют сколь угодно длинные арифметические прогрессии, состоящие из простых чисел , они доказывают, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым. Они также доказывают в качестве следствия, что из JR следует, что каждое рекурсивно перечислимое множество является диофантовым, что, в свою очередь, означает неразрешимость десятой проблемы Гильберта.
1960 г.	Робинсон упрощает доказательство условного результата для экспоненциальных диофантовых множеств и делает его независимым от гипотезы о простых числах и, следовательно, формальной теоремы. Это делает гипотезу JR достаточным условием неразрешимости десятой проблемы Гильберта. Однако многие сомневаются в истинности JR.
1961–1969	В течение этого периода Дэвис и Патнэм находят различные предложения, которые подразумевают JR, и Робинсон, ранее показавший, что JR подразумевает, что множество простых чисел является диофантовым множеством, доказывает, что это условие тогда и только тогда, когда . Юрий Матиясевич публикует некоторые редукции десятой проблемы Гильберта.
1970 г.	Основываясь на недавно опубликованной работе Николая Воробьева о числах Фибоначчи, Матиясевич доказывает, что множество, где является n- м числом Фибоначчи , является диофантовым и демонстрирует экспоненциальный рост. Это доказывает гипотезу JR, которая к тому времени оставалась открытым вопросом в течение 20 лет. Объединение JR с теоремой о том, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым, доказывает, что рекурсивно перечислимые множества диофантовы. Это делает неразрешимую десятую проблему Гильберта. пзнак равно{(а,б)|а>0,бзнак равноF2а},{ Displaystyle P = {(a, b) | a> 0, b = F_ {2a} },}Fп{ displaystyle F_ {n}}

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

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

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

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

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

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

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

Приложения

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

Существует такой многочлен , что для любого диофантова множества существует такое число , чтоп(а,п,Икс1,…,Иксk){ Displaystyle p (а, п, x_ {1}, ldots, x_ {k})}S{ displaystyle S}п0{ displaystyle n_ {0}}

Sзнак равно{а∣∃Икс1,…,Иксk[п(а,п0,Икс1,…,Иксk)знак равно0]}.{ Displaystyle S = {, а середина существует x_ {1}, ldots, x_ {k} [p (a, n_ {0}, x_ {1}, ldots, x_ {k}) = 0] , }.}

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

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

q(Икс0,Икс1,…,Иксп){ displaystyle q (x_ {0}, x_ {1}, ldots, x_ {n})}

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

Икс0,Икс1,…,Иксп{ displaystyle x_ {0}, x_ {1}, ldots, x_ {n}}

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

п(а,у1,…,уп)знак равно0{ Displaystyle p (а, y_ {1}, ldots, y_ {n}) = 0}

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

q(Икс0,Икс1,…,Иксп)знак равноИкс0[1-п(Икс0,Икс1,…,Иксп)2].{ displaystyle q (x_ {0}, x_ {1}, ldots, x_ {n}) = x_ {0} [1-p (x_ {0}, x_ {1}, ldots, x_ {n}) ) ^ {2}].}

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

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

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

Позволять

п(а,Икс1,…,Иксk)знак равно0{ Displaystyle p (а, x_ {1}, ldots, x_ {k}) = 0}

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

п(п,Икс1,…,Иксk)знак равно0{ Displaystyle p (п, x_ {1}, ldots, x_ {k}) = 0}

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

п(п0,Икс1,…,Иксk)знак равно0{ displaystyle p (n_ {0}, x_ {1}, ldots, x_ {k}) = 0}

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

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

п(п,Икс1,…,Иксk)знак равно0.{ displaystyle p (n, x_ {1}, ldots, x_ {k}) = 0.}

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

¬∃Икс1,…,Иксk[п(п,Икс1,…,Иксk)знак равно0]{ Displaystyle neg существует x_ {1}, ldots, x_ {k} [p (n, x_ {1}, ldots, x_ {k}) = 0]}

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

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

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

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

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

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

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

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

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

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

• Гильберт, Дэвид (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.
• Мартин Дэвис , «Десятая проблема Гильберта неразрешима», American Mathematical Monthly , том 80 (1973), стр. 233–269; перепечатано в качестве приложения к книге Мартина Дэвиса, « Вычислимость и неразрешимость» , Dover reprint 1982.
• Дэвис, Мартин ; Херш, Рувим (1973). «10-я проблема Гильберта». Scientific American . 229 : 84–91. DOI : 10.1038 / Scientificamerican1173-84 .
• Ян Денеф , Леонард Липшиц, Танасес Фейдас, Ян ван Гил, редакторы, «Десятая проблема Гильберта: семинар в Гентском университете, Бельгия, 2–5 ноября 1999 г.». Современная математика . 270 (2000), Американское математическое общество.
• М. Рам Мёрти и Брэндон Фодден: «Десятая проблема Гильберта: введение в логику, теорию чисел и вычислимость», Американское математическое общество, ISBN  978-1-4704-4399-3 (июнь 2021 г.).

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

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

Именно развитие теории вычислимости (также известной как теория рекурсии) обеспечило точное объяснение интуитивного понятия алгоритмической вычислимости, сделав таким образом понятие рекурсивной перечислимости совершенно строгим. Очевидно, что диофантовы множества рекурсивно перечислимы.

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

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

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

п(а,Икс1,…,Иксп){ Displaystyle p (а, x_ {1}, ldots, x_ {n})}

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

п(а,Икс1,…,Иксп)знак равно0{ Displaystyle p (а, x_ {1}, ldots, x_ {n}) = 0}

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

Реферат найти 10-я проблема гильберта