テネンバウムの定理

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

PAの再帰構造

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が含まれることを示すことです。第二段階は、 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から始め、 aは非再帰的である。証明方法は、標準システムの定義方法により、Mの加法関数をオラクルとして用いて集合Sの特性関数を計算できることを示す。特に、が0に対応するMの元であり、が1に対応するMの元である場合、それぞれについて( i回)を計算できる。数nがSに含まれるかどうかを判定するには、まずp （n番目の素数）を計算する。次に、 yが次を満たす 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{ 回}}}\oplus n_{i}}$

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

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

PAモデルのチューリング度

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

参考文献

• ブーロス、ジョージ、バージェス、リチャード・ジェフリー（2002年）『計算可能性と論理』（第4版）ケンブリッジ大学出版局、ISBN 0-521-00758-5。
• ケイ、リチャード（1991）『ペアノ算術のモデル』オックスフォード大学出版局、ISBN 0-19-853213-X。
• ケイ、リチャード（2011年9月）「算術モデルのためのテネンバウムの定理」ジュリエット・ケネディ、ローマン・コサック編『集合論、算術、そして数学の基礎 ― 定理と哲学』（PDF）論理学講義ノート 第36巻ISBN 9781107008045。
• テネンバウム、スタンレー(1959). 「算術のための非アルキメデス的モデル」アメリカ数学会報6 : 270.

1. V. Harizanov,第1章「純粋計算可能モデル理論」 , Yu. L. Ershov, SS Goncharov, A. Nerode, JB Remmel編『Handbook of Recursive Mathematics』 (1998年, Elsevier) 第1章, p.13