Definability lemma と Truth lemma

[PDF版 ]

ジェネリック拡大に関する性質を示す上で重要な役割を果すのがDefinability lemmaとTruth lemmaだった．今回は，モデルに言及しない新たな関係 $\mathrel{\Vdash^*}$ を定義し，その $M$ への相対化が $\Vdash$ と同値になることを示して，これら二つの補題の成立を証明する．今回は時間の都合上省略したが， $\Vdash$ が個々の原子論理式，論理結合子，量化子に関して満たす性質を逆に $\mathrel{\Vdash^*}$ の帰納的定義として採用して定義していく．

原子論理式の場合

まずは原子論理式の場合について考える．実はこの場合が一番大変である．

強制言語の原子閉論理式の全体を $\mathcal{AL}_\mathbb{P}$ で表す．即ち， $\mathcal{AL}_\mathbb{P}$ は $\tau, \vartheta \in V^\mathbb{P}$ に対し $\tau \in \vartheta$ または $\tau = \vartheta$ の形の論理式全体の成す真クラスである．

$\mathbb{P}$ ：forcing poset， $p \in \mathbb{P}, \varphi \in \mathcal{AL}_\mathbb{P}$ に対し，関係 $p \mathrel{\Vdash^*} \varphi$ を次により定義する：

$p \mathrel{\mathord\Vdash^*} \tau = \vartheta \xLeftrightarrow{\mathrm{def}} \forall \sigma \in \mathrm{dom}(\tau) \cup \mathrm{dom}(\vartheta)\ \forall q \leq p ,[q \mathrel{\Vdash^*} \sigma \in \tau \leftrightarrow q \mathrel{\Vdash^*} \sigma \in \vartheta]$
$p \mathrel{\Vdash^*} \pi \in \tau \xLeftrightarrow{\mathrm{def}} \left\{ q : \exists \left\langle \sigma, r \right\rangle \in \tau \,[q \leq r \wedge q \mathrel{\Vdash^*} \pi = \sigma] \right\}$ が $p$ 以下で稠密

$\forall \pi \in \mathbb{P}\,\forall \tau \in V^\mathbb{P} \, [p \mathrel{\Vdash^*} \tau = \tau]$
$\left\langle \sigma, r \right\rangle \in \tau, q \leq r \Longrightarrow q \mathrel{\Vdash^*} \sigma \in \tau$

これがちゃんとした帰納法の定義になっていることを示すためには，どんな整礎関係についての帰納法なのかをはっきりさせなくてはならない．そこで，以下 $(p, \varphi) \in \mathbb{P} \times \mathcal{AL}_\mathbb{P}$ 上に整礎関係を定義を定義しよう．

$x \lhd y \xLeftrightarrow{\mathrm{def}} x \in \mathrm{trcl}(y)$ とおく． $\mathbb{P} \times \mathcal{AL}_\mathbb{P}$ 上の二項関係 $\prec$ を次で定義する： $\begin{gathered} (p, \sigma_1 \in \tau_1) \prec (q, \sigma_2 = \tau_2) \Leftrightarrow (\sigma_1 \lhd \sigma_2 \vee \sigma_1 \lhd \tau_2) \wedge (\tau_1 = \sigma_2 \vee \tau_1 = \tau_2)\\ (p, \sigma_1 = \tau_1) \prec (q, \sigma_2 \in \tau_2) \Leftrightarrow \sigma_2 = \sigma_2 \wedge \tau_2 \lhd \tau_1\\ (p, \sigma_1 = \tau_1) \not\prec (q, \sigma_2 = \tau_2), \quad (p, \sigma_1 \in \tau_1) \not\prec (q, \sigma_2 \in \tau_2) \end{gathered}$

$\prec$ はleft-narrow (set-like)な整礎関係である．

Proof. left-narrow性は $\mathbb{P}$ が集合であることから従う．そこで， $x \prec y \rightarrow \Gamma(x) < \Gamma(y)$ となるようなrank関数 $\Gamma : \mathbb{P} \times \mathcal{AL}_\mathbb{P}$ を定めることによって整礎性を示す．

