Tennenbaumの定理

同義語:Tennenbaum's theorem

概要

Tennenbaumの定理(Tennenbaum's theorem)とは、Peano 算術 $\mathsf{PA}$ の超準モデルは、台集合を自然数の集合に取り直してどのように書き表しても、加法が計算可能な関数にならないという定理である。とくに演算と順序がすべて計算可能な $\mathsf{PA}$ のモデルは同型を除いて標準モデルだけである。証明の鍵は、計算可能な集合で分けられない 2 つの計算可能枚挙集合を分ける集合を、オーバースピルによって超準モデルの 1 つの元の標準的な素数での割り切れ方として書き込めることであり、加法が計算可能なら割った余りからその集合が計算できてしまう。帰納法を持たない Robinson 算術には演算が計算可能な超準モデルがあり、$\mathsf{PA}$ の可算な超準モデルも順序だけなら計算可能に表示できる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Peano算術, 超準モデル, 計算可能性理論

Tennenbaumの定理(Tennenbaum's theorem)は、Peano算術 $\mathsf{PA}$ の超準モデルを、演算が計算できる形で書き表すことはできない、という定理である。可算な超準モデル $\mathcal M$ は、台集合を自然数の集合 $\mathbb N$ に取り直すことができるが、どう取り直しても加法 $+^{\mathcal M}$ は $\mathbb N\times\mathbb N\to\mathbb N$ の計算可能な関数にならない。したがって、演算と順序がすべて計算可能な $\mathsf{PA}$ のモデルは、同型を除いて標準モデル $\mathfrak N$ だけである(OLT26 Theorem 26.22、p. 403)。
この結論は $\mathsf{PA}$ の帰納法の公理図式に強く依存している。帰納法を持たない Robinson算術 $\mathsf Q$ には演算が計算可能な超準モデルがあり、$\mathsf{PA}$ の可算な超準モデルでも、順序だけなら計算可能に書き表せる。Tennenbaum の定理は、超準モデルが コンパクト性定理(一階論理) によって存在すること(超準モデル)と、その具体的な姿が計算で捉えられないこととの対比を示している。
証明の考え方は次のとおりである。計算可能な手順では分けられない 2 つの計算可能枚挙集合をとる。超準モデルの中では、オーバースピルによって「標準的な素数のどれで割り切れるか」という形で、一方を含み他方と交わらない集合を 1 つの元 $a$ に書き込める。加法が計算できると、$a$ をそれぞれの素数で割った余りが計算でき、書き込んだ集合が計算可能になって矛盾する。

前提と記法

言語 $L_A=\{0,S,+,\cdot,< \}$、数項 $\underline n$、標準モデル $\mathfrak N$、$\mathsf Q$ と $\mathsf{PA}$ の公理は Peano算術 の定義「Peano算術」に従う。$\mathsf{PA}$ のモデル $\mathcal M$ の元のうち、ある $n$ について $\underline n^{\mathcal M}$ と書けるものを 標準元、そうでないものを 非標準元 といい、非標準元をもつモデルを 超準モデル という(超準モデル の定義「標準元・非標準元・超準モデル」)。$\Delta_0$ 論理式(有界な量化だけをもつ論理式)と $\Sigma_1$ 論理式は Robinson算術 の定義「$\Delta_0$ 論理式・$\Sigma_1$ 論理式・$\Pi_1$ 論理式」に従う。
使う事実は次の 4 つである。

  • (F1) $\Sigma_1$ 完全性.$\mathfrak N$ で真な $\Sigma_1$ 文は $\mathsf Q$ で証明できる(Robinson算術 の定理「$\mathsf Q$ の $\Sigma_1$ 完全性」)。$\mathsf{PA}$ は $\mathsf Q$ を含むので、そのような文は $\mathsf{PA}$ のすべてのモデルで真である。とくに $\mathfrak N$ で真な $\Delta_0$ 文は $\mathsf{PA}$ のすべてのモデルで真である。
  • (F2) 標準元は先頭に並ぶ.$\mathsf{PA}$ のモデルでは、標準元はすべての非標準元より小さい(Peano算術 の定理「$\mathsf{PA}$ の超準モデルの順序」の 1)。
  • (F3) オーバースピル.$\mathcal M$ を $\mathsf{PA}$ の超準モデル、$\varphi(x)$ を論理式とする。すべての $n$ で $\mathcal M\models\varphi(\underline n)$ なら、ある非標準元 $c$ で $\mathcal M\models\varphi(c)$ である(Peano算術 の命題「オーバースピル」)。
  • (F4) MRDP の定理.計算可能枚挙な集合 $S\subseteq\mathbb N$ には、自然数係数の多項式 $P^+(x,y_1,\dots,y_m)$、$P^-(x,y_1,\dots,y_m)$ があって、$x\in S\iff$ ある $y\in\mathbb N^m$ で $P^+(x,y)=P^-(x,y)$ となる(MRDPの定理。整数係数の定義多項式の負の係数の項を右辺へ移せばこの形になる)。

計算可能な表示.$L_A$ の構造 $\mathcal M$ について、台集合が $\mathbb N$ で、後者・和・積が計算可能な関数、$<$ が決定可能な関係であるとき、$\mathcal M$ は 計算可能 であるという(OLT26 Definition 26.20、p. 402)。より細かく、$\mathcal M$ と同型で台集合が $\mathbb N$ の構造 $\mathcal M'$ があって、$+^{\mathcal M'}\colon\mathbb N^2\to\mathbb N$ が計算可能なとき、$\mathcal M$ の 加法は計算可能に表示できる という。同型な構造に取り替えても以下の議論は変わらないので、そのときは $\mathcal M$ の台集合をはじめから $\mathbb N$ とし、$+^{\mathcal M}$ を計算可能とする。

定理

Tennenbaumの定理

$\mathcal M$ を $\mathsf{PA}$ の超準モデルとする。$\mathcal M$ の加法は計算可能に表示できない。すなわち、$\mathcal M$ と同型で台集合が $\mathbb N$ のどの構造でも、加法は計算可能な関数でない。

計算可能なモデルは標準モデルだけ

$\mathsf{PA}$ の計算可能なモデルは $\mathfrak N$ と同型である。

加法が計算可能でないことから

計算可能なモデル $\mathcal M$ は、加法が計算可能な関数なので、thm-tb-main により超準モデルではない。非標準元をもたない $\mathsf{PA}$ のモデルでは、$n\mapsto\underline n^{\mathcal M}$ は全射であり、Robinson算術 の補題「数項の計算と大小」の 1〜3・5 により単射で、後者・和・積・大小を保つ(たとえば 1 から $\mathsf Q\vdash\underline m+\underline n=\underline{m+n}$)。よって $\mathcal M$ は $\mathfrak N$ と同型である。$\square$

$\mathsf{PA}$ の超準モデルは コンパクト性定理(一階論理) から存在し、可算なものもある(Peano算術 の命題「超準モデルの存在」)。系は、それらがどれも演算まで計算可能には表せないことを述べる。非可算なモデルは台集合を $\mathbb N$ にとれないので、はじめから計算可能ではない。

補題

計算可能に分離できない集合

互いに交わらない計算可能枚挙な集合 $U,V\subseteq\mathbb N$ で、$U\subseteq C$ かつ $C\cap V=\emptyset$ となる計算可能な集合 $C$ が存在しないものがある。さらに、$p_n$ を $n$ 番目の素数($p_0=2$)として $U':=\{p_n\mid n\in U\}$、$V':=\{p_n\mid n\in V\}$ とおくと、$U',V'$ は素数からなる互いに交わらない計算可能枚挙な集合で、$U'\subseteq C'$ かつ $C'\cap V'=\emptyset$ となる計算可能な集合 $C'$ は存在しない。

自分の番号で値を反転する

計算可能性理論 の記事の番号付け $\varphi_e$ を使い、
$$ U:=\{e\mid\varphi_e(e)\!\downarrow=0\},\qquad V:=\{e\mid\varphi_e(e)\!\downarrow=1\} $$
とおく。$(e,x)\mapsto\varphi_e(x)$ は部分計算可能なので、$\varphi_e(e)$ を計算して値を見る手順により $U,V$ は計算可能枚挙であり、明らかに交わらない。計算可能な $C$ で $U\subseteq C$、$C\cap V=\emptyset$ となるものがあったとし、$C$ の特性関数を $\varphi_d$ とする。$\varphi_d(d)\in\{0,1\}$ である。$\varphi_d(d)=1$ なら $d\in C$ だが、$d\in V$ なので $C\cap V=\emptyset$ に反する。$\varphi_d(d)=0$ なら $d\notin C$ だが、$d\in U\subseteq C$ に反する。
後半:$n\mapsto p_n$ は計算可能なので $U',V'$ は計算可能枚挙で、交わらない。計算可能な $C'$ が $U'\subseteq C'$、$C'\cap V'=\emptyset$ を満たせば、$C:=\{n\mid p_n\in C'\}$ は計算可能で $U\subseteq C$、$C\cap V=\emptyset$ を満たし、前半に反する。$\square$

