投稿者: 初等拡大モデルとは
簡単に言うと初等拡大とは, ２つの構造\(\mathcal{M}, \mathcal{N}\)の大きい方が小さい方の満たす性質を全部満たすときの大きい方をいいます.
初等拡大の例を構成しようとしたら意外に証明が大変だったのでまとめておきます.
ここでは, \(L = \{<\}\)としたとき\(\mathbb{R}\)が\(\mathbb{Q}\)の初等拡大になることを示します. つまり,
\(\langle \mathbb{Q}; < \rangle \prec \langle \mathbb{R}; < \rangle\).
簡単な例を考えてみることはやはり勉強になりますね.
初等拡大モデルの定義
言語\(L\)について２つの\(L\)-構造を\(\mathcal{M}, \mathcal{N}\)とし, \(\mathcal{M} \subset \mathcal{N}\)とする. このとき, 任意の\(L(\mathcal{M})\)-閉論理式\(\varphi\)について,
\( \mathcal{M} \vDash \varphi \iff \mathcal{N} \vDash \varphi \),
となるとき, \(\mathcal{M} \prec \mathcal{N}\)と表し\(\mathcal{N}\)は\(\mathcal{M}\)の初等拡大であるという.
初等拡大になるための必要十分条件
この補題を自分で探したので時間がかかりました. あとから見返したら新井数学基礎論にはさらっと書いてあって「なんだー」と思いましたが．
自分でやったことに価値があると言い聞かせて進みます.
\(L\)-構造\(\mathcal{M}, \mathcal{N}\)について,\(\mathcal{M} \subset \mathcal{N}\)とする. このとき, 次の３条件は同値.
(1) \(\mathcal{M} \prec \mathcal{N}\).
(2) 任意の\(L(\mathcal{M})\)-閉論理式\(\varphi\)について,\( \mathcal{M} \vDash \varphi \iff \mathcal{N} \vDash \varphi \).
(3) 自由変数を１つだけ持つ（その１つについては何度出現してもよい）任意の\(L(\mathcal{M})\)-論理式\(\varphi[x]\)について,
任意の\(a \in |\mathcal{M}|\)について\(\mathcal{N} \vDash \varphi[x := C_a] \Rightarrow \mathcal{N} \vDash \forall x \varphi. \)
(Proof)
(2)は(1)の定義であるから(1)\(\iff\)(2)は自明.
(2)\(\iff\)(3)を示す.
(\(\Rightarrow\))
(3)の対偶をとると,
\(\mathcal{N} \vDash \exists x (\lnot \varphi) \Rightarrow \) ある\(a \in |\mathcal{M}|\)について\(\mathcal{N} \vDash \lnot \varphi[x := C_a] \)
となるが, (2)より\(\mathcal{M} \vDash \exists x (\lnot \varphi)\)であるから\( \lnot \varphi\)の証拠として\(\mathcal{M}\)の元をとることができる. よって示された.
(\(\Leftarrow\))
\(\varphi\)が\(\lnot, \land, \lor, \rightarrow\)で分解できるときは, (3)を用いずに\(\varphi\)の長さに関する帰納法で\(\mathcal{M} \vDash \varphi \iff \mathcal{N} \vDash \varphi\)を示すことができる.
\(\varphi \equiv \exists y \psi\)の形のとき. \(\mathcal{M} \vDash \exists y \psi \Rightarrow \mathcal{N} \vDash \exists y \psi\)は自明であるから逆を示す. 逆の対偶をとると, \(\mathcal{M} \vDash \forall y \lnot \psi \Rightarrow \mathcal{N} \vDash \forall y \lnot \psi\)となるから, これは\(\varphi \equiv \forall y \psi\)の形のときに帰着する.
\(\varphi \equiv \forall y \psi\)の形のとき. \(\mathcal{N} \vDash \forall y \psi \Rightarrow \mathcal{M} \vDash \forall y \psi\)は自明であるから逆を示す. \(\mathcal{M} \vDash \forall y \psi\)とする. このとき\(\mathcal{M} \subset \mathcal{N}\)より, 任意の\(a \in |\mathcal{M}|\)について\(\mathcal{N} \vDash \varphi[x := C_a]\)となる. よって, (3)より\(\mathcal{N} \vDash \forall y \lnot \psi\)
□
具体例の構成
\(L = \{<\}\)としたとき\(\mathbb{R}\)が\(\mathbb{Q}\)の初等拡大になることを示します. \(\mathcal{Q} := \langle \mathbb{Q}; < \rangle, \mathcal{R} := \langle \mathbb{R}; < \rangle\)としましょう.
\(\varphi\)を自由変数を１つだけ持つ（その１つについては何度出現してもよい）任意の\(L(\mathcal{Q})\)-論理式\(\varphi[x]\)とする. このとき,
任意の\(a \in |\mathcal{Q}|\)について\(\mathcal{R} \vDash \varphi[x := C_a] \Rightarrow \mathcal{R} \vDash \forall x \varphi. \)
が成り立つ. すなわち, 補題より\(\langle \mathbb{Q}; < \rangle \prec \langle \mathbb{R}; < \rangle\).
(Proof)
(i) \(\varphi\)が量化子を持たないとき, \(\lnot, \land, \lor, \rightarrow\)による分解と\(\varphi\)の長さに関する帰納法示すことができる.
(ii) \(\varphi\)が量化子を持つとき.
量化子の個数による帰納法で示す. 量化子の個数が\(0\)のときは(i)より成り立つ. \(\varphi\)が量化子\(n-1\)個\((n > 0)\)持つときに主張が成り立つとして, \(n\)個でも成り立つことを示す.
①\(\varphi \equiv \forall y \psi\)の形のとき. 任意の\(a \in |\mathcal{Q}|\)について\(\mathcal{R} \vDash \varphi[x := C_a] \)とする. このとき, 任意の\(r \in |\mathcal{R}|\)について,
\(\mathcal{R} \vDash \psi[x := C_a, y := C_r],\)
が成り立つ. このとき右辺は\(L(\mathcal{R})\)-論理式であることに注意. 帰納法の仮定より\(\mathcal{R} \vDash (\forall x \psi)[y := C_r]\)が成り立つ. ここで\(r \in |\mathcal{R}|\)は任意でよかったから,
\(\mathcal{R} \vDash \forall y (\forall x \psi) \equiv \forall x (\forall y \psi) \equiv \forall x \varphi.\)
②\(\varphi \equiv \exists y \psi\)の形のとき. ①と同様. ただし, 最後の変形で\(\mathcal{R} \vDash \exists y (\forall x \psi) \Rightarrow \mathcal{R} \vDash \forall x (\exists y \psi)\)の逆は成り立たないことに注意.
□
最後に
難しいポイントは, 拡大してしまうと量化子の言及範囲が変化するところでした.
具体例を構成してみることは勉強になります.