理論とモデル | 数理論理

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}$ が台集合上の狭義線型順序であることは同値である。特に $(\Z,<)$ は $T_{\mathrm{lo}}$ のモデルである。

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

$\Sigma$ -理論 $T$ について、ある $\Sigma$ -文 $\sigma$ に対して $T\models\sigma$ かつ $T\models\neg\sigma$ であることと、 $T$ が充足不能であることが同値であることを示せ。また、 $T$ が充足可能であるとき、 $T$ が完全であることと、 $T$ の任意の二つのモデル $\mathcal M,\mathcal N$ と任意の $\Sigma$ -文 $\sigma$ について $\mathcal M\models\sigma\iff\mathcal N\models\sigma$ が成り立つこととが同値であることを示せ。
二項関係記号 $<$ だけをもつシグネチャの構造 $(\N,<)$ と $(\Z,<)$ を考え、 $\iota:\N\to\Z$ を包含写像とする。 $\iota$ は単射であり、定義 2.1 条件 (b)を満たすことを確かめよ。さらに、文 $\sigma=\exists x\forall y\,\neg(y<x)$ について $(\N,<)\models\sigma$ かつ $(\Z,<)\not\models\sigma$ であることを示し、定理 2.3の結論が全射でない $\iota$ については成り立たないことを結論せよ。
群理論が完全でないことを示す二つのモデルと一つの文を挙げよ。
新しい元 $\infty\notin\N$ を取り、台集合 $M=\N\cup\{\infty\}$ 上で、 $\N$ の元どうしの $S,+,\cdot$ は $\mathcal N$ と同じとし、さらに $S(\infty)=\infty$ 、 $x+\infty=\infty+x=\infty$ （ $x\in M$ ）、 $x\neq0$ ならば $x\cdot\infty=\infty\cdot x=\infty$ 、 $0\cdot\infty=\infty\cdot0=0$ と定めた $\Sigma_{\mathrm{ar}}$ -構造 $\mathcal M$ を考える。 $\mathcal M\models Q$ であることを示し、 $\mathcal M$ と $\mathcal N$ が同型でないことを示せ。

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

$T$ が充足不能ならば、注意 1.3により任意の文 $\sigma$ について $T\models\sigma$ かつ $T\models\neg\sigma$ である。逆に、ある文 $\sigma$ について $T\models\sigma$ かつ $T\models\neg\sigma$ とし、 $\mathcal M\in\operatorname{Mod}(T)$ が存在すると仮定する。 $\mathcal M\models\sigma$ かつ $\mathcal M\models\neg\sigma$ であり、文の真偽は割当てに依存しないので、否定の充足節により $\mathcal M\models\sigma$ と $\mathcal M\not\models\sigma$ が同時に成り立ち、矛盾する。よって $T$ は充足不能である。

$T$ を充足可能とする。 $T$ が完全であるとし、 $\mathcal M,\mathcal N\in\operatorname{Mod}(T)$ と文 $\sigma$ を取る。 $T\models\sigma$ ならば $\mathcal M\models\sigma$ かつ $\mathcal N\models\sigma$ である。 $T\models\neg\sigma$ ならば $\mathcal M\not\models\sigma$ かつ $\mathcal N\not\models\sigma$ である。いずれの場合も $\mathcal M\models\sigma\iff\mathcal N\models\sigma$ である。逆に、 $T$ の任意の二つのモデルが同じ文を満たすとする。 $T$ は充足可能であるから $\mathcal M_0\in\operatorname{Mod}(T)$ を一つ取る。文 $\sigma$ について $\mathcal M_0\models\sigma$ ならば、仮定により $T$ のすべてのモデルが $\sigma$ を満たすので $T\models\sigma$ である。 $\mathcal M_0\not\models\sigma$ ならば、 $T$ のすべてのモデル $\mathcal N$ について $\mathcal N\not\models\sigma$ 、すなわち $\mathcal N\models\neg\sigma$ であるから $T\models\neg\sigma$ である。よって $T$ は完全である。
包含写像は単射であり、 $a,b\in\N$ について $a<b$ であることと、 $a,b$ を整数とみなして $a<b$ であることは同値であるから、定義 2.1 条件 (b)が成り立つ。関数記号はないので定義 2.1 条件 (a)は条件を課さない。

