MathLabs

解法: MRDP定理:ディオファントス集合は帰納的可算集合と一致する(1970年)

ステップ 5/9: Davis–Putnam–Robinson 1961年:すべてのr.e.集合は指数ディオファントスである
前のステップ次のステップ
ざっくり言うと

「指数ディオファントス方程式」とは、単なる多項式方程式よりも寛容な種類の方程式であり、変数を掛け合わせたり足し合わせたりするだけでなく、xy=zx^y = z のように指数にも変数が現れることを許す。1961年、Martin Davis、Hilary Putnam、Julia Robinsonは、この追加の寛容さがあれば、すべてのリスト化可能な集合をすでに例外なく正確に捉えられることを証明した。

これは、Davisの1953年の当初の予想に残っていた困難全体が、一つの正確に述べられた技術的障害へと絞り込まれたことを意味した:指数を通常の多項式の形へと押し戻す方法を見つけることであり、それはまさに前のステップのRobinsonのJR仮説である。

r.e. set  ⟺  ∃ exponential Diophantine eq. Q(a,x1,…,xk,y1,…,yl)=0, yi appear as exponents\text{r.e. set} \iff \exists \text{ exponential Diophantine eq. } Q(a, x_1, \ldots, x_k, y_1, \ldots, y_l) = 0,\ y_i \text{ appear as exponents}
詳しい解説

指数ディオファントス方程式は、変数が指数として現れることを許す。例えば Q(a,x1,…,xk,y1,…,yl)=0Q(a, x_1, \ldots, x_k, y_1, \ldots, y_l) = 0 で、いくつかの yiy_i が QQ のどこかで指数として現れる。集合 SS が指数ディオファントスであるとは、通常のディオファントス集合と同じように、そこに属することがそのような方程式によって表現できることをいう。

1961年、Davis、Putnam、Robinsonは、Davisの標準形(一つの有界全称量化子)と、指数サイズの構成要素(またしてもペル方程式の解)が利用可能なときに有界量化子を排除するRobinsonの以前の存在論的定義可能性の技法を組み合わせることで、すべての帰納的可算集合が指数ディオファントスであることを証明した。これは、当初の予想が通常の多項式方程式のみについてのものであったにもかかわらず、より広い指数方程式のクラスについてDavisの予想を完全に証明するものだった。

この1961年の結果とDavisの1953年の完全な予想との間に残る隙間全体が、今やまさにRobinsonのJR仮説となった:指数的増大を持つ純粋に多項式的な(非指数的な)ディオファントス関係を一つ見つければ、あらゆる指数ディオファントス的定義は通常の定義へと書き換えられる。この唯一残った隙間を埋めるには1970年までかかり、それが次のステップの主題である。

このステップの用語
指数ディオファントス方程式
整数変数を用いた加法、乗法、べき乗から構築される方程式のことで、例えば xy+z=wx^y + z = w のように、(定数だけでなく)変数を指数として許すもの——通常の多項式方程式よりも厳密に表現力の高い方程式のクラスである。
このステップで使う知識
一次不定方程