Zestaw diofantyny - Diophantine set

W matematyce , ą równanie diofantycznego jest równanie postaci P ( x ₁ , ..., x _j , Y ₁ , ..., Y _k ) = 0 (zwykle skrótem P ( x , y ) = 0), w którym P ( x , y ) jest wielomianem o współczynnikach całkowitych , gdzie x ₁ , ..., x _j oznaczają parametry, a y ₁ , ..., y _k oznaczają niewiadome.

Zbiór diofantyczny jest podzbiorem S od N ^j tak, że dla pewnego równania diofantycznego P ( x , y ) = 0,

${\ Displaystyle {\ bar {n}} \ w S \ iff (\ istnieje {\ bar {m}} \ w \ mathbb {N} ^ {k}) (P ({\ bar {n}}), {\ słupek {m}})=0).}$

Oznacza to, że wartość parametru znajduje się w zestawie diofantycznym S wtedy i tylko wtedy, gdy powiązane równanie diofantyczne jest możliwe do spełnienia pod tą wartością parametru. Użycie liczb naturalnych zarówno w S, jak iw kwantyfikacji egzystencjalnej odzwierciedla jedynie zwykłe zastosowania w obliczalności i teorii modeli. Równie dobrze możemy mówić o diofantycznych zbiorach liczb całkowitych i swobodnie zastępować kwantyfikację po liczbach naturalnych kwantyfikacją po liczbach całkowitych. Wystarczy również założyć, że P jest wielomianem i pomnożyć P przez odpowiednie mianowniki, aby uzyskać współczynniki całkowite. Jednak to, czy kwantyfikacja po liczbach wymiernych może być również zastąpiona kwantyfikacją po liczbach całkowitych, jest bardzo trudnym, otwartym problemem. ${\ Displaystyle \ mathbb {Q}}$

Twierdzenie MRDP stwierdza, że ​​zbiór liczb całkowitych jest diofantyczny wtedy i tylko wtedy, gdy jest przeliczalny . Zbiór liczb całkowitych S jest przeliczalny wtedy i tylko wtedy, gdy istnieje algorytm, który po podaniu liczby całkowitej zatrzymuje się, jeśli ta liczba jest członkiem S i działa w nieskończoność w przeciwnym razie. Oznacza to, że pojęcie ogólnego zbioru diofantycznego, najwyraźniej należące do teorii liczb , może być rozumiane raczej w kategoriach logicznych lub rekurencji. Nie jest to jednak oczywiste i stanowi kulminację kilkudziesięciu lat pracy.

Dokończenie przez Matiyasevicha twierdzenia MRDP rozwiązało dziesiąty problem Hilberta . Dziesiątym problemem Hilberta było znalezienie ogólnego algorytmu, który może rozstrzygnąć, czy dane równanie diofantyczne ma rozwiązanie wśród liczb całkowitych. Podczas gdy dziesiąty problem Hilberta nie jest formalnym twierdzeniem matematycznym jako takim, niemal powszechna akceptacja (filozoficznej) identyfikacji algorytmu decyzyjnego z całkowicie obliczalnym predykatem pozwala nam wykorzystać twierdzenie MRDP do stwierdzenia, że ​​dziesiąty problem jest nierozwiązywalny.

Przykłady

Równanie Pella

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

jest przykładem równania diofantycznego z parametrem. Równanie ma rozwiązanie w niewiadomych dokładnie wtedy, gdy parametr wynosi 0 lub nie jest idealnym kwadratem . Mianowicie to równanie zapewnia diofantyczną definicję zbioru ${\displaystyle x,y}$${\displaystyle d}$

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

składający się z 0 i liczb naturalnych, które nie są kwadratami idealnymi.

Inne przykłady definicji diofantycznych są następujące:

• Równanie ma rozwiązania tylko wtedy, gdy a nie jest potęgą 2.${\displaystyle a=(2x+3)y}$${\ Displaystyle \ mathbb {N}}$
• Równanie ma rozwiązania tylko wtedy, gdy a jest większe niż 1 i nie jest liczbą pierwszą .${\ Displaystyle a = (x + 2) (y + 2)}$${\ Displaystyle \ mathbb {N}}$
• Równanie definiuje zbiór par takich, że${\displaystyle a+x=b}$${\displaystyle (a\,,\,b)}$${\displaystyle a\leq b.}$

Twierdzenie Matiyasevicha

Twierdzenie Matiyasevicha, zwane też twierdzeniem Matiyasevich – Robinson – Davis – Putnam lub MRDP, mówi:

Każdy przeliczalny zbiór jest diofantyną i odwrotnie.