$(\N,<)$ では、割当て $s$ を任意に取り $a=0$ とすると、任意の $b\in\N$ について $b<0$ ではないので $(\N,<),s[x\mapsto0]\models\forall y\,\neg(y<x)$ であり、 $(\N,<)\models\sigma$ である。 $(\Z,<)$ では、任意の $a\in\Z$ について $a-1<a$ であるから $(\Z,<),s[x\mapsto a][y\mapsto a-1]\models y<x$ であり、 $(\Z,<),s[x\mapsto a]\not\models\forall y\,\neg(y<x)$ である。 $a$ は任意であるから $(\Z,<)\not\models\sigma$ である。

とくに、 $s(x)=0$ を満たす割当て $s:\mathrm{Var}\to\N$ について $(\N,<),s\models\forall y\,\neg(y<x)$ であるが $(\Z,<),\iota\circ s\not\models\forall y\,\neg(y<x)$ である。全称量化の節は $\Z$ のすべての元を調べ、 $\iota$ の像に入らない $-1$ がこの論理式の反例を与える。したがって、定理 2.3の同値は、二つの条件を満たす単射であっても全射でない写像については成り立たない。
整数加法群と三次対称群を取り、可換性の文 $\forall x\forall y\,(x\cdot y=y\cdot x)$ を用いる。
$Q$ の七つの文を順に確かめる。 $\N$ の元どうしの等式と存在主張は命題 5.3の証明と同じであるから、 $\infty$ を含む場合だけを調べる。

第一の文について、 $S(\infty)=\infty\neq0$ である。第二の文について、 $\N$ 上の $S$ は単射であり値は $\N$ に属するので、 $S(x)=S(\infty)=\infty$ ならば $x=\infty$ である。第三の文について、 $\infty\neq0$ であり $\infty=S(\infty)$ である。第四の文について、 $\infty+0=\infty$ である。第五の文について、 $x=\infty$ または $y=\infty$ ならば、 $x+S(y)$ と $S(x+y)$ はともに $\infty$ である。実際、 $y=\infty$ ならば $S(y)=\infty$ であり、 $x+y=\infty$ ならば $S(x+y)=\infty$ である。第六の文について、 $\infty\cdot0=0$ である。第七の文 $x\cdot S(y)=(x\cdot y)+x$ について場合を分ける。 $x=0$ ならば両辺は $0$ である。実際、 $0\cdot S(y)=0$ であり、 $0\cdot y=0$ と $0+0=0$ から右辺も $0$ である。 $x\neq0$ かつ $y=\infty$ ならば、左辺は $x\cdot\infty=\infty$ 、右辺は $\infty+x=\infty$ である。 $x=\infty$ かつ $y\in\N$ ならば、 $S(y)\neq0$ であるから左辺は $\infty$ であり、右辺は $(\infty\cdot y)+\infty=\infty$ である。以上により $\mathcal M\models Q$ である。

文 $\tau=\exists x\,(Sx=x)$ を考える。 $\mathcal M$ では $x$ に $\infty$ を割り当てると $S(\infty)=\infty$ であるから $\mathcal M\models\tau$ である。 $\mathcal N$ では任意の $n\in\N$ について $n+1\neq n$ であるから $\mathcal N\not\models\tau$ である。 $\mathcal M$ と $\mathcal N$ が同型ならば系 2.4により両者は同じ文を満たすので、 $\mathcal M$ と $\mathcal N$ は同型でない。したがって $\mathcal N\models Q$ であっても、 $Q$ のモデルは $\mathcal N$ と同型なものに限らない。

▨

§E19.8理論とモデル

1 理論とモデル

2 構造の同型

3 群の公理化

4 線型順序の公理化

5 算術の公理化

6 演習

参考文献

前提記事