完全な理論

同義語：完全理論complete theory

概要

前提知識: 一階述語論理, 構造(モデル), Löwenheim–Skolemの定理

群の公理だけからは、「どの 2 元も可換である」という文は証明も否定もできない。整数の加法群では真で、3 次対称群では偽だからである。一方、1 つの構造 $M$ で真な文をすべて集めた理論は、どの文についても真偽を決めている。このように、言語のどの文についても、その文かその否定のどちらかが帰結として決まっている理論を 完全な理論（complete theory）という。完全な理論のモデルはどれも同じ文を満たし、理論は「モデルの間で一階論理の言葉では区別がつかない」ところまで構造を決めている。
この記事では、完全な理論を定義して同値な言い換えを証明し、Łoś–Vaught の判定法と量化記号消去を使って、無限集合の理論、捩れのない可除群の理論、代数閉体の理論などが完全であることを示す。さらに、決定可能な公理系をもつ完全な理論は決定可能であることを示し、完全でも決定可能でない理論の例を挙げる。
以下、$L$ は一階言語、$T$ は $L$ の文の集合とする。構造の台集合は空でない。$T\models\sigma$ は「$T$ のすべてのモデルで文 $\sigma$ が真」を表し（一階述語論理の記事の定義「モデル・妥当性・論理的帰結」）、$\operatorname{Cn}(T):=\{\sigma\mid T\models\sigma\}$ を $T$ の帰結の全体とする。$L$ 構造 $M$ で真な文の全体を $\operatorname{Th}(M)$ と書き、$M$ の理論という。同じ文を満たす構造は 初等同値 であるといい、$M\equiv N$ と書く。

定義

完全な理論

$L$ の文の集合 $T$ が完全（complete）であるとは、$T$ がモデルをもち、$L$ のどの文 $\sigma$ についても $T\models\sigma$ または $T\models\lnot\sigma$ が成り立つことをいう。

これは Löwenheim–Skolemの定理の記事の節「完全性の判定法」での定義と同じである。モデルをもつ $T$ では、$T\models\sigma$ と $T\models\lnot\sigma$ が同時に成り立つことはないので、完全な理論はどの文についても真偽をちょうど一方に決める。
Gödelの完全性定理により、$T\models\sigma$ は「$T$ から $\sigma$ が証明できる」（$T\vdash\sigma$）と同値であり、$T$ がモデルをもつことは $T$ が無矛盾であることと同値である。したがって、完全な理論とは「無矛盾で、どの文についても、その文かその否定が証明できる」理論といってもよい。この意味の完全性は理論の性質であり、証明体系が意味論に対して完全であるという Gödel の完全性定理の「完全」とは別の概念である（Gödelの完全性定理の記事の節「理論の完全性と不完全性定理」）。なお、矛盾した理論もすべての文を証明するので完全とよぶ流儀もある（OLT26 §36.6、p. 576）。この記事では、モデルをもつことを定義に含める。

同値な言い換え

完全性の同値な言い換え

$T$ がモデルをもつとき、次は同値である。

$T$ は完全である。
$T$ の任意の 2 つのモデルは初等同値である。
$T$ のあるモデル $M$ について $\operatorname{Cn}(T)=\operatorname{Th}(M)$ である。
どの文 $\sigma$ についても、$T\cup\{\sigma\}$ がモデルをもつなら $T\models\sigma$ である。
さらにこのとき、$T$ のすべてのモデル $M$ について $\operatorname{Cn}(T)=\operatorname{Th}(M)$ である。

