Zbiór diofantyczny – Wikipedia, wolna encyklopedia

Zbiór diofantyczny – taki zbiór uporządkowanych n-elementowych krotek liczb naturalnych ${\displaystyle M,}$ który posiada diofantyczną reprezentacje pewnego diofantycznego równania parametrycznego. Diofantyczną reprezentacją zbioru ${\displaystyle M}$ nazywamy równoważność postaci:

${\displaystyle (a_{1},\dots ,a_{n})\in M\iff \exists x_{1}\dots x_{m}[D(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m})=0]\qquad (x_{1}\dots x_{m}\in \mathbb {N} ),}$

gdzie ${\displaystyle D(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m})=0}$ jest diofantycznym równaniem parametrycznym, ${\displaystyle a_{1},\dots ,a_{n}}$ to parametry, natomiast ${\displaystyle x_{1},\dots ,x_{m}}$ to niewiadome. Liczbę ${\displaystyle n}$ nazywamy wymiarem zbioru ${\displaystyle M.}$ Każdy zbiór diofantyczny posiada nieskończenie wiele diofantycznych reprezentacji.

Przykład[edytuj | edytuj kod]

Rozważmy równanie Pella:

${\displaystyle x^{2}-D(y+1)^{2}=1.}$

Jest to równanie parametryczne z parametrem ${\displaystyle D}$ i niewiadomymi ${\displaystyle x}$ i ${\displaystyle y.}$ Wiadomo, że powyższe równanie ma rozwiązanie w dziedzinie liczb całkowitych wtw. gdy parametr ${\displaystyle D}$ jest równy ${\displaystyle 0}$ lub nie jest kwadratem liczby całkowitej, dlatego zbiór diofantyczny związany z tym równaniem to: ${\displaystyle \{0,2,3,5,6,7,8,10,\dots \}.}$

Własności[edytuj | edytuj kod]

Łatwo zauważyć, że suma dwóch zbiorów diofantycznych ${\displaystyle M_{1}}$ i ${\displaystyle M_{2}}$ tego samego wymiaru ${\displaystyle n}$ również jest zbiorem diofantycznym. Jeżeli równania parametryczne ${\displaystyle D_{1}}$ i ${\displaystyle D_{2}}$ to odpowiednio diofantyczne reprezentacje zbiorów ${\displaystyle M_{1}}$ i ${\displaystyle M_{2}{:}}$

${\displaystyle D_{1}(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m_{1}})=0,}$

${\displaystyle D_{2}(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m_{2}})=0,}$

to poniższe równanie jest reprezentacją diofantyczną sumy zbiorów ${\displaystyle M_{1}}$ i ${\displaystyle M_{2}{:}}$

${\displaystyle D_{1}(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m_{1}})\cdot D_{2}(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m_{2}})=0.}$

Podobnie przecięcie dwóch zbiorów diofantycznych ${\displaystyle M_{1}}$ i ${\displaystyle M_{2}}$ również jest zbiorem diofantycznym, jako że reprezentacją diofantyczną tego przecięcia jest:

${\displaystyle D_{1}(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m_{1}})^{2}+D_{2}(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m_{2}})^{2}=0.}$

Twierdzenia Matijasiewicza[edytuj | edytuj kod]

Twierdzenie Matijasiewicza mówi, że każdy rekurencyjnie przeliczalny zbiór jest zbiorem diofantycznym. Zbiór ${\displaystyle S}$ jest rekurencyjnie przeliczalny wtw. gdy istnieje taka maszyna Turinga ${\displaystyle T,}$ że jeżeli maszyna ${\displaystyle T}$ działając na liczbę ${\displaystyle n}$ kończy pracę to ${\displaystyle n\in S.}$ 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 ${\displaystyle D(n,x_{1},\dots ,x_{n})=0}$ jest diofantyczną reprezentacją pewnego zbioru diofantycznego ${\displaystyle S}$ to zbiór ${\displaystyle S}$ jest rekurencyjnie przeliczalny. Algorytm wypisujący wszystkie elementy zbioru ${\displaystyle S}$ możemy uzyskać sprawdzając równość ${\displaystyle D(n,x_{1},\dots ,x_{n})=0}$ dla wszystkich możliwych uporządkowanych, n+1-elementowych krotek ${\displaystyle (n,x_{1},\dots ,x_{n})}$ (których jest przeliczalnie wiele z uwagi na przeliczalność iloczynów kartezjańskich zbiorów przeliczalnych).

Zobacz też[edytuj | edytuj kod]

• dziesiąty problem Hilberta
• równanie diofantyczne

Bibliografia[edytuj | edytuj kod]

• Yuri Matiyasevich, M. Davis, H. Putnam: Hilbert’s 10th Problem (Foundations of Computing). The MIT Press, 1993. ISBN 978-0262132954.