まず $\rho: V^\mathbb{P}\times V^\mathbb{P}\rightarrow \mathrm{On}$ を， $\rho(\sigma, \tau) \mathrel{:=} \max\left\{ \mathop{\mathrm{rank}}\nolimits(\sigma),\mathop{\mathrm{rank}}\nolimits(\tau) \right\}$ と定め， $\Gamma$ を次で定める： $\begin{aligned} \Gamma(p, \sigma \in \tau) &= \begin{cases} 3 \rho(\sigma, \tau) & (\mathop{\mathrm{rank}}\nolimits(\sigma) < \mathop{\mathrm{rank}}\nolimits(\tau))\\ 3 \rho(\sigma, \tau) + 2 & (\mathop{\mathrm{rank}}\nolimits(\sigma) \geq \mathop{\mathrm{rank}}\nolimits(\tau)) \end{cases} & \Gamma(p, \sigma = \tau) &= 3 \rho(\sigma, \tau) + 1 \end{aligned}$ すると，簡単な場合分けにより $\Gamma$ がrank関数となっていることがわかる．

これにより， $p \in \mathbb{P}$ と $\varphi \in \mathcal{AL}_\mathbb{P}$ に対し $p \mathrel{\Vdash^*} \varphi$ がwell-definedであることはわかった．

原子論理式の場合に $\mathrel{\Vdash^*}$ と $\Vdash$ が一致することを示したい．そのために，補助的な定義と補題を確認しておく．

$\varphi \in \mathcal{AL}_\mathbb{P}$ とする．

$p \mathrel{\Vdash^*} \varphi, q \leq p \Rightarrow q \mathrel{\Vdash^*} \varphi$
$p \mathrel{\Vdash^*} \varphi \Leftrightarrow \left\{ q : q \mathrel{\Vdash^*} \varphi \right\}$ が $p$ 以下で稠密

Proof. (1)は定義から明らか．(2)の $\Rightarrow$ は(1)から従うので，示すべきは $(\Leftarrow)$ である．

$\prec$ に関する帰納法で示す． $\varphi \equiv \pi \in \tau$ の時は， $\left\{ q : A\ \text{が}\ q \text{以下で稠密} \right\}$ が $p$ 以下で稠密なら， $A$ が $p$ 以下で稠密となることから明らか． $\varphi \equiv \tau = \vartheta$ の時を考える．

対偶を示そう． $p \not\mathrel{\Vdash^*} \pi = \tau$ とすると，定義を展開すれば， $\neg [q \mathrel{\Vdash^*} \sigma \in \tau \leftrightarrow q \mathrel{\Vdash^*} \sigma \in \vartheta]$ を満たすような $q \leq p$ と $\sigma \in \mathrm{dom}(\tau) \cup \mathrm{dom}(\vartheta)$ が存在する．特に $q \mathrel{\Vdash^*} \sigma \in \tau$ かつ $q \not\mathrel{\Vdash^*} \sigma \in \vartheta$ であるとして一般性を失わない．すると，帰納法の仮定から $\left\{ r : r \mathrel{\Vdash^*} \sigma \in \vartheta \right\}$ は $q$ 以下で稠密でない．よって $\forall s \leq r\,[s \not\mathrel{\Vdash^*} \pi \in \vartheta]$ を満たす $r \leq q$ が存在する．(1)と $r \leq q \mathrel{\Vdash^*} \sigma \in \tau$ より， $\forall s \leq r\, [s \mathrel{\Vdash^*} \sigma \in \tau \nleftrightarrow s \mathrel{\Vdash^*} \sigma \in \vartheta]$ ．よって $\left\{ q : q \mathrel{\Vdash^*} \tau = \vartheta \right\}$ は $p$ 以下で稠密でない．

$\varphi \in \mathcal{AL}_\mathbb{P}$ に対し， $p \mathrel{\Vdash^*} \neg \varphi \xLeftrightarrow{\mathrm{def}} \forall q \leq p \, [q \not\mathrel{\Vdash^*} \varphi]$

$\varphi \in \mathcal{AL}_\mathbb{P}$ について $p \mathrel{\Vdash^*} \varphi \Leftrightarrow \forall q \leq p\,[q \not\mathrel{\Vdash^*} \neg \varphi]$