1 ⇒ 2：$M,N$ を $T$ のモデル、$\sigma$ を文とする。$T\models\sigma$ なら $M,N$ はともに $\sigma$ を満たし、$T\models\lnot\sigma$ ならともに $\sigma$ を満たさない。よって $M\equiv N$。
2 ⇒ 3：$T$ のモデル $M$ を 1 つとる。$\operatorname{Cn}(T)\subset\operatorname{Th}(M)$ はつねに成り立つ。$\sigma\in\operatorname{Th}(M)$ なら、2 により $T$ のどのモデル $N$ も $M\equiv N$ なので $N\models\sigma$ であり、$\sigma\in\operatorname{Cn}(T)$ である。この議論は $M$ の選び方によらないので、最後の主張も示された。
3 ⇒ 1：文 $\sigma$ について、$M\models\sigma$ なら $\sigma\in\operatorname{Th}(M)=\operatorname{Cn}(T)$、そうでなければ $\lnot\sigma\in\operatorname{Th}(M)=\operatorname{Cn}(T)$ である。
1 ⇒ 4：$T\cup\{\sigma\}$ のモデル $N$ があるとする。$T\models\lnot\sigma$ なら $N\models\lnot\sigma$ となって矛盾するので、1 により $T\models\sigma$ である。
4 ⇒ 1：$T$ のモデル $M$ をとると、$M\models\sigma$ か $M\models\lnot\sigma$ のどちらかなので、$T\cup\{\sigma\}$ か $T\cup\{\lnot\sigma\}$ のどちらかはモデルをもつ。4 により $T\models\sigma$ か $T\models\lnot\sigma$ である。$\square$

3 から、構造の理論 $\operatorname{Th}(M)$ はつねに完全である（$\operatorname{Cn}(\operatorname{Th}(M))=\operatorname{Th}(M)$ だから）。4 は、$\operatorname{Cn}(T)$ が「モデルをもつ文の集合」の中で極大であることを言っている。
モデルをもつ理論 $T$ を含む完全な理論は、帰結の全体で比べれば、$T$ のモデル $M$ の理論 $\operatorname{Th}(M)$ のことにほかならない。$T\subset T'$ で $T'$ が完全なら、$T'$ のモデル $M$ は $T$ のモデルで、3 により $\operatorname{Cn}(T')=\operatorname{Th}(M)$ だからである。したがって、$T$ を完全な理論に広げる仕方は、帰結の全体で比べて、$T$ のモデルを初等同値で分類した類と 1 対 1 に対応する（$M\mapsto\operatorname{Th}(M)$）。$T$ が完全であるとは、この類がただ 1 つであることである。

例

完全な理論と完全でない理論

構造の理論．どの構造 $M$ についても $\operatorname{Th}(M)$ は完全である。自然数の構造の理論 $\operatorname{Th}(\mathbb{N},0,S,+,\cdot,<)$（真の算術）も完全である。
群の理論は完全でない．文 $\forall x\,\forall y\,(x\cdot y=y\cdot x)$ は $(\mathbb{Z},+)$ で真、3 次対称群で偽なので、群の公理はこの文もその否定も帰結としない。
稠密な全順序．端点のない稠密な全順序の理論 DLO は完全である（量化記号消去の記事の系「DLO の完全性と定義可能集合」、Löwenheim–Skolemの定理の記事の例「稠密な線形順序と代数閉体」）。とくに $(\mathbb{Q},<)\equiv(\mathbb{R},<)$ である。
代数閉体．標数を $p$（素数または $0$）に定めた代数閉体の理論 $\mathrm{ACF}_p$ は完全である（同じ 2 つの記事）。標数を定めない ACF は完全でない。文 $1+1=0$ は $\overline{\mathbb{F}_2}$ で真、$\mathbb{C}$ で偽だからである。ACF の完全な拡大は、標数ごとの $\mathrm{ACF}_p$ でちょうど尽くされる。
実閉体．順序環の言語の実閉体の理論 RCF は完全である。整数係数の文はある実閉体で真ならすべての実閉体で真であるという Tarski–Seidenberg の原理（Tarski–Seidenbergの定理の記事が挙げる BPR16 Theorem 2.98・2.99、p. 81。この記事では証明しない）は、この言語の文についての完全性そのものだからである。