標準の数で割る

$p\ge1$ を自然数とする。次の文はすべて $\mathsf{PA}$ で証明できる(自由変数は全称量化する)。

  1. $\underline p\cdot q=q+\cdots+q$(右辺は $q$ を $p$ 個加えたもの)であり、$q\le\underline p\cdot q$ である。
  2. $\displaystyle\exists q\,\bigvee_{r< p}a=\underline p\cdot q+\underline r$。
  3. $r,r'< p$ について、$\underline p\cdot q+\underline r=\underline p\cdot q'+\underline{r'}$ なら $q=q'$ かつ $r=r'$($r\ne r'$ なら矛盾が導ける)。
帰納法と打ち消し
証明を開く

以下、Peano算術 の定理「$\mathsf{PA}$ が証明する基本法則」の番号 (A1)〜(O8)・(M1)〜(M5) を使う。また $x+\underline1=Sx$(公理 4・5)と、$\underline{r+1}=S\underline r$(数項の定義)を使う。

1:自然数 $p$ についての(理論の外での)帰納法で、$\underline{p}\cdot q=q\cdot\underline p$((M3))$=q\cdot\underline{p-1}+q$(公理 7)を繰り返し、$q\cdot0=0$(公理 6)と (A1) で終わる。$q\le\underline p\cdot q$ は、$\underline p\cdot q=q+d$($d$ は残りの $p-1$ 個の和)と (O7) による。

