理論とモデル | 数理論理 | 天游ヶ丘数理学院

1 理論とモデル

定義 1.1. $\Sigma$ を一階シグネチャとする。集合

T\subseteq\operatorname{Sent}(\Sigma)

を $\Sigma$ -理論 (Sigma-theory) という。 $\Sigma$ -構造 $\mathcal M$ が $T$ のモデル (model) であるとは、すべての $\sigma\in T$ について $\mathcal M\models\sigma$ が成り立つことをいう。この関係を $\mathcal M\models T$ と書き、モデル類を

\operatorname{Mod}(T)=\{\mathcal M:\mathcal M\text{ は }\Sigma\text{-構造であり }\mathcal M\models T\}

と書く。

定義 1.2. $\Sigma$ -理論 $T$ が充足可能 (satisfiable theory) であるとは、 $\operatorname{Mod}(T)\ne\varnothing$ であることをいう。 $\Sigma$ -文 $\sigma$ に対して

T\models\sigma

とは、すべての $\mathcal M\in\operatorname{Mod}(T)$ について $\mathcal M\models\sigma$ が成り立つことをいう。

注意 1.3 (空のモデル類からの帰結). $T$ が充足不能なら、 $\operatorname{Mod}(T)$ 上の全称量化は空虚に真となるため、すべての $\Sigma$ -文 $\sigma$ について $T\models\sigma$ である。完全性の定義には充足可能性を含めず、充足可能性が必要な定理では独立した仮定として明示する。

定義 1.4. $\Sigma$ -理論 $T$ が完全 (complete theory) であるとは、任意の $\Sigma$ -文 $\sigma$ について

T\models\sigma \quad\text{または}\quad T\models\neg\sigma

が成り立つことをいう。

注意 1.5 (充足不能な完全理論という退化例). 上の定義には充足可能性を含めない。例えば

T=\{\forall x\,x=x,\ \neg\forall x\,x=x\}

は充足不能であるため、任意の文 $\sigma$ について $T\models\sigma$ かつ $T\models\neg\sigma$ であり、定義上は完全である。充足可能で完全な理論だけを扱う定理では、充足可能性を定理の仮定として別に置かなければならない。

注意 1.6 (完全な理論と完全性定理). 完全な理論は、一つの理論 $T$ が各文の真偽を意味論的に決定するという性質である。命題論理や一階論理の完全性定理は、意味論的帰結と形式的導出が一致するという証明体系の性質である。二つの「完全性」は対象も量化も異なる。

例 1.7 (一つの構造の完全理論). $\Sigma$ -構造 $\mathcal M$ に対して

\operatorname{Th}(\mathcal M) =\{\sigma\in\operatorname{Sent}(\Sigma):\mathcal M\models\sigma\}

と置く。 $\mathcal M$ 自身がモデルであるため $\operatorname{Th}(\mathcal M)$ は充足可能である。任意の文 $\sigma$ について、 $\mathcal M\models\sigma$ または $\mathcal M\models\neg\sigma$ のちょうど一方が成り立つ。前者なら $\sigma\in\operatorname{Th}(\mathcal M)$ であり、 $\operatorname{Th}(\mathcal M)$ のすべてのモデルが公理 $\sigma$ を満たす。後者なら同じ理由で $\operatorname{Th}(\mathcal M)\models\neg\sigma$ である。したがって $\operatorname{Th}(\mathcal M)$ は完全である。

2 構造の同型

定義 2.1. $\mathcal M,\mathcal N$ を同じシグネチャ $\Sigma$ の構造とし、台集合をそれぞれ $M,N$ とする。全単射 $h:M\to N$ が同型 (isomorphism of structures) であるとは、次を満たすことをいう。

各 $f\in F_n$ と $a_1,\ldots,a_n\in M$ について $h(f^{\mathcal M}(a_1,\ldots,a_n)) =f^{\mathcal N}(h(a_1),\ldots,h(a_n)).$
各 $R\in R_n$ と $a_1,\ldots,a_n\in M$ について $(a_1,\ldots,a_n)\in R^{\mathcal M} \iff (h(a_1),\ldots,h(a_n))\in R^{\mathcal N}.$