4 の最後の主張は、完全な拡大についての前の節の注意から分かる。代数閉体 $K$ の理論 $\operatorname{Th}(K)$ は $K$ の標数 $p$ の $\mathrm{ACF}_p$ を含み、$\mathrm{ACF}_p$ が完全なので $\operatorname{Cn}(\mathrm{ACF}_p)=\operatorname{Th}(K)$ だからである。

完全性を示す方法

理論が完全であることを示す代表的な方法は 2 つある。

範疇性による方法．モデルをもち、有限のモデルをもたず、ある基数 $\kappa\ge\lvert L\rvert+\aleph_0$ について濃度 $\kappa$ のモデルがどれも同型なら、理論は完全である（Löwenheim–Skolemの定理の記事の定理「Łoś–Vaught の判定法」）。
量化記号消去による方法．理論が量化記号消去をもち、どの 2 つのモデルも同じ量化記号のない文を満たすなら、理論は完全である（量化記号消去の記事の命題「量化記号消去の帰結」の 2）。
範疇性による方法の例を 2 つ挙げる。

無限集合の理論

記号のない言語（等号だけ）で、$n\ge2$ について
$$ \sigma_{\ge n}:=\exists x_1\cdots\exists x_n\bigwedge_{1\le i< j\le n}\lnot(x_i=x_j) $$
（相異なる元が $n$ 個以上ある）とおき、$I_\infty:=\{\sigma_{\ge n}\mid n\ge2\}$ とする。$I_\infty$ は完全である。
実際、$I_\infty$ のモデルはちょうど無限集合であり、有限のモデルはなく、$I_\infty$ はすべての無限基数で範疇的である（カテゴリー性の記事の例「無限集合の理論」）。言語は可算だから Łoś–Vaught の判定法により完全である。一方、$I_\infty$ を有限個の文で置き換えることはできない。有限個の文の集合 $\Sigma$ が $\operatorname{Cn}(\Sigma)=\operatorname{Cn}(I_\infty)$ を満たしたとすると、コンパクト性定理(一階論理) の記事の系「帰結の有限性」により $\Sigma$ の各文は $I_\infty$ の有限個の文から、したがってある 1 つの $\sigma_{\ge N}$ から従う。すると $N$ 元集合は $\Sigma$ のモデルだが、$\sigma_{\ge N+1}\in\operatorname{Cn}(\Sigma)$ を満たさず、矛盾する。

次の例では、範疇性が非可算な濃度でだけ成り立つ。

捩れのない可除群の理論の完全性

アーベル群の言語 $\{+,-,0\}$ で、アーベル群の公理に次の文を加えた理論を $\mathrm{DAG}^\ast$ とする。

（可除）$n\ge1$ ごとに $\forall x\,\exists y\,(\underbrace{y+\cdots+y}_{n}=x)$。
（捩れがない）$n\ge1$ ごとに $\forall x\,(\underbrace{x+\cdots+x}_{n}=0\to x=0)$。
（自明でない）$\exists x\,\lnot(x=0)$。
$\mathrm{DAG}^\ast$ は完全である。とくに $(\mathbb{Q},+)\equiv(\mathbb{R},+)\equiv(\mathbb{Q}^2,+)$ である。

