テネンバウムの定理

テネンバウムの定理は、 1959年に定理を発表したスタンレー・テネンバウムにちなんで名付けられた、一階ペアノ算術(PA)の可算な非標準モデルは再帰的ではないという数理論理学の結果である(Kaye 1991:153ff)。

PA言語の構造が再帰的であるとは 、からへの再帰関数と、上の再帰的な2項関係 < _M、および次のような 区別された定数がある場合である。${\displaystyle M}$${\displaystyle \oplus}$${\displaystyle \otimes }$${\displaystyle \mathbb {N} \times \mathbb {N} }$${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$${\displaystyle n_{0},n_{1}}$

${\displaystyle (\mathbb {N} ,\oplus ,\otimes ,<_{M},n_{0},n_{1})\cong M,}$

ここで、 は同型性を示し、は（標準）自然数の集合です。同型性は全単射でなければならないため、すべての再帰モデルは可算です。PA には、同型でない可算な非標準モデルが多数存在します。 ${\displaystyle \cong}$${\displaystyle \mathbb {N} }$

テネンバウムの定理によれば、PA の可算な非標準モデルは再帰的ではない。さらに、そのようなモデルの加算も乗算も再帰的ではない。

この概略は、Kaye (1991) が提示した議論に従っています。証明の最初のステップは、M がPA の任意の可算な非標準モデルである場合、 Mの標準システム(以下で定義) には少なくとも 1 つの非再帰的な集合Sが含まれることを示すことです。2 番目のステップは、 Mの加算または乗算のいずれかの演算が再帰的である場合、この集合S は再帰的になることを示すことですが、これは矛盾です。

順序付きタプルをコード化するために使用される方法により、各要素はMの要素の集合のコードとして見ることができます。特に、 をMのi番目の素数とすると、 となります。各集合はMで有界になりますが、xが非標準の場合、集合には無限個の標準自然数が含まれる可能性があります。モデルの標準システムはコレクション です。PA の任意の非標準モデルの標準システムには、不完全性定理を適用するか、再帰的に分離不可能なre 集合のペアを直接考慮することによって、非再帰集合が含まれていることが示されます(Kaye 1991:154)。これらは互いに素な re 集合であるため、および を含む再帰集合は存在しません。 ${\displaystyle x\in M}$${\displaystyle S_{x}}$${\displaystyle p_{i}}$${\displaystyle z\in S_{x}\leftrightarrow M\vDash p_{z}|x}$${\displaystyle S_{x}}$${\displaystyle S_{x}}$${\displaystyle \{S_{x}\cap \mathbb {N} :x\in M\}}$${\displaystyle A,B\subseteq \mathbb {N} }$${\displaystyle C\subseteq \mathbb {N} }$${\displaystyle A\subseteq C}$${\displaystyle B\cap C=\emptyset }$

後者の構成では、再帰的に分離不可能な集合AとBのペアから始める。自然数xに対して、すべてのi < xに対して、であればであり、 であればとなるyが存在する。オーバースピル特性により、これはMに非標準のxが存在し、それに対してMに(必然的に非標準の) y が存在することを意味し、 となる任意の に対して、次が成り立つ 。${\displaystyle i\in A}$${\displaystyle p_{i}|y}$${\displaystyle i\in B}$${\displaystyle p_{i}\nmid y}$${\displaystyle m\in M}$${\displaystyle m<_{M}x}$

${\displaystyle M\vDash (m\in A\to p_{m}|y)\land (m\in B\to p_{m}\nmid y)}$

をMの標準システムにおける対応する集合とします。AとB はre なので、およびであることを示すことができます。したがって、S はAとBの分離集合であり、 AとBの選択により、S は非再帰的であることを意味します。 ${\displaystyle S=\mathbb {N} \cap S_{y}}$${\displaystyle A\subseteq S}$${\displaystyle B\cap S=\emptyset }$

さて、テネンバウムの定理を証明するには、非標準の可算モデルMと、が非再帰的となるMの元aから始めます。証明方法は、標準システムの定義方法により、 Mの加算関数をオラクルとして使用して集合Sの特性関数を計算できることを示しています。特に、 が0 に対応するMの元であり、 が1 に対応するMの元である場合、それぞれについて( i回)を計算できます。数nがSに含まれるかどうかを判断するには、まず のn番目の素数p を計算します。次に、となる Mの元yを検索します。${\displaystyle S=\mathbb {N} \cap S_{a}}$${\displaystyle \oplus}$${\displaystyle n_{0}}$${\displaystyle n_{1}}$${\displaystyle i\in \mathbb {N} }$${\displaystyle n_{i}=n_{1}\oplus \cdots \oplus n_{1}}$${\displaystyle \mathbb {N} }$

${\displaystyle a=\underbrace {y\oplus y\oplus \cdots \oplus y} _{p{\text{ times}}}\oplus n_{i}}$

に対して となります。ユークリッドの互除法はPA のどのモデルにも適用できるため、この探索は停止します。最後に、探索で見つかったiが 0 の場合に限り となります。S は再帰的でないため、 Mの加算演算は非再帰的であることを意味します。 ${\displaystyle i<p}$${\displaystyle n\in S}$

同様の議論は、 Mの乗算をオラクルとして使用してSの特性関数を計算することが可能であることを示し、したがってMの乗算演算も非再帰的である (Kaye 1991:154)。

ジョックシュとソアレは、低次数のPAモデルが存在することを示した。^[1]