2:$a$ についての帰納法。$a=0$ では $q=0$、$r=0$ とする(公理 6・4)。$a=\underline p\cdot q+\underline r$ とする。$r+1< p$ なら $Sa=\underline p\cdot q+\underline{r+1}$(公理 5)。$r=p-1$ なら $Sa=\underline p\cdot q+\underline p=\underline p\cdot Sq+0$(公理 7・4)。

3:$q< q'$ とすると (O1) で $q'=q+Sz$ と書け、(M4) と公理 7 から $\underline p\cdot q'=\underline p\cdot q+\underline p\cdot z+\underline p$ となる。等式の両辺から $\underline p\cdot q$ を打ち消すと((A3)・(A4)・(A5))$\underline r=(\underline p\cdot z+\underline{r'})+\underline p$ なので (O7) から $\underline p\le\underline r$ となり、$\underline r< \underline p$(Robinson算術 の補題「数項の計算と大小」の 3)と (O2)・(O3) に反する。$q'< q$ も同様で、(O4) から $q=q'$。このとき (A5) から $\underline r=\underline{r'}$ で、$r\ne r'$ なら Robinson算術 の補題「数項の計算と大小」により $\mathsf Q\vdash\underline r\ne\underline{r'}$ なので矛盾する。$\square$

定理の証明

分離できない集合を 1 つの元に書き込む

$\mathcal M$ の台集合を $\mathbb N$ とし、$+^{\mathcal M}$ が計算可能だと仮定して矛盾を導く。
段 1:有界な論理式を用意する. lem-tb-inseparable の $U',V'$ に (F4) を使い、自然数係数の多項式で
$$ x\in U'\iff\exists y\ P^+(x,y)=P^-(x,y),\qquad x\in V'\iff\exists y\ Q^+(x,y)=Q^-(x,y) $$
($y=(y_1,\dots,y_m)$、変数の個数は同じにそろえる)と書く。$L_A$ の $\Delta_0$ 論理式を
$$ \alpha(x,s):\ \exists y_1< s\cdots\exists y_m< s\ \ P^+(x,y)=P^-(x,y) $$
とし、$Q^\pm$ から同様に $\beta(x,t)$ を作る(多項式は $+$ と $\cdot$ と数項からなる項で書く)。$x\in U'\iff\mathfrak N\models\exists s\,\alpha(x,s)$、$x\in V'\iff\mathfrak N\models\exists t\,\beta(x,t)$ である。$\mathrm{Pr}(x)$ を「$x$ は素数」を表す $\Delta_0$ 論理式 $\underline1< x\land\forall u< Sx\ \forall v< Sx\,(u\cdot v=x\to u=\underline1\lor v=\underline1)$ とし、
$$ \begin{aligned} \delta(a,c):\ &\forall x< c\,\Bigl(\mathrm{Pr}(x)\to\bigl(\exists s< c\ \alpha(x,s)\leftrightarrow\exists q< Sa\ x\cdot q=a\bigr)\Bigr)\\ &\land\ \forall x< c\ \forall s< c\ \forall t< c\ \lnot\bigl(\alpha(x,s)\land\beta(x,t)\bigr) \end{aligned} $$
とおく。$\delta$ は $\Delta_0$ 論理式である。
段 2:標準の $c$ では成り立つ. 自然数 $c$ を固定し、$Y:=\{x< c\mid x\text{ は素数で、ある }s< c\text{ で }\mathfrak N\models\alpha(x,s)\}$、$a:=\prod_{x\in Y}x$($Y=\emptyset$ なら $a=1$)とおく。素数 $x< c$ について、$x$ が $a$ を割り切るのは $x\in Y$ のときに限り、割り切るなら商は $a$ 以下である。また $\alpha(x,s)$ と $\beta(x,t)$ が同時に成り立てば $x\in U'\cap V'=\emptyset$ となるので、2 行目も成り立つ。よって $\mathfrak N\models\delta(\underline a,\underline c)$ で、$\Sigma_1$ 文 $\exists a\,\delta(a,\underline c)$ は $\mathfrak N$ で真である。(F1) により、すべての自然数 $c$ について $\mathcal M\models\exists a\,\delta(a,\underline c)$ である。
段 3:非標準の $c$ でも成り立つ. (F3) を論理式 $\exists a\,\delta(a,c)$ に使うと、非標準元 $c^*$ と元 $a^*$ で $\mathcal M\models\delta(a^*,c^*)$ となるものがある。$a^*$ と $c^*$ を固定し、
$$ C':=\{p\mid p\text{ は素数で、}\mathcal M\models\exists q< Sa^*\ \underline p\cdot q=a^*\} $$
とおく。$U'\subseteq C'$ かつ $C'\cap V'=\emptyset$ を示す。素数 $p$ について $\mathrm{Pr}(\underline p)$ は $\mathfrak N$ で真な $\Delta_0$ 文なので $\mathcal M$ でも真であり、(F2) から $\underline p< c^*$ である。

  • $p\in U'$ なら、ある自然数 $s$ で $\mathfrak N\models\alpha(\underline p,\underline s)$ であり、(F1) から $\mathcal M\models\alpha(\underline p,\underline s)$、(F2) から $\underline s< c^*$ である。$\delta$ の 1 行目から $\mathcal M\models\exists q< Sa^*\ \underline p\cdot q=a^*$、すなわち $p\in C'$ である。
  • $p\in V'$ なら、同様に自然数 $t$ で $\mathcal M\models\beta(\underline p,\underline t)$、$\underline t< c^*$ である。$\delta$ の 2 行目から、$s< c^*$ で $\mathcal M\models\alpha(\underline p,s)$ となる $s$ はない。$\delta$ の 1 行目から $\mathcal M\not\models\exists q< Sa^*\ \underline p\cdot q=a^*$、すなわち $p\notin C'$ である。

段 4:$C'$ は計算可能になる. lem-tb-division の 2・3 により、素数 $p$ について、$\mathcal M\models a^*=\underline p\cdot q+\underline r$ となる $q\in\mathcal M$ と $r< p$ の組がただ 1 つある。$r=0$ なら、1 から $q\le a^*$ で $p\in C'$ である。逆に $p\in C'$ なら $a^*=\underline p\cdot q+\underline 0$ と書けるので、一意性から $r=0$ である。よって
$$ p\in C'\iff p\text{ は素数で、}a^*\text{ を }\underline p\text{ で割った余り }r\text{ が }0 $$
である。
この余りを計算する手順を作る。$\mathcal M$ の台集合は $\mathbb N$ なので、$0^{\mathcal M}$、$\underline1^{\mathcal M}$、$a^*$ はそれぞれある自然数であり、それらを手順に書き込んでおく。$\underline r^{\mathcal M}$ は $\underline1^{\mathcal M}$ を $r$ 個 $+^{\mathcal M}$ で加えて計算できる($r=0$ なら $0^{\mathcal M}$)。素数 $p$ が与えられたら、$q=0,1,2,\dots$ と $r=0,1,\dots,p-1$ の組を順に調べ、
$$ \underbrace{q+^{\mathcal M}\cdots+^{\mathcal M}q}_{p\text{ 個}}+^{\mathcal M}\underline r^{\mathcal M}=a^* $$
となる最初の組で止まって $r$ を出力する。lem-tb-division の 1 により左辺は $\underline p\cdot q+\underline r$ の $\mathcal M$ での値なので、この組はちょうど 1 つあり、手順は必ず止まって正しい余りを出す。$+^{\mathcal M}$ が計算可能なので、これは計算可能な手順である。
素数の判定も計算可能なので $C'$ は計算可能な集合であり、$U'\subseteq C'$、$C'\cap V'=\emptyset$ を満たす。これは lem-tb-inseparable に反する。したがって $+^{\mathcal M}$ は計算可能でない。$\square$

加法が計算可能だという仮定を使ったのは段 4 だけである。$a^*$ は $\mathcal M$ の中では普通の数で、「標準的な素数のどれで割り切れるか」という情報の中に、計算できない集合 $C'$ が書き込まれている。

乗法だけの場合

乗法 $\cdot^{\mathcal M}$ だけについても、次の段落の $\mathsf{PA}$ での事実(この記事では示さない)を認めれば、計算可能に表示できないという同じ結論が得られる。上の証明を乗法だけに移すには、加法を使った「割った余り」の計算を、乗法だけで書ける判定に取り替える必要がある。ここではその筋だけを述べ、細部は書かない。
$\mathsf{PA}$ で $2^x$ を定義し、指数法則、$x\mapsto2^x$ が単射であること、「$2^b$ の約数は 2 の累乗である」ことを証明できることを使う(この記事では示さない)。段 3 の $a^*$ に対して $a^{**}:=2^{a^*}$ とおく。素数 $p$ について、$\mathcal M$ では $a^{**}=y^{\underline p}\cdot2^{\underline r}$($r< p$)となる $y$ と $r$ がただ 1 つあり、$r$ は $a^*$ を $\underline p$ で割った余りである。$y^{\underline p}$ と $2^{\underline r}$ は乗法を $p$ 回・$r$ 回使えば計算できるので、$\underline 2^{\mathcal M}$ と $a^{**}$ を手順に書き込めば、段 4 と同じ探索で余りが加法なしに計算できる。したがって $\cdot^{\mathcal M}$ が計算可能なら $C'$ が計算可能になり、矛盾する。

例

演算が計算可能な $\mathsf Q$ の超準モデル

$\mathbb N$ に新しい元 $a$ を 1 つ加えた $\mathbb N\cup\{a\}$ の上に、$S$・和・積・大小を、$\mathbb N$ の上では通常どおり、$a$ が絡むところでは $Sa=a$、和は $a$、積は $0$ を含めば $0$ でなければ $a$、$x< a$(すべての $x$)と定めた構造は $\mathsf Q$ のモデルで、$a$ は非標準元である(OLT26 Example 26.21、pp. 402–403)。台集合を $\mathbb N$ に取り直す($a$ を $0$ に、$n$ を $n+1$ に送る)と、演算はすべて場合分けで計算でき、大小も決定できる。したがって、$\mathsf Q$ には計算可能な超準モデルがある。

順序だけなら計算可能

$\mathcal M$ を $\mathsf{PA}$ の可算な超準モデルとすると、$(\mathcal M,<)$ は $\mathbb N$ のあとに $\mathbb Q\times\mathbb Z$ を辞書式順序で並べた順序と同型である(Peano算術 の系「可算な超準モデルの順序型」)。$\mathbb Q\times\mathbb Z$ の元は有理数と整数の組として自然数で符号化でき、辞書式順序は決定可能なので、この順序は計算可能に表示できる。後者 $S$ も、$\mathbb N$ の上では $n\mapsto n+1$、$(q,z)\mapsto(q,z+1)$ として計算可能である。Tennenbaum の定理は、ここに加法を加えると計算可能に表示できなくなることを述べている。

反例:条件を外すと成り立たないこと

主張外す条件例成り立たなくなること
thm-tb-main帰納法の公理図式($\mathsf{PA}$ を $\mathsf Q$ に弱める)ex-tb-q-model加法が計算可能に表示できないこと
thm-tb-main超準モデルである$\mathfrak N$加法が計算可能に表示できないこと
thm-tb-main表示を求めるのが加法順序 $<$ と後者 $S$(ex-tb-order)計算可能に表示できないこと
(F3) オーバースピル帰納法の公理図式ex-tb-q-model の構造と、論理式 $\lnot\,Sx=x$非標準元で成り立つこと
表の確かめを開く

1 行目:ex-tb-q-model で取り直した構造は加法が計算可能で、非標準元をもつ。$\mathsf{PA}$ を $\mathsf Q$ に弱めると結論が成り立たない。この構造では証明の (F3) が成り立たない(4 行目)。

2 行目:$\mathfrak N$ では $+$ はふつうの足し算で計算可能である。段 3 で非標準元 $c^*$ をとれないことが証明の止まる場所である。

3 行目:ex-tb-order による。

4 行目:その構造ではすべての標準元 $n$ で $S\underline n=\underline{n+1}\ne\underline n$ なので $\lnot\,S\underline n=\underline n$ が成り立つが、ただ 1 つの非標準元 $a$ では $Sa=a$ である。帰納法の公理があれば、Peano算術 の命題「オーバースピル」により、非標準元のどれかで成り立たなければならない。

補足

証明の要点.計算可能でない情報を、超準モデルの 1 つの元の「標準的な素数での割り切れ方」として書き込めることが核心である。この書き込みはオーバースピルによるもので、帰納法の公理図式を本質的に使う。書き込まれた集合は、$\mathcal M$ の外から見ると lem-tb-inseparable の 2 つの集合を分ける集合であり、計算可能にはなりえない。
不完全性定理との関係.$\mathsf{PA}$ に「$\mathsf{PA}$ は無矛盾である」の否定を加えた理論は、Gödelの不完全性定理 により無矛盾なので、Gödelの完全性定理 によりモデルをもつ。そのモデルでは $\mathfrak N$ で偽な文が成り立つので、$\mathfrak N$ と同型でなく、cor-tb-only-standard により計算可能ではない。モデルの存在は保証されても、その姿を計算可能な形で示すことはできない。
次数との関係.計算できなさの程度は Turing次数 で測れる。証明の段 4 は、$+^{\mathcal M}$($\mathbb N^2\to\mathbb N$ の関数のグラフを集合とみたもの)を神託とし、有限個の自然数を書き込んだ手順で $C'$ が計算できることを示している。よって $+^{\mathcal M}$ の次数は、$U'$ を含み $V'$ と交わらない集合のどれかの次数以上である。

参照箇所

  • OLT26 §26.6:Definition 26.20(p. 402、計算可能な構造)、Example 26.21(pp. 402–403、計算可能な $\mathsf Q$ の超準モデル)、Theorem 26.22(p. 403、Tennenbaum の定理。$\mathfrak N$ が $\mathsf{PA}$ の唯一の計算可能なモデルであること)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する