$\mathrm{DAG}^\ast$ のモデルは、自明でない捩れのない可除群である。
段 1（モデルは $\mathbb{Q}$ 上のベクトル空間）． 可除群の記事の命題「捩れのない可除群と有理数体上のベクトル空間」により、モデル $D$ は整数倍を延長する $\mathbb{Q}$ 上のベクトル空間の構造をただ 1 つもつ。$D\ne0$ なので、これは $\{0\}$ でない $\mathbb{Q}$ 上のベクトル空間である。
段 2（非可算な濃度での範疇性）． $\kappa$ を非可算な基数とし、$D_1,D_2$ を濃度 $\kappa$ のモデルとする。段 1 により、$D_1,D_2$ は $\{0\}$ でない $\mathbb{Q}$ 上のベクトル空間、すなわちカテゴリー性の記事の理論 $T_{\mathbb{Q}}$（言語 $\{0,+\}\cup\{\lambda_q\mid q\in\mathbb{Q}\}$ の、$\{0\}$ でない $\mathbb{Q}$ 上のベクトル空間の理論）の濃度 $\kappa$ のモデルになる。同記事の定理「有理数体上のベクトル空間の理論の範疇性」により $T_{\mathbb{Q}}$ はすべての非可算基数で範疇的なので、全単射な $\mathbb{Q}$ 線形写像 $h\colon D_1\to D_2$ がある。$h$ は加法と $0$ を保ち、したがって $-$ も保つので、群の言語の構造としての同型である。よって $\mathrm{DAG}^\ast$ は $\kappa$-範疇的である。
段 3（有限のモデルがないこと）． $a\ne0$ を含むモデルで、$m< n$ について $na=ma$ なら $(n-m)a=0$ で捩れがないことに反する。よって $a,2a,3a,\dots$ は相異なり、モデルは無限である。
言語は可算なので、Łoś–Vaught の判定法により $\mathrm{DAG}^\ast$ は完全である。$\square$

$\mathrm{DAG}^\ast$ は $\aleph_0$-範疇的ではない。$\mathbb{Q}$ と $\mathbb{Q}^2$ はどちらも可算なモデルだが、群の同型は $\mathbb{Q}$ 線形写像なので（可除群の記事の同じ命題の後の注意）、群として同型なら $T_{\mathbb{Q}}$ のモデルとしても同型になり、カテゴリー性の記事の同じ定理（$\aleph_0$-範疇的でないこと）の証明が示すとおり、次元 $1$ と $2$ の違いから同型でない。範疇性は 1 つの濃度で成り立てば十分であり、どの濃度で成り立つかは理論によって違う。

完全性と決定可能性

この節では $L$ は可算な言語とし、文に自然数の番号（Gödel 数）$\ulcorner\sigma\urcorner$ を、文であるかどうかの判定や否定 $\sigma\mapsto\lnot\sigma$ が番号の上で計算できるように付けておく。自然数の集合 $A$ が 決定可能 であるとは、その特性関数が Turing 計算可能であることをいい、半決定可能（計算可能枚挙）であるとは、ある Turing 計算可能な部分関数の定義域であることをいう（停止問題）。文の集合は、番号の集合が決定可能（半決定可能）であるとき、そうよぶ。

決定可能な公理系をもつ完全な理論は決定可能

$T$ が決定可能な文の集合で、完全であるとする。このとき $\operatorname{Cn}(T)$ は決定可能である。すなわち、文 $\sigma$ を与えられて $T\models\sigma$ かどうかを判定する機械的な手順がある。

次の 3 つの事実を使う。いずれもこの記事では証明しない。

