第IV章 演習問題 [13]

第1段. まず偶数全体の集合 \(E=\{\,n+n\,:\,n\in\omega\,\}\) が構造 \((\omega,{<})\) 上で一階の式で定義できないことを証明する. 仮に, 順序構造の言語の式 \(\varphi\) によって集合 \(E\) が \((\omega,{<})\) 上で定義可能だったとしよう: \[ x\in E\;\leftrightarrow\;(\omega,{<})\models\varphi(x)\qquad(x\in\omega). \]構造 \((\omega,{<})\) の初等理論, すなわち順序構造の言語の一階の閉じた文のうち \((\omega,{<})\) で真であるもの全体を \(\mathrm{Th}(\omega,{<})\) と書く. 以下に証明するとおり, この \(\mathrm{Th}(\omega,{<})\) は \((\omega,{<})\) と同型でないモデル(超準モデル)をもつ. ひとつの超準モデル \(\mathfrak{A}=(A,{<}_A)\) を考える. \(\mathfrak{A}\) の標準的でない要素, すなわち \(0,1,2,\ldots\) のどれにも対応しない要素のひとつを \(a\) としよう. \(\mathfrak{A}\) は全順序だが, 標準的な要素 \(0^{\mathfrak{A}}\), \(1^{\mathfrak{A}}\), \(2^{\mathfrak{A}}\) 等々はすべて有限の要素であり, また有限の要素はすべて標準的であるから, \(a\) は “無限大の要素” である. \(A\) の要素 \(x\) と \(a\) との間の区間が有限集合であるとき \(h(x)\) を \(x\) の “次の要素” とし, \(x\) と \(a\) の間の区間が無限集合であるときは \(h(x)=x\) と定めて関数 \(h:A\to A\) を作る. この \(h\) は順序構造 \(\mathfrak{A}\) の自己同型写像であるから, \(A\) のすべての要素 \(x\) について \[ \mathfrak{A}\models\varphi(x)\,\leftrightarrow\,\varphi(h(x))\tag{1} \]である. しかしながら, \((\omega,{<})\) 上では \(x\) とその次の要素 \(S(x)\) との間に \[ \forall x\big(\,\varphi(x)\,\leftrightarrow\,\neg\varphi(S(x))\big) \]が成立しており, \(\mathfrak{A}\) でもこの式は真である. とくに \[ \mathfrak{A}\models\varphi(a)\,\leftrightarrow\,\neg\varphi(h(a))\tag{2} \]となるが, これは(1)と矛盾する. したがって, \((\omega,{<})\) において偶数全体の集合を一階の式で定義することはできない.

第2段. \(\mathrm{Th}(\omega,{<})\) の超準モデルの存在証明. 順序構造の言語に一つの新しい定数記号 \(c\) を追加し, 拡大された言語の文 \[ \exists x_0\exists x_1\cdots\exists x_n\Big(\;\bigwedge_{i<n}\big(\, x_i<x_{i+1}\,\big)\land x_n<c\;\Big) \]を \(\psi_n\) と書こう. この式は内容的には \(n<c\) を意味している. 標準モデル \((\omega,{<})\) で \(c=n+1\) と解釈すれば \(\mathrm{Th}(\omega,{<})\cup\{\psi_0,\ldots,\psi_n\}\) のモデルが得られるから, コンパクト性定理により \(\mathrm{Th}(\omega,{<})\cup\{\,\psi_n\,:\,n\in\omega\,\}\) もモデルをもつ. この文の集合の任意のモデル \(\mathfrak{A}\) において, \(c^{\mathfrak{A}}\) は \(0^{\mathfrak{A}}\), \(1^{\mathfrak{A}}\), \(2^{\mathfrak{A}}\) 等々のどれよりも大きい非標準的な要素になっている.