Proof. $(\Rightarrow)$ は定義と先の補題の(1)より明らか． $(\Leftarrow)$ は対偶が(2)と定義から従う．

$p \in \mathbb{P} \in M, G \subseteq \mathbb{P}$ ： $M$ 上 $\mathbb{P}$ -ジェネリック， $D \subseteq \mathbb{P}$ ： $p$ 以下で稠密， $D \in M$ とすると，

$p \in G \Rightarrow G \cap D \neq \emptyset$

Proof. $D^+ \mathrel{:=} D \cup \left\{ q \in \mathbb{P} : q \perp p \right\}$ とおけば， $D^+$ は稠密である．定義より明らかに $D^+ \in M$ ．よって $G$ のジェネリック性より $G \cap D^+ \neq \emptyset$ ．ここで $r \in G \cap D^+$ をとると， $r, p \in G$ より $r \mathrel{\|} p$ となるので， $r \in D$ ．

$M \models ZF-P$ ：ctm， $\mathbb{P} \in M$ ， $G \subseteq \mathbb{P}$ ： $M$ 上 $\mathbb{P}$ -ジェネリック， $\varphi \in \mathcal{AL} \cap M$ とする．

$(p \mathrel{\Vdash^*} \varphi)^M \wedge p \in G\Rightarrow M[G] \models \varphi$
$M[G] \models \varphi \Rightarrow \exists p \in G\, (p \mathrel{\Vdash^*} \varphi)^M$

Proof. それぞれ $\prec$ に関する帰納法で示す．原子論理式の場合に関しては定義の方法から $\mathrel{\Vdash^*}$ は推移的モデルに対して絶対なので，以下相対化を落として考えよう．

$p \mathrel{\Vdash^*} \tau =\vartheta$ の時． $M[G] \models \tau \subseteq \vartheta$ が示せれば逆向きも同様に示せる．そこで $\sigma_G \in \tau_G, r \in G$ となるような $\left\langle \sigma, r \right\rangle \in \tau$ を取る． $p, r \in G$ より $q \leq p, r$ で $q \in G$ を満たすものが取れる．すると注意1より $q \mathrel{\Vdash^*} \sigma \in \tau$ となる．また， $\mathrel{\Vdash^*}$ の定義より $q \mathrel{\Vdash^*} \sigma \in \tau \leftrightarrow q \mathrel{\Vdash^*} \sigma \in \vartheta$ だったので $q \mathrel{\Vdash^*} \sigma \in \vartheta$ が成立する．すると帰納法の仮定より $M[G] \models \sigma \in \vartheta$ となり， $M[G] \models \tau \subseteq \vartheta$ が云えた．

$p \mathrel{\Vdash^*} \pi \in \tau$ の時．この時， $D \mathrel{:=} \left\{ q : \exists \left\langle \sigma, r \right\rangle \in \tau \,[q \leq r \wedge q \mathrel{\Vdash^*} \pi = \sigma] \right\}$ は $p$ 以下で稠密である．よって補題3より $q \leq p$ で $\exists \left\langle \sigma, r \right\rangle \in \tau \,[q \leq r \wedge q \mathrel{\Vdash^*} \pi = \sigma], q \in G$ を満たすものが取れる．よって帰納法の仮定より $M[G] \models \pi = \sigma$ である． $G$ はフィルターなので $r \in G$ だから，以上と合わせて $\pi_G = \sigma_G \in \tau_G$ となり， $M[G] \models \pi \in \tau$ が云えた．
$M[G] \models \pi \in \tau$ の時． $D = \left\{ q : \exists \left\langle \sigma, r \right\rangle \in \tau \,[q \leq r \wedge q \mathrel{\Vdash^*} \pi = \sigma] \right\}$ が $p$ 以下で稠密となるような $p \in G$ を見付けたい．定義より， $\left\langle \sigma, r \right\rangle \in \tau$ で $\sigma_G = \pi_G$ かつ $r \in G$ を満たすような物が取れる．定義を展開すれば $M[G] \models \pi = \sigma$ であり，帰納法の仮定より $p \mathrel{\Vdash^*} \pi = \sigma$ を満たすような $p \in G$ が取れる． $G$ がフィルターであることと補題 1 (1)から $p \leq r$ として良い．すると補題 1 (2)より $D$ は $p$ 以下で稠密となり， $p \mathrel{\Vdash^*} \pi \in \tau$ となる．