Zbiór S liczb całkowitych jest przeliczalny, jeśli istnieje algorytm taki, że: Dla każdego wejścia liczb całkowitych n , jeśli n należy do S , to algorytm ostatecznie zatrzymuje się; w przeciwnym razie działa w nieskończoność. Jest to równoznaczne z twierdzeniem, że istnieje algorytm, który działa w nieskończoność i wyświetla listę członków S . Zbiór S jest diofantyną dokładnie wtedy, gdy istnieje jakiś wielomian o współczynnikach całkowitych f ( n , x ₁ , ..., x _k ) taki, że liczba całkowita n jest w S wtedy i tylko wtedy, gdy istnieją liczby całkowite x ₁ , ... , x _k takie, że f ( n , x ₁ , ..., x _k ) = 0.

I odwrotnie, każdy zbiór diofantyczny jest przeliczalny : rozważmy równanie diofantyczne f ( n , x ₁ , ..., x _k ) = 0. Teraz tworzymy algorytm, który po prostu próbuje wszystkich możliwych wartości dla n , x ₁ , ... , x _k (powiedzmy, w pewnym prostym porządku zgodnym z porządkiem rosnącym sumy ich wartości bezwzględnych) i wypisuje n za każdym razem, gdy f ( n , x ₁ , ..., x _k ) = 0. Ten algorytm będzie oczywiście działa w nieskończoność i wypisze dokładnie n, dla których f ( n , x ₁ , ..., x _k ) = 0 ma rozwiązanie w x ₁ , ..., x _k .

Technika dowodowa

Yuri Matiyasevich wykorzystał metodę wykorzystującą liczby Fibonacciego , które rosną wykładniczo , aby pokazać, że rozwiązania równań diofantycznych mogą rosnąć wykładniczo . Wcześniejsze prace Julii Robinson , Martina Davisa i Hilary Putnam – stąd MRDP – pokazały, że to wystarczy, aby wykazać, że każdy przeliczalny zbiór jest diofantyną.

Zastosowanie do dziesiątego problemu Hilberta

Dziesiąty problem Hilberta wymaga podania ogólnego algorytmu rozstrzygającego o rozwiązywalności równań diofantycznych. Połączenie wyniku Matiyasevicha z faktem, że większość rekurencyjnie przeliczalnych języków nie jest rozstrzygalna, implikuje, że rozwiązanie dziesiątego problemu Hilberta jest niemożliwe.

Udoskonalenia

Późniejsza praca wykazała, że ​​kwestia rozwiązania równania diofantycznego jest nierozstrzygalna, nawet jeśli równanie ma tylko 9 zmiennych liczb naturalnych (Matiyasevich, 1977) lub 11 zmiennych całkowitych ( Zhi Wei Sun , 1992).

Dalsze zastosowania

Twierdzenie Matiyasevicha zostało od tego czasu wykorzystane do udowodnienia, że ​​wiele problemów z rachunku różniczkowego i równań różniczkowych jest nierozwiązywalnych.

Z wyniku Matiyasevicha można również wyprowadzić następującą silniejszą formę pierwszego twierdzenia Gödla o niezupełności :

Odpowiadając dowolnej spójnej aksjomatyzacji teorii liczb, można jawnie skonstruować równanie diofantyczne, które nie ma rozwiązań, ale takie, że faktu tego nie można udowodnić w ramach danej aksjomatyzacji.

Zgodnie z twierdzeniami o niezupełności wystarczająco potężna, spójna teoria aksjomatyczna jest niekompletna, co oznacza, że ​​prawdziwości niektórych jej twierdzeń nie można ustalić w jej formalizmie. Powyższe stwierdzenie mówi, że ta niezupełność musi obejmować rozwiązanie równania diofantycznego, przy założeniu, że rozważana teoria jest teorią liczb.

Uwagi

Bibliografia

• Matiyasevich, Jurij V. (1970). Диофантовость перечислимых множеств[Zbiory policzalne to Diofantyny]. Doklady Akademii Nauk SSSR (po rosyjsku). 191 : 279–282. MR  0258744 .Tłumaczenie angielskie w matematyce sowieckiej 11 (2), s. 354–357.
• Davis, Martin (1973). „Dziesiąty problem Hilberta jest nie do rozwiązania”. Amerykański miesięcznik matematyczny . 80 : 233–269. doi : 10.2307/2318447 . ISSN  0002-9890 . Zbl  0277.02008 .
• Matiyasevich, Jurij V. (1993). 10. Problem Hilberta . MIT Press Series w podstawach informatyki. Przedmowa Martina Davisa i Hilary Putnam. Cambridge, MA: MIT Press. Numer ISBN 0-262-13295-8. Zbl  0790.03008 .
• Szlapentoch, Aleksandra (2007). Dziesiąty problem Hilberta. Klasy diofantyczne i rozszerzenia pól globalnych . Nowe Monografie Matematyczne. 7 . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-83360-4. Zbl  1196.11166 .
• Słońce Zhi-Wei (1992). „Redukcja niewiadomych w przedstawieniach diofantycznych” (PDF) . Nauka Chiny Matematyka . 35 (3): 257–269. Zbl  0773.11077 .

Zewnętrzne linki

• Artykuł o twierdzeniu Matiyasevicha na Scholarpedii .
• Artykuł dotyczący zestawu diofantycznego na PlanetMath .