(a) 決定可能な文の集合 $T$ について、$\operatorname{Cn}(T)$ は半決定可能である。Gödelの完全性定理により $T\models\sigma$ は $T$ から $\sigma$ が証明できることと同値であり、証明を順に数え上げられるからである（OLT26 Lemma 36.7、p. 576）。
(b) 半決定可能な集合の和集合は半決定可能であり、計算可能な全域関数による半決定可能な集合の逆像は半決定可能である（和集合について OLT26 Theorem 30.13、p. 458。逆像は、定義域を与える部分関数に全域関数を合成すればよい）。
(c) 自然数の集合 $A$ が決定可能であることは、$A$ と補集合 $\mathbb{N}\setminus A$ がともに半決定可能であることと同値である（OLT26 Theorem 30.14、p. 460）。
$C:=\{\ulcorner\sigma\urcorner\mid T\models\sigma\}$ とおくと、(a) により $C$ は半決定可能である。文の番号の全体を $\mathrm{Sent}$ とすると、これは決定可能で、$C\subset\mathrm{Sent}$ であり、$\mathbb{N}\setminus C$ は $\mathbb{N}\setminus\mathrm{Sent}$ と $\mathrm{Sent}\setminus C$ の和である。$\mathbb{N}\setminus\mathrm{Sent}$ は決定可能なので、(c) により半決定可能である。
否定を $\mathbb{N}$ 全体の関数に延ばして
$$ \operatorname{neg}(n):=\begin{cases}\ulcorner\lnot\sigma\urcorner & (n=\ulcorner\sigma\urcorner\in\mathrm{Sent}),\\ n & (n\notin\mathrm{Sent})\end{cases} $$
とおく。$\mathrm{Sent}$ が決定可能で、否定が番号の上で計算できるので、$\operatorname{neg}$ は計算可能な全域関数である。$T$ は完全でモデルをもつので、文 $\sigma$ について $T\not\models\sigma\iff T\models\lnot\sigma$ である。よって $n=\ulcorner\sigma\urcorner\in\mathrm{Sent}$ なら $n\notin C\iff\operatorname{neg}(n)\in C$ であり、$n\notin\mathrm{Sent}$ なら $\operatorname{neg}(n)=n\notin\mathrm{Sent}$ なので $\operatorname{neg}(n)\notin C$ である。したがって
$$ \mathrm{Sent}\setminus C=\{\ulcorner\sigma\urcorner\mid T\models\lnot\sigma\}=\operatorname{neg}^{-1}(C) $$
であり、(b) の逆像の主張により半決定可能である。(b) の和集合の主張により $\mathbb{N}\setminus C=(\mathbb{N}\setminus\mathrm{Sent})\cup\operatorname{neg}^{-1}(C)$ も半決定可能であり、(c) により $C$ は決定可能である。$\square$

証明の考え方は単純である。文 $\sigma$ が与えられたら、$T$ からの証明を 1 つずつ数え上げ、$\sigma$ の証明か $\lnot\sigma$ の証明が見つかるまで待つ。完全性により、どちらかは必ず見つかる。無矛盾性により、見つかったほうが答えである。完全でない理論では、どちらも見つからずに待ち続けることがある。

決定可能な理論の例

DLO、$\mathrm{ACF}_p$（$p$ は素数または $0$）、RCF、$I_\infty$、$\mathrm{DAG}^\ast$ の帰結の全体は、それぞれ決定可能である。

どの理論も完全であり（ex-ct-examples、ex-ct-infinite-sets、thm-ct-dag）、公理は有限個の文と、$n$ や $m$ で番号付けた文の列（「$n$ 個以上の元がある」「$m$ 次の多項式は根をもつ」「$n$ 倍で割れる」など）からなる。与えられた文がこの列のどれかに一致するかは機械的に確かめられるので、公理の集合は決定可能である。thm-ct-decidable による。$\square$

RCF の場合は、整数係数の文が実数体で成り立つかを判定する手順があるという Tarski の結果にあたる（Tarski–Seidenbergの定理の記事の節「系」の末尾の箇条書きのうち、Tarski の量化記号消去の手順と判定の算法を述べる項）。
逆向きは成り立たない。完全な理論が決定可能な公理系をもつとは限らない。

完全だが決定可能でない理論