$0$ 項関数の場合、条件 (a)は $h(c^{\mathcal M})=c^{\mathcal N}$ を意味する。

補題 2.2. $h:\mathcal M\cong\mathcal N$ を $\Sigma$ -構造の同型、 $s:\mathrm{Var}\to M$ を割当て、 $t$ を $\Sigma$ -項とする。このとき

h(\llbracket t\rrbracket_s^{\mathcal M}) =\llbracket t\rrbracket_{h\circ s}^{\mathcal N}

である。

証明. $t$ に関する構造帰納法を用いる。 $t=x$ の場合、両辺は $h(s(x))$ である。 $t=c$ の場合は同型の定数保存条件から従う。 $t=f(t_1,\ldots,t_n)$ の場合、帰納法の仮定と同型の関数保存条件により

\begin{aligned} h(\llbracket t\rrbracket_s^{\mathcal M}) &=h(f^{\mathcal M}(\llbracket t_1\rrbracket_s^{\mathcal M},\ldots, \llbracket t_n\rrbracket_s^{\mathcal M}))\\ &=f^{\mathcal N}(h(\llbracket t_1\rrbracket_s^{\mathcal M}),\ldots, h(\llbracket t_n\rrbracket_s^{\mathcal M}))\\ &=f^{\mathcal N}(\llbracket t_1\rrbracket_{h\circ s}^{\mathcal N},\ldots, \llbracket t_n\rrbracket_{h\circ s}^{\mathcal N})\\ &=\llbracket t\rrbracket_{h\circ s}^{\mathcal N} \end{aligned}

となる。▨

定理 2.3. $h:\mathcal M\cong\mathcal N$ を $\Sigma$ -構造の同型、 $s:\mathrm{Var}\to M$ を割当て、 $\varphi$ を $\Sigma$ -論理式とする。このとき

\mathcal M,s\models\varphi \quad\Longleftrightarrow\quad \mathcal N,h\circ s\models\varphi

である。

証明. $\varphi$ に関する構造帰納法を用いる。 $\varphi$ が $t=u$ なら、補題 2.2と $h$ の単射性により

\llbracket t\rrbracket_s^{\mathcal M}=\llbracket u\rrbracket_s^{\mathcal M} \iff \llbracket t\rrbracket_{h\circ s}^{\mathcal N} =\llbracket u\rrbracket_{h\circ s}^{\mathcal N}

である。 $\varphi=R(t_1,\ldots,t_n)$ なら、項評価の移送と同型の関係保存条件から同値を得る。否定と含意の場合は、充足関係の対応する節と帰納法の仮定から従う。

$\varphi=\forall x\,\psi$ とする。任意の $a\in M$ について

h\circ(s[x\mapsto a])=(h\circ s)[x\mapsto h(a)]

である。帰納法の仮定により

\mathcal M,s[x\mapsto a]\models\psi \iff \mathcal N,(h\circ s)[x\mapsto h(a)]\models\psi.

$h$ は全射でもあるから、 $a$ が $M$ 全体を動くと $h(a)$ は $N$ 全体を動く。両辺をそれぞれすべての $a\in M$ とすべての $b\in N$ について量化し、全称量化の充足節を適用すると

\mathcal M,s\models\forall x\,\psi \iff \mathcal N,h\circ s\models\forall x\,\psi

を得る。▨

系 2.4. $h:\mathcal M\cong\mathcal N$ を同型とする。任意の $\Sigma$ -文 $\sigma$ について

\mathcal M\models\sigma\iff\mathcal N\models\sigma

である。したがって、任意の $\Sigma$ -理論 $T$ について

\mathcal M\models T\iff\mathcal N\models T

である。