第3段. つぎに関数 \(f(n)=n+n\) は集合論において \(\mathit\Delta_0\) 式によっては定義されないことを証明する. 関数 \(f\) を定義する \(\mathit\Delta_0\) 式 \(\varphi(x,y)\) があったとすると, 偶数全体の集合 \(E\) は, \[ y\in E\;\leftrightarrow\;y\in\omega\land\big(y=0\lor \exists x\in y\,\varphi(x,y)\big) \tag{3} \]と定義できることになる. \(\mathit\Delta_0\) 式は任意の推移的クラスに対して絶対的であるので, \[ E=\Big\{\,y\in\omega\,:\,\big(y=0\lor \exists x\in y\,\varphi(x,y)\big)^{(\omega,{\in})}\,\Big\}\tag{4} \]である. ところが, 集合論の言語の式は \(\in\) を \(<\) に読み替えることで自然に順序構造の式に翻訳され, その翻訳を介して式(4)は\((\omega,{<})\) において集合 \(E\) を定義してしまう. これは第1段の結論と矛盾することになる.

第4段. 最後に, 関数 \(f(n)=n+n\) がふたつの \(\mathit\Delta_0\) 関数の合成関数として定義できることを証明する. あきらかに \(f(n)=n\cdot 2\) なので, \(f\) は再帰的定義 \[ \begin{gather} f(0)=0,\\ f(S(n))=S(S(f(n))) \end{gather} \] によって定義できる. そこで, 《\(\,x\) は自然数, \(g\) は関数で \(\mathrm{dom}(g)=x+1\) であり, \(\mathrm{dom}(g)\) の各要素 \(y\) について \(y=0\land g(y)=0\) あるいは \(y\neq0\land g(y)=S(S(g(y-1)))\) が成立する》という内容をあらわす式 \(\theta(x,g)\) を用いれば, \[ \forall n\in\omega\exists !g\;\theta(x,g) \] かつ \[ \theta(x,g)\,\rightarrow\,g(x)=x+x \] となる. そこで, \(\theta(x,g)\) のあらわす関数 \(x\mapsto g\) と, 関数の値を返す \(\langle x,g\rangle\mapsto g(x)\) という関数 \(\mathrm{Eval}\) との合成で, 関数 \(f(n)=n+n\) を定義できる. ここで \(\mathrm{Eval}\) が \(\mathit\Delta_0\) 関数であることは前の演習問題[12]の(g)で証明したので, あとは \(\theta(x,g)\) がなんらかの \(\mathit\Delta_0\) 式と同値であることがわかればよい. 演習問題[12]で導入した記号を使って論じる. まず 《\(\,x\) は自然数である》 は \(x\) が後続型順序数であり, \(x\) のゼロでない要素もすべて後続型順序数である, と書けるので \(\mathit\Delta_0\) である. 《\(\,g\) は関数である》 は演習問題[12]で証明したとおり \(\mathit\Delta_0\) である. \(\mathrm{dom}(g)=x+1\) は \[ x\in \mathrm{dom}(g)\land x\subset \mathrm{dom}(g)\land \forall y\in\mathrm{dom}(g)\big(\,y=x\lor y\in x\,\big) \]と書けるが, \(y\in\mathrm{dom}(g)\) が \[ \exists w\in g\Big(\,(w)_0=y\land \forall w'\in g\,\big(\,(w')_0=y\,\rightarrow\,(w')_1=(w)_1\,\big)\,\Big) \] と \(\mathit\Delta_0\) で書けることと, 量化 \(\forall y\in\mathrm{dom}(g)(\ldots)\) が \[ \forall v_1\in g\forall v_2\in v_1\forall y\in v_2\big(\,y\in\mathrm{dom}(g)\,\rightarrow\,\ldots\,\big) \]と書けるので, \(\mathrm{dom}(g)=x+1\) が \(\mathit\Delta_0\) であるとわかる. 最後に \(g(y)=S(S(g(y-1)))\) は \(z=y-1\), \(g(y)=u\), \(g(z)=v\), \(S(v)=w\) として \[ \exists u\in\in\in g\Big(\;u=g(y)\land \exists z\in y\exists v\in\in\in g\big(\, y=S(z)\land v=g(z)\land \exists w\in u(\,u=S(w)\land w=S(v)\,)\,\big)\;\Big) \]と書ける. ただし, \(\exists u\in\in\in g(\ldots)\) と書いたのは, 他所で使われていない変数 \(u_1\) と \(u_2\) によって \[ \exists u_1\in g\exists u_2\in u_1\exists u\in u_2(\ldots) \]と書かれている式を略記するものとする. \(\exists v\in\in\in g\) についても同様. 以上により, \(\theta(x,g)\) と同値な \(\mathit\Delta_0\) 式を書き下せるとわかった.