特性関数が Turing 計算可能でない集合 $X\subset\mathbb{N}$ がある（Turing機械の記事の定理「Turing 計算可能でない関数の存在」の 1 により Turing 計算可能な関数は可算個しかなく、$\{0,1\}$ に値をとる関数は非可算個あるため）。定数記号 $0$、1 項関数記号 $s$、1 項関係記号 $P$ の言語で、構造 $\mathcal N_X:=(\mathbb{N},0,n\mapsto n+1,X)$ を考え、$T_X:=\operatorname{Th}(\mathcal N_X)$ とおく。
$T_X$ は構造の理論なので完全である。一方、$n$ に文 $\pi_n:=P(s(s(\cdots s(0)\cdots)))$（$s$ を $n$ 回）の番号を対応させる関数は計算可能で、$n\in X\iff\mathcal N_X\models\pi_n\iff\ulcorner\pi_n\urcorner\in\{\ulcorner\sigma\urcorner\mid T_X\models\sigma\}$ である。$\operatorname{Cn}(T_X)$ が決定可能なら、$X$ の特性関数は計算可能な関数の合成として計算可能になり、$X$ の選び方に反する。よって $\operatorname{Cn}(T_X)$ は決定可能でなく、thm-ct-decidable の対偶により、$T_X$ と同じ帰結をもつ決定可能な文の集合は存在しない。

自然数の構造の理論、すなわち真の算術 $\operatorname{Th}(\mathbb{N},0,S,+,\cdot,<)$ も完全だが決定可能でない（OLT26 Corollary 36.6、p. 576）。そこでは上の例のように計算できない集合を言語に入れる必要はなく、加法と乗法だけで十分である。さらに、算術の弱い公理系 Q を含む無矛盾で決定可能な文の集合は完全でない（同 Theorem 36.9、p. 576）。これが Gödelの不完全性定理の一つの形である。この記事では証明しない。

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

外す条件	反例	成り立たなくなること
捩れがない（thm-ct-dag）	自明でない可除アーベル群の理論	完全性
可除（thm-ct-dag）	自明でない捩れのないアーベル群の理論	完全性
自明でない（thm-ct-dag）	捩れのない可除アーベル群の理論	完全性
決定可能な公理系（thm-ct-decidable）	$T_X=\operatorname{Th}(\mathbb{N},0,s,X)$	決定可能性

反例の確かめ

1 行目：$(\mathbb{Q}/\mathbb{Z},+)$ と $(\mathbb{Q},+)$ はどちらも自明でない可除アーベル群である。文 $\exists x\,(\lnot(x=0)\land x+x=0)$ は $\mathbb{Q}/\mathbb{Z}$ で真（$x=1/2+\mathbb{Z}$）、$\mathbb{Q}$ で偽なので、理論はこの文もその否定も帰結としない。
2 行目：$(\mathbb{Z},+)$ と $(\mathbb{Q},+)$ はどちらも自明でない捩れのないアーベル群である。文 $\forall x\,\exists y\,(y+y=x)$ は $\mathbb{Q}$ で真、$\mathbb{Z}$ で偽（$x=1$）である。
3 行目：自明な群 $\{0\}$ は捩れがなく可除である。文 $\exists x\,\lnot(x=0)$ は $\mathbb{Q}$ で真、$\{0\}$ で偽である。
4 行目は ex-ct-undecidable である。

1〜3 行目の理論では、Łoś–Vaught の判定法の仮定が崩れている。1 行目の理論は非可算な濃度でも範疇的でない（非可算な基数 $\kappa$ について、$\mathbb{Q}^{(\kappa)}$ を、$\kappa$ を添字とする $\mathbb{Q}$ の元の族で有限個を除いて $0$ のものの全体とする。その濃度は $\kappa$ である（カテゴリー性の補題「有理数体上のベクトル空間の濃度」）。$\mathbb{Q}/\mathbb{Z}\oplus\mathbb{Q}^{(\kappa)}$ と $\mathbb{Q}^{(\kappa)}$ は濃度 $\kappa$ で、前者だけが位数 $2$ の元をもつ）。2 行目の理論も同様である（$\mathbb{Z}\oplus\mathbb{Q}^{(\kappa)}$ と $\mathbb{Q}^{(\kappa)}$ は濃度 $\kappa$ で、後者だけが可除）。3 行目の理論は 1 元のモデルをもつ。