D方程式（ディオファントス方程式）
定義 2.1記号列としての多項式全体を $\mathcal{P}$ で表すことにします． さらに，任意の多項式 $p \in \mathcal{P}$ に対して，$p$ に含まれる変数の集合を $var(p)$ で表すことにします． このとき，多項式の順序対からなる集合 $\mathcal{D}$ を次のように定義します．
$\mathcal{D} = \{ \langle p, q \rangle \mid p \in \mathcal{P}, q \in \mathcal{P}, var(p)=var(q) \}$
$\mathcal{D}$ の要素 $\langle p, q \rangle$ を D方程式 と呼ぶことにします．
さらに，D方程式を多項式内の変数を明記して $\langle p(\vec{x}), q(\vec{x}) \rangle$ などと表したり，変数を２つのグループに分けて議論とするときには $\langle p(\vec{x},\vec{y}), q(\vec{x},\vec{y}) \rangle$ などと表したりします．
■
補足
「D方程式」はディオファントス方程式を略したものです．一般に，ディオファントス方程式は整数係数の多変数多項式 $t(\vec{x})$ を使って $t(\vec{x})=0$ と表される方程式のことです．一方，この方程式は，$t(\vec{x})$ における負の積項を右辺に移項することによって，自然数係数の多変数多項式 $p(\vec{x})$ と $q(\vec{x})$ を使って $p(\vec{x}) = q(\vec{x})$ と表すことができます．上記の $\mathcal{D}$ はこのような方程式をすべて集めた集合です．このノートでは，記法上の混乱を避けるために，D方程式を等号を使って表さずに，上のような順序対によって表すことにします．
厳密に言うと，上記のD方程式の両辺 $p,q$（$t(\vec{x})$ における負の積項を右辺に移項して得られる２つの多項式）は一般に同じ変数を持っているとは限りません．一方，$\bar{0}$ を係数とする積項を便宜的に追加することによって両辺を同じ変数を持つようにできます．従って，両辺が同一の変数を持つと仮定しても，少なくとも標準モデルの上では一般性を失うことはありません．
ただ，D方程式の両辺が同じ変数を持つかどうかは本当はどうでもよいことです．このノートでは，D方程式の両辺が異なる変数を持ったときの表記法がうまく思いつかなかったので，両辺が同じ変数を持つような方程式だけを扱うことにしています．上記の「$var(p)=var(q)$」という条件は単に表記法に関する都合でしかありません．
■
前節の多項式の定義から，
次の命題は明らかと言っても怒られることはないでしょう．
以後の議論では，この命題を暗黙的に利用します．
命題 2.2$\mathcal{P}$ は計算可能です． 従って，$\mathcal{D}$ も計算可能です．■
MRDP定理とその系
定理 2.3（MRDP定理）任意の計算的枚挙可能な集合 $A \subseteq \mathbb{N}^n$ に対して，D方程式 $\langle p(\vec{x},\vec{y}),q(\vec{x},\vec{y}) \rangle \in \mathcal{D}$ が存在して，
$A = \{ \vec{a} \in \mathbb{N}^n \mid
\mathcal{N} \models \exists{\vec{y}}(p(\widehat{\vec{a}},\vec{y}) = q(\widehat{\vec{a}},\vec{y})) \}$
が成り立ちます．ここで，$\vec{a}$ は自然数列 $a_1, a_2, \ldots, a_n$ の省略記法であり，$\widehat{\vec{a}}$ は数項列 $\widehat{a_1}, \widehat{a_2}, \ldots, \widehat{a_n}$ の省略記法です．さらに，$\vec{y}$ は変数列 $y_1, \ldots, y_m$ の省略記法であり，「$\exists{\vec{y}}$」は「$\exists{y_1}\exists{y_2} \cdots \exists{y_m}$」の省略記法です．
■
定義 2.4$\mathcal{D}$ の部分集合 $\mathcal{D}^\mathcal{N}_\exists$ と $\mathcal{D}^\mathcal{N}_\forall$ を次のように定義します．
$\mathcal{D}^\mathcal{N}_\exists$ $=$
$\{ \langle p, q \rangle \in \mathcal{D} \mid
\mathcal{N} \models \exists{\vec{x}}(p(\vec{x})=q(\vec{x})) \}$
$\mathcal{D}^\mathcal{N}_\forall$ $=$ $\{ \langle p, q \rangle \in \mathcal{D} \mid \mathcal{N} \models \forall{\vec{x}}\neg(p(\vec{x})=q(\vec{x})) \}$
ここで，$\vec{x}$は変数列 $x_1, x_2, \ldots, x_n$ の省略記法であり，
「$\exists{\vec{x}}$」は「$\exists{x_1}\exists{x_2} \cdots \exists{x_n}$」の省略記法です．「$\forall{\vec{x}}$」も「$\forall{x_1}\forall{x_2}\cdots\forall{x_n}$」の省略記法です．
$\mathcal{D}^\mathcal{N}_\exists$ は自然数解を持つD方程式の集合であり，
$\mathcal{D}^\mathcal{N}_\forall$ は自然数解を持たないD方程式の集合です．
系 2.5$\mathcal{D}^\mathcal{N}_\forall$ $=$ $\{ \langle p, q \rangle \in \mathcal{D} \mid \mathcal{N} \models \forall{\vec{x}}\neg(p(\vec{x})=q(\vec{x})) \}$
上で定義した２つの集合に対して次が成り立ちます．
- $\mathcal{D}^\mathcal{N}_\exists$ は計算的枚挙可能ですが計算不可能です．
- $\mathcal{D}^\mathcal{N}_\forall$ は計算的枚挙可能ですらありません．
\(
a \in K \iff
\mathcal{N} \models \exists{\vec{y}}(p(\widehat{a},\vec{y}) = q(\widehat{a},\vec{y})) \iff
\langle p(\widehat{a},\vec{y}),q(\widehat{a},\vec{y}) \rangle \in \mathcal{D}^\mathcal{N}_\exists
\)
が成り立ちます．これは，$K$ が $\mathcal{D}^\mathcal{N}_\exists$ に還元可能（many-one reducible）であることを示しています．従って，$\mathcal{D}^\mathcal{N}_\exists$ は計算不可能です．(2) $\mathcal{D}^\mathcal{N}_\exists$ と $\mathcal{D}^\mathcal{N}_\forall$ の定義から， $\mathcal{D} = \mathcal{D}^\mathcal{N}_\exists \cup \mathcal{D}^\mathcal{N}_\forall$ かつ $\mathcal{D}^\mathcal{N}_\exists \cap\mathcal{D}^\mathcal{N}_\forall = \emptyset$ が成り立ちます．さらに，$\mathcal{D}$ は計算可能です．つまり， $\mathcal{D}^\mathcal{N}_\exists$ と $\mathcal{D}^\mathcal{N}_\forall$ は計算可能集合を全体集合とする補集合の関係にあります．この事実より，$\mathcal{D}^\mathcal{N}_\forall$ が計算的枚挙可能であると仮定すると，$\mathcal{D}^\mathcal{N}_\exists$ が計算可能となってしまって(1)に反します．よって，$\mathcal{D}^\mathcal{N}_\forall$ は計算的枚挙可能ではありません．■ 補足 次節以降の議論では，$\mathcal{D}^\mathcal{N}_\forall$ が計算的枚挙可能でないという事実を利用します． ■