証明. 文の真偽は割当てに依存しない。任意の割当て $s:\mathrm{Var}\to M$ に定理 2.3を適用すれば文に関する同値を得る。理論に関する同値は、各 $\sigma\in T$ へ文の同値を適用して全称量化すれば従う。▨

3 群の公理化

定義 3.1. 群のシグネチャ (language of groups) $\Sigma_{\mathrm{grp}}$ は定数 $e$ 、単項関数 $i$ 、二項関数 $m$ をもつ。 $m(x,y)$ を $x\cdot y$ 、 $i(x)$ を $x^{-1}$ と略記する。

定義 3.2. $T_{\mathrm{grp}}$ (theory of groups) を次の三つの文からなる理論とする。

\begin{aligned} &\forall x\forall y\forall z\,((x\cdot y)\cdot z=x\cdot(y\cdot z)),\\ &\forall x\,(e\cdot x=x\land x\cdot e=x),\\ &\forall x\,(x^{-1}\cdot x=e\land x\cdot x^{-1}=e). \end{aligned}

命題 3.3. $\Sigma_{\mathrm{grp}}$ -構造 $\mathcal G$ が $T_{\mathrm{grp}}$ のモデルであることと、台集合 $G$ が演算 $m^{\mathcal G}$ 、単位元 $e^{\mathcal G}$ 、逆元写像 $i^{\mathcal G}$ によって群をなすことは同値である。

証明. $\mathcal G\models T_{\mathrm{grp}}$ なら、第一文の充足は結合律、第二文の充足は $e^{\mathcal G}$ が両側単位元であること、第三文の充足は $i^{\mathcal G}(a)$ が各 $a\in G$ の両側逆元であることを、それぞれすべての台集合の元について述べる。したがって $G$ は群である。

逆に $G$ が指定された演算で群なら、群の結合律、単位元律、逆元律を任意の $a,b,c\in G$ へ適用すると三つの文の Tarski 充足条件が成り立つ。よって $\mathcal G\models T_{\mathrm{grp}}$ である。▨

例 3.4 (群理論は完全ではない). 可換性を表す文

\sigma_{\mathrm{ab}}=\forall x\forall y\,(x\cdot y=y\cdot x)

を考える。整数加法群は $T_{\mathrm{grp}}\cup\{\sigma_{\mathrm{ab}}\}$ のモデルである。三次対称群 $S_3$ は $T_{\mathrm{grp}}$ のモデルであるが、例えば $(12)(23)\ne(23)(12)$ なので $\sigma_{\mathrm{ab}}$ を満たさない。したがって $T_{\mathrm{grp}}\not\models\sigma_{\mathrm{ab}}$ かつ $T_{\mathrm{grp}}\not\models\neg\sigma_{\mathrm{ab}}$ であり、群理論は完全ではない。

4 線型順序の公理化

定義 4.1. 二項関係記号 $<$ だけをもつシグネチャで、 $T_{\mathrm{lo}}$ (theory of strict linear orders) を次の文からなる理論とする。

\begin{aligned} &\forall x\,\neg(x<x),\\ &\forall x\forall y\forall z\,((x<y\land y<z)\to x<z),\\ &\forall x\forall y\,(x<y\lor x=y\lor y<x). \end{aligned}

命題 4.2. $<$ を二項関係として解釈する構造 $\mathcal A$ が $T_{\mathrm{lo}}$ のモデルであることと、 $<^{\mathcal A}$ が台集合上の狭義線型順序であることは同値である。特に $(\mathbb Z,<)$ は $T_{\mathrm{lo}}$ のモデルである。

証明. 三つの文は順に非反射性、推移性、任意の二元の比較可能性を述べる。これらは狭義線型順序の公理である。逆向きも定義を Tarski の充足節へ展開すれば直ちに従う。整数の通常の大小関係は $n<n$ を満たさず、 $m<n<n'$ なら $m<n'$ を満たし、任意の整数 $m,n$ について $m<n,m=n,n<m$ のいずれかを満たす。したがって $(\mathbb Z,<)\models T_{\mathrm{lo}}$ である。▨