$M[G] \models \tau = \vartheta$ の時． $D$ を以下のいずれか一つを満たす $q$ の全体とする：
1. $q \mathrel{\Vdash^*} \tau = \vartheta$
2. $\exists \sigma \in \mathrm{dom}(\tau) \cup \mathrm{dom}(\vartheta)\,[q \mathrel{\Vdash^*} \sigma \in \tau \wedge q \mathrel{\Vdash^*} \sigma \notin \vartheta]$
3. $\exists \sigma \in \mathrm{dom}(\tau) \cup \mathrm{dom}(\vartheta)\,[q \mathrel{\Vdash^*} \sigma \notin \tau \wedge q \mathrel{\Vdash^*} \sigma \in \vartheta]$
すると， $D$ は $\mathbb{P}$ で稠密であり，特に $D \in M$ である．すると， $G$ はジェネリックなので $p \in G \cap D$ が取れる． $p$ が(1)を満たせばOK．もし(2)を満たすとすると， $p \in G$ と(a)より $M[G] \models \sigma \in \tau$ となる．ここで， $M[G] \models \tau = \vartheta$ よりこれらを合わせれば $M[G] \models \sigma \in \vartheta$ ．すると帰納法の仮定より $q \mathrel{\Vdash^*} \sigma \in \vartheta$ を満たすような $q \in G$ を取ることが出来る．特に $q \leq p$ としてよい．しかし， $q \leq p \mathrel{\Vdash^*} \sigma \notin \vartheta$ より $\mathrel{\Vdash^*}$ の定義から $q \not\mathrel{\Vdash^*} \sigma \in \vartheta$ とならなくてはならないので矛盾．同様の議論により(3)も有り得ない．

$M \models ZF-P$ ：c.t.m.， $P \in M$ ， $\varphi \in \mathcal{AL}_\mathbb{P} \cap M \Longrightarrow p \Vdash_{\mathbb{P}, M} \varphi \Leftrightarrow (p \mathrel{\Vdash_\mathbb{P}^*} \varphi)^M$

Proof. 前回とおなじく相対化は無視して議論を進めることが出来る． $(\Leftarrow)$ は補題 1 (a)より直ちに従うので， $(\Rightarrow)$ を示す．そこで $p \Vdash \varphi$ かつ $p \not\mathrel{\Vdash^*} \varphi$ とする．この時補題2より $q \mathrel{\Vdash^*} \neg \varphi$ を満たす $q \leq p$ が存在する．すると定義より $\forall r \leq q \, [r \not\mathrel{\Vdash^*} \varphi]$ となる．ここで $q \in G$ を満たすジェネリックフィルターを取る．この時 $p \geq q$ より $p \in G$ なので，仮定より $M[G] \models \varphi$ を満たす．すると，補題1 (b)より $r \in G$ で $r \mathrel{\Vdash^*} \varphi$ を満たすものが取れ， $G$ がフィルターであることから特に $r \leq q$ とできる．すると $r \mathrel{\Vdash^*} \neg \varphi$ となり矛盾．

一般の論理式について

原子論理式に関しての定義は済んだので，一般の強制言語の論理式に対して $\mathrel{\Vdash^*}$ を定義していこう．

$p \in \mathbb{P} \in M \models ZF - P$ ， $\varphi, \psi \in \mathcal{FL}_\mathbb{P}$ について，以下のように帰納的に $p \mathrel{\Vdash^*} \varphi$ を定める：

