Zbiór diofantyczny
Zbiór diofantyczny – taki zbiór uporządkowanych n-elementowych krotek liczb naturalnych który posiada diofantyczną reprezentacje pewnego diofantycznego równania parametrycznego. Diofantyczną reprezentacją zbioru nazywamy równoważność postaci:
gdzie jest diofantycznym równaniem parametrycznym, to parametry, natomiast to niewiadome. Liczbę nazywamy wymiarem zbioru Każdy zbiór diofantyczny posiada nieskończenie wiele diofantycznych reprezentacji.
Przykład
Rozważmy równanie Pella:
Jest to równanie parametryczne z parametrem i niewiadomymi i Wiadomo, że powyższe równanie ma rozwiązanie w dziedzinie liczb całkowitych wtw. gdy parametr jest równy lub nie jest kwadratem liczby całkowitej, dlatego zbiór diofantyczny związany z tym równaniem to:
Własności
Łatwo zauważyć, że suma dwóch zbiorów diofantycznych i tego samego wymiaru również jest zbiorem diofantycznym. Jeżeli równania parametryczne i to odpowiednio diofantyczne reprezentacje zbiorów i
to poniższe równanie jest reprezentacją diofantyczną sumy zbiorów i
Podobnie przecięcie dwóch zbiorów diofantycznych i również jest zbiorem diofantycznym, jako że reprezentacją diofantyczną tego przecięcia jest:
Twierdzenia Matijasiewicza
Twierdzenie Matijasiewicza mówi, że każdy rekurencyjnie przeliczalny zbiór jest zbiorem diofantycznym. Zbiór jest rekurencyjnie przeliczalny wtw. gdy istnieje taka maszyna Turinga że jeżeli maszyna działając na liczbę kończy pracę to W sposób równoważny można powiedzieć, że zbiór jest rekurencyjnie przeliczalny jeżeli istnieje algorytm wypisujący listę wszystkich elementów tego zbioru.
Implikacja odwrotna również jest spełniona. Jeżeli jest diofantyczną reprezentacją pewnego zbioru diofantycznego to zbiór jest rekurencyjnie przeliczalny. Algorytm wypisujący wszystkie elementy zbioru możemy uzyskać sprawdzając równość dla wszystkich możliwych uporządkowanych, n+1-elementowych krotek (których jest przeliczalnie wiele z uwagi na przeliczalność iloczynów kartezjańskich zbiorów przeliczalnych).