5 算術の公理化

定義 5.1. 算術のシグネチャ (language of arithmetic) $\Sigma_{\mathrm{ar}}$ は定数 $0$ 、単項関数 $S$ 、二項関数 $+$ と $\cdot$ をもつ。

定義 5.2. Robinson 算術 $Q$ (Robinson arithmetic Q) を次の七つの文からなる $\Sigma_{\mathrm{ar}}$ -理論とする。

\begin{aligned} &\forall x\,\neg(Sx=0),\\ &\forall x\forall y\,(Sx=Sy\to x=y),\\ &\forall x\,(\neg(x=0)\to\exists y\,x=Sy),\\ &\forall x\,(x+0=x),\\ &\forall x\forall y\,(x+Sy=S(x+y)),\\ &\forall x\,(x\cdot0=0),\\ &\forall x\forall y\,(x\cdot Sy=(x\cdot y)+x). \end{aligned}

命題 5.3. $\mathbb N$ 上で $0,S,+,\cdot$ をそれぞれ零、 $S(n)=n+1$ 、通常の加法、通常の乗法として解釈した構造 $\mathcal N$ は $Q$ のモデルである。

証明. 任意の $m,n\in\mathbb N$ を取る。 $S(n)=n+1$ は $0$ でなく、 $m+1=n+1$ なら $m=n$ である。 $n\ne0$ なら自然数の離散性により $n=m+1=S(m)$ を満たす $m\in\mathbb N$ が存在する。加法について $n+0=n$ と $n+(m+1)=(n+m)+1$ が成り立つ。乗法について $n\cdot0=0$ と $n\cdot(m+1)=n\cdot m+n$ が成り立つ。各等式と存在主張は対応する七文の充足条件そのものであるから、 $\mathcal N\models Q$ である。▨

注意 5.4 (標準モデルと公理からの一意性). $\mathcal N\models Q$ であることは、 $Q$ のすべてのモデルが $\mathcal N$ と同型であることを意味しない。公理を満たす具体的な構造が存在することと、公理が同型を除いて構造を一意に特徴付けることは別の主張である。

6 演習

問題 6.1.

充足不能な理論が上の定義では完全となる理由と、充足可能性を必要とする定理では充足可能性を別の仮定として置く理由を、意味論的帰結の定義から説明せよ。
同型不変性の量化の場合に、 $h$ の単射性だけでなく全射性が必要となる理由を述べよ。
群理論が完全でないことを示す二つのモデルと一つの文を挙げよ。
$\mathcal N\models Q$ と「 $Q$ のモデルは $\mathcal N$ だけである」との相違を述べよ。

解答 (確認問題の解答).

モデルが存在しないと、すべてのモデルについての条件は空虚に成り立ち、任意の文 $\sigma$ について $T\models\sigma$ と $T\models\neg\sigma$ が同時に成り立つ。したがって $T$ は定義上完全である。しかし、完全性だけではモデルの存在を保証しないため、モデルを用いる定理では充足可能性を別の仮定として置かなければならない。
$\forall x$ は $N$ のすべての元を調べる。各 $b\in N$ を $h(a)$ と書くために全射性が必要である。
整数加法群と三次対称群を取り、可換性の文 $\forall x\forall y\,(x\cdot y=y\cdot x)$ を用いる。
前者は七つの公理が標準モデルで真であるという主張である。後者は全モデルの同型型を一意にするという、前者より強い主張である。

▨

理論は文の集合、モデルは文を同時に満たす構造、完全な理論はすべての文を意味論的に決定する理論である。同型不変性は、一階文が構造の要素名ではなく構造そのものの性質を述べることを保証する。

§E16.8理論とモデル

1 理論とモデル

2 構造の同型

3 群の公理化

4 線型順序の公理化

5 算術の公理化

6 演習

参考文献

前提記事