$\varphi \in \mathcal{AL}_\mathbb{P}$ の時は定義2と同じ．
$p \mathrel{\Vdash^*} \varphi \wedge \psi \xLeftrightarrow{\mathrm{def}} p \mathrel{\Vdash^*} \varphi$ かつ $p \mathrel{\Vdash^*} \psi$
$p \mathrel{\Vdash^*} \neg \varphi \xLeftrightarrow{\mathrm{def}} \forall q \leq p \,[ q \not \mathrel{\Vdash^*} \varphi]$
$p \mathrel{\Vdash^*} \varphi \rightarrow \psi \xLeftrightarrow{\mathrm{def}} \neg \exists q \geq p \,[q \mathrel{\Vdash^*} \varphi \wedge q \mathrel{\Vdash^*} \neg \psi]$
$p \mathrel{\Vdash^*} \varphi \vee \psi \xLeftrightarrow{\mathrm{def}} \left\{ q : [q \mathrel{\Vdash^*} \varphi] \vee [q \mathrel{\Vdash^*} \psi] \right\}$ が $p$ 以下で稠密
$p \mathrel{\Vdash^*} \forall x \varphi(x) \xLeftrightarrow{\mathrm{def}} \forall \tau \in V^\mathbb{P} \, p \mathrel{\Vdash^*} \varphi(\tau)$
$p \mathrel{\Vdash^*} \exists x \varphi(x) \xLeftrightarrow{\mathrm{def}} \left\{ q : \exists \tau \in V^\mathbb{P} \, q \mathrel{\Vdash^*} \varphi(\tau) \right\}$ が $p$ 以下で稠密

ここで， $(3)$ の定義は定義4と整合的である．また， $\forall, \exists$ の定義は， $\wedge, \vee$ の定義の一般化と見做せる．

この「帰納的」定義を注意深くみてみると，(6)や(7)の定義では，各 $\tau \in V^\mathbb{P}$ について $\varphi(\tau)$ の形の $\mathcal{FL}_\mathbb{P}$ 閉論理式全体について帰納法を回している．これは真クラスなので $V$ の中ではどう頑張っても定義出来ないことがわかる．即ち，上の $\mathrel{\Vdash^*}$ の定義はメタ理論における定義図式であって， $p \mathrel{\Vdash^*} \varphi \Leftrightarrow \Psi(p, \varphi)$ を満たすような一つの論理式が存在するのではない．つまり，各 $\varphi(\vec{x}) \in \mathcal{FL}_\mathbb{P}$ に対して， $p \mathrel{\Vdash^*} \varphi(\vec{\varkappa})$ を表す論理式 $Forces_\varphi(p, \vec{\varkappa})$ を帰納的に作る方法が，論理式の長さに関する帰納法で与えられているのだ．我々の目的は $\Vdash$ に関するDefinability lemmaを確立することだから，各 $\varphi$ に対して $p \Vdash \varphi$ を表す論理式を別個に書くことができれば良いので， $\mathrel{\Vdash^*}$ が $V$ の内部で定義出来なくても問題はないのである．

このように定義すれば，今までの原子論理式に対する命題を一般の強制言語の論理式に拡張出来る．上の定義は， $\neg$ が与えられれば同値変形だけで出て来るので，以下では必要最低限の場合だけ証明することにする：

$\varphi \in \mathcal{FL}_\mathbb{P}$ に対し，

$p \mathrel{\Vdash^*} \varphi, q \leq p \Rightarrow q \mathrel{\Vdash^*} \varphi$
$p \mathrel{\Vdash^*} \varphi \Leftrightarrow \left\{ q : q \mathrel{\Vdash^*} \varphi \right\}$ が $p$ 以下で稠密
$p \mathrel{\Vdash^*} \varphi \Leftrightarrow \forall q \leq p\, [q \not\mathrel{\Vdash^*} \neg \varphi]$
$p \mathrel{\Vdash^*} \varphi$ かつ $p \mathrel{\Vdash^*} \neg \varphi$ となることは有り得ない．

Proof. (c)(d)は(a)(b)から従い，(a)は定義より明らか．原子論理式の場合と同様に(b)の $(\Leftarrow)$ だけ帰納法により示す．

$\varphi \equiv \forall x \psi(x)$ の時． $\left\{ q : q \mathrel{\Vdash^*} \forall x \psi(x) \right\}$ が $p$ 以下で稠密だとする．定義を展開すれば， $\forall q \leq p \exists r \leq q \forall \tau \in V^\mathbb{P}\,[r \mathrel{\Vdash^*} \psi(\tau)]$ となる．特にこれから各 $\tau \in V^\mathbb{P}$ について $\left\{ q : q \mathrel{\Vdash^*} \psi(\tau) \right\}$ は $p$ 以下で稠密となる．よって帰納法の仮定より $\forall \tau \in V^\mathbb{P}\,p \mathrel{\Vdash^*} \psi(\tau)$ となり，定義から $p \mathrel{\Vdash^*} \forall x \varphi(x)$ となる．

