ディオファントス集合

数学において、ディオファントス方程式は、 P ( x ₁ , ..., x _j , y ₁ , ..., y _k ) = 0 (通常はP ( x , y ) = 0 と略記)の形式の方程式であり、 P ( x , y ) は整数係数の多項式であり、x ₁ , ..., x _jはパラメータを示し、y ₁ , ..., y _{k は} 未知数を示します。

ディオファントス集合 は、${\displaystyle \mathbb {N} ^{j}}$、自然数のj組の集合であり、あるディオファントス方程式P ( x , y ) = 0に対して、

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

すなわち、パラメータ値がディオファントス集合Sに含まれるのは、そのパラメータ値の下で関連するディオファントス方程式が充足可能である場合に限る。Sと存在量化の両方で自然数を使用しているのは、計算可能性理論とモデル理論における通常の応用を反映しているにすぎない。ディオファントス集合の2つの定義は同等であるため、自然数が非負整数の集合を指すか正整数の集合を指すかは問題ではない。同様に、整数のディオファントス集合について語ることも同様に可能であり、自然数上の量化を整数上の量化に自由に置き換えることができる。^{[ 1 ]}また、 Pが多項式であると仮定すれば十分である。${\displaystyle \mathbb {Q} }$そして、Pに適切な分母を掛けて整数係数を得る。しかし、有理数上の量化が整数上の量化の代わりにもなり得るかどうかは、非常に難しい未解決問題である。^{[ 2 ]}

MRDP定理(その解法に大きく貢献した 4 人の頭文字をとって名付けられた) は、整数の集合がディオファントス集合であるのは、それが計算可能列挙可能である場合に限ると述べています。^{[ 4 ] [ 5 ]}整数の集合Sが計算可能列挙可能であるのは、与えられた整数がSの要素であれば停止し、そうでなければ永久に実行されるアルゴリズムが存在する場合に限ります。これは、一見数論に属する一般ディオファントス集合の概念が、論理的または計算可能性理論的な観点から捉えることができることを意味します。しかし、これは決して自明ではなく、数十年にわたる研究の集大成でした。

マティヤセヴィッチによるMRDP定理の完成は、ヒルベルトの第10問題を解決した。ヒルベルトの第10問題^{[ 6 ]}は、与えられたディオファントス方程式が整数の中に解を持つかどうかを判定できる一般的なアルゴリズムを見つけることであった。ヒルベルトの第10問題は、それ自体は形式的な数学的記述ではないが、決定アルゴリズムと全計算可能述語との（哲学的）同一視がほぼ普遍的に受け入れられているため、MRDP定理を用いて第10問題は解決不可能であると結論付けることができる。

以下の例では、自然数とは正の整数の集合を指します。

方程式

${\displaystyle x=(y_{1}+1)(y_{2}+1)}$

これは、パラメータxと未知数y ₁およびy ₂を持つディオファントス方程式の一例です。この方程式は、x が1 より大きい 2 つの整数の積として表せる場合、つまりxが合成数である場合に限り、 y ₁およびy ₂に関して解を持ちます。具体的には、この方程式は集合のディオファントス定義を与えます。

{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

合成数から構成される。

ディオファントスの定義の他の例は以下のとおりです。

• 方程式${\displaystyle x=y_{1}^{2}+y_{2}^{2}}$パラメータxと未知数y ₁、y ₂のみで解を持つ${\displaystyle \mathbb {N} }$xが2つの平方数の和である場合、この方程式のディオファントス集合は{2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}です。
• 方程式${\displaystyle y_{1}^{2}-xy_{2}^{2}=1}$パラメータxと未知数y ₁、y ₂を持つ。これはペル方程式であり、解は のみを持つことを意味する。${\displaystyle \mathbb {N} }$xが平方数でない場合。ディオファントス集合は{2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}です。
• 方程式${\displaystyle x_{1}+y=x_{2}}$これは、2 つのパラメータx ₁、x ₂と未知数yを持つディオファントス方程式であり、 x ₁ < x ₂となるペア ( x ₁、x ₂ )の集合を定義します。

マティヤセビッチの定理（マティヤセビッチ・ロビンソン・デイビス・パトナム定理、またはMRDP定理とも呼ばれる）は、次のように述べている。

計算可能なすべての集合はディオファントス集合であり、その逆もまた然りである。

整数の集合Sは、次のようなアルゴリズムが存在する場合に計算可能列挙可能である。各整数入力nに対して、nがSの要素であれば、アルゴリズムは最終的に停止する。そうでなければ、アルゴリズムは永久に実行される。これは、永久に実行され、Sの要素を列挙するアルゴリズムが存在することと同等である。整数の集合Sは、整数係数f ( n , x ₁ , ..., x _k ) を持つ多項式が存在し、整数nがSに含まれるのは、 f ( n , x 1 , _{... ,} x _k ) = 0 となる整数x ₁ , ..., x _kが存在する場合に限る、という条件を満たす場合に限り、ディオファントス的である。

ディオファントス集合はすべて計算可能列挙可能であることは容易にわかります。ディオファントス方程式f ( n , x ₁ , ..., x _k ) = 0 を考えてみましょう。ここで 、 n、x ₁、 ..., x _kのすべての可能な値(たとえば、それらの絶対値の合計の昇順と一致する単純な順序で) を試行し、f ( n、x ₁、 ..., x _k ) = 0になるたびにnを出力するアルゴリズムを作成します。このアルゴリズムは永久に実行され、f ( n、x ₁、 ..., x _k ) = 0 がx ₁、 ..., x _kに解を持つnを正確にリストします。

ユーリ・マティヤセヴィッチは、指数関数的に増加するフィボナッチ数を用いた手法を用いて、ディオファントス方程式の解が指数関数的に増加する可能性があることを示した。ジュリア・ロビンソン、マーティン・デイビス、ヒラリー・パトナムによる以前の研究（MRDP）では、この手法を用いれば、計算可能なすべての集合がディオファントス集合であることを示すのに十分であることが示されていた。

ヒルベルトの第10問題は、ディオファントス方程式の可解性を判定する一般的なアルゴリズムを求めるものである。マティヤセヴィッチの結果と、ほとんどの再帰的に列挙可能な言語は判定不可能であるという事実を合わせると、ヒルベルトの第10問題の解は不可能であることが示唆される。

マティヤセビッチの定理はその後、微積分や微分方程式における多くの問題が解けないことを証明するために用いられてきた。

マティヤセヴィッチの結果から、ゲーデルの第一不完全性定理のより強い形式を以下のように導き出すこともできる。

数論の任意の一貫した公理化に対応して、^{[ 9 ]}解を持たないが、与えられた公理化内ではこの事実を証明できないディオファントス方程式を明示的に構成することができる。

不完全性定理によれば、十分に強力で一貫性のある公理的理論は不完全であり、その形式体系内ではいくつかの命題の真偽を立証できないことを意味する。上記の記述は、問題の理論が数論であると仮定すれば、この不完全性にはディオファントス方程式の解の存在が含まれるはずだと述べている。

• ScholarpediaのMatiyasevich 定理の記事。