ディオファントスセット

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

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

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

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

MRDP定理（解決に寄与した4人の主要人物の頭文字をとって名付けられた）は、整数の集合がディオファントス集合であるための必要条件は、それが計算可能列挙可能であることである。^[3]整数の集合Sが計算可能列挙可能であるのは、与えられた整数がSのメンバーであれば停止し、そうでない場合は永久に実行されるアルゴリズムが存在する場合のみである。これは、明らかに数論に属する一般ディオファントス集合の概念は、むしろ論理的または計算可能性理論的な用語で捉えることができることを意味している。しかし、これは決して自明ではなく、数十年にわたる研究の集大成である。

マティヤセビッチのMRDP定理の完成により、ヒルベルトの第10問題は解決されました。ヒルベルトの第10問題^[4]は、与えられたディオファントス方程式が整数の中に解を持つかどうかを決定できる一般的なアルゴリズムを見つけることでした。ヒルベルトの第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、...}

合成数から構成されます。

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

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

マティヤセビッチの定理は、マティヤセビッチ–ロビンソン–デイビス–パトナム定理または MRDP 定理とも呼ばれ、次のことを述べています。

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

整数の集合Sが計算可能に列挙可能であるのは、次のようなアルゴリズムが存在する場合です。各整数入力nに対して、n がSのメンバーであれば、アルゴリズムは最終的に停止します。そうでない場合は、永久に実行されます。これは、永久に実行され、Sのメンバーをリストするアルゴリズムが存在すると言っているのと同じです。集合Sがディオファントス多項式であるためには、整数係数f ( n、x ₁、 ...、x _k ) を持つ何らかの多項式が存在し、整数nがSに含まれる場合と、 f ( n、x ₁、 ...、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 つの自然数変数 (Matiyasevich、1977) または 11 の整数変数 ( Zhi Wei Sun、1992) しかない場合でも決定不可能であることが示されました。

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

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

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

不完全性定理によれば、十分に強力で一貫した公理理論は不完全であり、その命題のいくつかの真実はその形式論の範囲内で確立できないことを意味する。上記の記述は、問題の理論が数論であると仮定すると、この不完全性にはディオファントス方程式の可解性が含まれなければならないことを述べている。

• マティヤセビッチ、ユーリ・V.（1970）。 Диофантовость перечислимых множеств[数え切れない集合はディオファンティーンです]。Doklady Akademii Nauk SSSR (ロシア語)。191 : 279–282。MR 0258744  。​英語訳はSoviet Mathematics 11 (2)、pp. 354-357に掲載。
• デイビス、マーティン(1973)。 「ヒルベルトの第 10 問題 は解決不可能」。アメリカ数学月刊誌。80 (  3 ): 233– 269。doi :10.2307/2318447。ISSN 0002-9890。JSTOR 2318447。Zbl 0277.02008  。
• Matiyasevich, Yuri V. (1993)。ヒルベルトの第 10 の問題。MIT プレスのコンピューティングの基礎シリーズ。マーティン・デイビスとヒラリー・パトナムによる序文。マサチューセッツ州ケンブリッジ: MIT プレス。ISBN 0-262-13295-8.ZBL0790.03008  。​
• シュラペントーク、アレクサンドラ (2007)。ヒルベルトの第 10 問題。ディオファントス類と大域体への拡張。新数学モノグラフ。第 7 巻。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-83360-8.ZBL1196.11166  。​
• Sun Zhi-Wei (1992). 「ディオファントス表現における未知数の削減」(PDF) . Science China Mathematics . 35 (3): 257– 269. Zbl  0773.11077. 2011-07-07 にオリジナルからアーカイブ(PDF)されました。

• Scholarpediaの Matiyasevich 定理の記事。