$\varphi \equiv \neg\psi$ の時．対偶を示す． $p \not\mathrel{\Vdash^*} \neg \psi$ とすると，定義から $\exists q \leq p\,[q \mathrel{\Vdash^*} \psi]$ であり，(a)より $\forall r \leq q\,[r \mathrel{\Vdash^*} \psi]$ となる．よって $\left\{ s : s \mathrel{\Vdash^*} \neg \psi \right\}$ は $p$ 以下で稠密でない．

$\varphi \equiv \psi \vee \vartheta$ の時． $D = \left\{ q : q \mathrel{\Vdash^*} \psi \vee \vartheta \right\}$ が $p$ 以下で稠密だとする．このときもう少し定義を展開すると， $\left\{ q :\left\{ r : [r \mathrel{\Vdash^*} \psi] \vee [r \mathrel{\Vdash^*} \vartheta] \right\}\ \text{が}\ q\ \text{以下で稠密} \right\}$ が $p$ 以下で稠密である．稠密性の定義よりこれは単に $\left\{ r : [r \mathrel{\Vdash^*} \psi] \vee [r \mathrel{\Vdash^*} \vartheta] \right\}$ が $p$ 以下で稠密であるということである．

いよいよ，一般の $\varphi$ について $\mathrel{\Vdash^*}$ をモデルと結び付ける補題を証明する：

$M \models ZF-P$ ：ctm， $\mathbb{P} \in M$ ， $G \subseteq \mathbb{P}$ ： $M$ 上 $\mathbb{P}$ -ジェネリック， $\varphi \in \mathcal{FL} \cap M$ とする．

$(p \mathrel{\Vdash^*} \varphi)^M \wedge p \in G\Rightarrow M[G] \models \varphi$
$M[G] \models \varphi \Rightarrow \exists p \in G\, (p \mathrel{\Vdash^*} \varphi)^M$

Proof. 構造に関する帰納法により，(a) (b)の二つを同時に証明する． $L(\varphi)$ により「 $\varphi$ について(a) (b)が成立する」ことを表す．

以上を使えば，原子論理式の時と同様にして $\Vdash$ との関係を証明できる：

$M \models ZF-P$ ：c.t.m.， $P \in M$ ， $\varphi \in \mathcal{FL}_\mathbb{P} \cap M \Longrightarrow p \Vdash \varphi \Leftrightarrow (p \mathrel{\Vdash^*} \varphi)^M$

ここまでくれば，Definability lemmaとTruth lemmaの証明は簡単である：

Truth lemmaとDefinability lemmaの証明. Truth lemmaは補題8および補題7の(b)から明らか．Definability lemmaについても，補題8より $\left\{ (\mathbb{P}, \leq, \mathbb{1}, p, \vec{\kappa}) : \cdots \ p \Vdash \varphi(\vec{\varkappa}) \right\}$ は $M$ 内で定義可能．

実は，後程示すが「 $M \models ZFC$ で $p \Vdash \exists x \varphi(x)$ ならば $p \Vdash \varphi(\tau)$ を満たす $\tau \in M^\mathbb{P}$ が存在する」という定理（極大原理）がある．これを使えば $\exists$ に関する $\mathrel{\Vdash^*}$ の定義を簡略化出来そうな気もするが，その極大原理の証明にここでの議論を使っているので循環論法になってしまう．また， $M$ が必ずしも $AC$ を満たさない場合に使えなくなってしまうので，ここでは上の定義を用いた．

参考文献

[1]

田中一之, 渕野昌, 松原洋, and 戸田山和久, ゲーデルと20世紀の論理学（ロジック）４集合論とプラトニズム, vol. 4. 東京大学出版会, 2007.

[2]

新井敏康, 数学基礎論. 岩波書店, 2011.

[3]

K. Kunen, Set theory, vol. 34. College Publications, 2011.

Definability lemma と Truth lemma konn-san.com

原子論理式の場合

一般の論理式について

参考文献

Comments