週刊 MAのモデルを作る #03 論理公理の強制

前回は名称と強制関係を定義して基本性質を見た．今回は論理公理が強制されることを見よう．

ZFCの論理的な公理として以下を採用することにする．ただしそれぞれの全称閉包をとる．すなわち各自由変数 $x$ について $\forall x$ で縛る．

$\varphi \to (\psi \to \varphi)$
$(\varphi \to (\psi \to \theta)) \to ( (\varphi \to \psi) \to (\varphi \to \theta))$
$(\neg \psi \to \neg \varphi) \to (\varphi \to \psi)$
$\forall x (\varphi \to \psi) \to (\forall x \varphi \to \forall x \psi)$
$\varphi \to \forall x \varphi$ (ただし $x$ は $\varphi$ の自由変数でないとする)
$\forall x \varphi(x) \to \varphi(y)$ ( $\varphi(x)$ の自由変数 $x$ に $y$ は代入可能であるとする)
$x=x$
$x=y \to y=x$
$x=y \to (y=z \to x=z)$
$x=y \to (x\in A \to y\in A)$
$A=B \to (x\in A \to x\in B)$

以下，上記の論理公理がすべて強制されることを示すが，証明するのがかんたんな1-8を先に示す．

命題1
$P$ を半順序集合とする．このとき上記の論理公理のうち1番から8番はすべて最大元 $1$ で強制される．

証明．以下，全称閉包によって生じている全称量化については適切に任意に名称をとって議論していると考えてほしい．

1の $\varphi \to (\psi \to \varphi)$ について． $p \in P$ について $p \Vdash \varphi$ とする．このとき $p \Vdash \psi \to \varphi$ を示せばよい． $q \le p$ を任意にとり $q \Vdash \psi$ とする．このとき仮定より $q \Vdash \varphi$ である．よって示せた．

2の $(\varphi \to (\psi \to \theta)) \to ( (\varphi \to \psi) \to (\varphi \to \theta))$ について． $p \Vdash \varphi \to (\psi \to \theta)$ $\cdots (*)$ とする．このとき $p \Vdash (\varphi \to \psi) \to (\varphi \to \theta)$ を示す．そのために $q \le p$ を任意にとり， $q \Vdash \varphi \to \psi$ $\cdots (**)$ とする．示すべきは $q \Vdash \varphi \to \theta$ である．そのために， $r \le q$ を任意にとり， $r \Vdash \varphi$ とする．すると $(*)$ より $r \Vdash \psi \to \theta$ であり， $(**)$ より $r \Vdash \psi$ である.この二つから $r \Vdash \theta$ .よって示せた．

3の $(\neg \psi \to \neg \varphi) \to (\varphi \to \psi)$ について． $p \Vdash \neg \psi \to \neg \varphi$ $\cdots (*)$ とする．このとき $p \Vdash \varphi \to \psi$ を示す．そのために $q \le p$ を任意にとり， $q \Vdash \varphi$ とする．背理法で $q \Vdash \psi$ でないと仮定すると $r \le q$ があって $r \Vdash \neg \psi$ である．すると $(*)$ より $r \Vdash \neg \varphi$ . $q \Vdash \varphi$ より特に $r \Vdash \varphi$ でもあるので， $r$ は $\varphi$ と $\neg\varphi$ の両方を強制する．これは矛盾．

4の $\forall x (\varphi \to \psi) \to (\forall x \varphi \to \forall x \psi)$ について． $p \Vdash \forall x (\varphi \to \psi)$ $\cdots (*)$ とする． $q \le p$ をとり $q \Vdash \forall x \varphi$ $\cdots (**)$ とする．このとき示すべきは， $q \Vdash \forall x \psi$ である．名称 $\dot{x} \in V^P$ を任意にとる．このとき $(*)$ より $q \Vdash \varphi(\dot{x}) \to \psi(\dot{x})$ であり $(**)$ より $q \Vdash \varphi(\dot{x})$ である．よってこの二つから $q \Vdash \psi(\dot{x})$ である．これで $q \Vdash \forall x \psi$ が示された．

5の $\varphi \to \forall x \varphi$ について． $p \Vdash \varphi$ とする． $\varphi$ には変数 $x$ は自由に出現しないということから任意の名称 $\dot{x}$ について $p \Vdash \varphi(\dot{x})$ である．よって $p \Vdash \forall x \varphi$ となる．

6の $\forall x \varphi(x) \to \varphi(y)$ について． $\dot{y} \in V^P$ を任意にとる． $p \Vdash \forall x \varphi(x)$ を仮定する．このとき全称量化の強制の定義から $p \Vdash \varphi(\dot{y})$ .よってOK.

7の $x = x$ について．ランク帰納法で $\Vdash \dot{x} = \dot{x}$ を示す．等号の強制の定義を思い出すと， $\forall (\dot{z}, p) \in \dot{x}\ (p \Vdash \dot{z} \in \dot{x})$ を示せばよい． $(\dot{z}, p) \in \dot{x}$ とする． $p \Vdash \dot{z} \in \dot{x}$ の定義は $\{ q \in P : \exists (\dot{w}, r) \in \dot{x} \ (q \le r \land q \Vdash \dot{z} = \dot{w}) \}$ が $p$ 以下で稠密ということであった．今任意の $q \le p$ で $(\dot{w}, r) = (\dot{z}, p)$ ととることで， $q \le r$ は満たしているし，ランク帰納法の仮定より $q \Vdash \dot{z} = \dot{z}$ を満たしている．よって， $p \Vdash \dot{z} \in \dot{x}$ なのでこれで示せた．

8の $x = y \to y = x$ について． $p \Vdash \dot{x} = \dot{y}$ ならば $p \Vdash \dot{y} = \dot{x}$ なのは等号の強制の定義を見れば明らか．なのでよい． □

命題2
$P$ を半順序集合とする．このとき上記の論理公理のうち9番と10番は最大元 $1$ で強制される．

証明．ここがやっかいなポイントである． 9番を証明するのに10番が必要になり，10番を証明するのに9番が必要になる．そこでランク帰納法で同時に9番と10番を示す．

帰納法の仮定を表す命題を次のようにおく:

$\begin{align*} \mathrm{IH_1}(\alpha) &\iff \forall \dot{x}, \dot{y}, \dot{z} \in V^P_\alpha\ 1 \Vdash \dot{x}=\dot{y} \to (\dot{y}=\dot{z} \to \dot{x}=\dot{z}) \\ \mathrm{IH_2}(\alpha) &\iff \forall \beta \lt \alpha\ \forall \dot{x}, \dot{y} \in V^P_\beta, \dot{A} \in V^P_\alpha\ 1 \Vdash \dot{x}=\dot{y} \to (\dot{x}\in\dot{A} \to \dot{y}\in\dot{A}) \end{align*}$

任意の順序数 $\alpha$ について $\mathrm{IH}_2(\alpha) \Rightarrow \mathrm{IH}_1(\alpha)$ と $(\forall \beta \lt \alpha\ \mathrm{IH}_1(\beta)) \Rightarrow \mathrm{IH}_2(\alpha)$ を示す．

まず， $\mathrm{IH}_2(\alpha)\Rightarrow \mathrm{IH}_1(\alpha)$ について． $p \Vdash \dot{x}=\dot{y}$ かつ $p \Vdash \dot{y}=\dot{z}$ としよう．このとき $p \Vdash \dot{x}=\dot{z}$ を示せばよい． $p \Vdash \dot{x} = \dot{z}$ の定義の前半 $\forall (\dot{w}, q) \in \dot{x}\ \forall r \le p, q\ (r \Vdash \dot{w} \in \dot{z})$ を示そう．後半も同様である． $(\dot{w}, q) \in \dot{x}$ と $r \le p, q$ を任意にとる． $s \le r$ を任意にとる．このとき， $p \Vdash \dot{x}=\dot{y}$ の定義より $s \Vdash \dot{w} \in \dot{y}$ である．よって $t \le s$ と $(\dot{w}', u) \in \dot{y}$ がとれて $t \le u$ かつ $t \Vdash \dot{w}' = \dot{w}$ となる．すると $p \Vdash \dot{y} = \dot{z}$ の定義より， $t \Vdash \dot{w}' \in \dot{z}$ となる． $t$ は $\dot{w}' = \dot{w}$ と $\dot{w}' \in \dot{z}$ の両方を強制するので $\mathrm{IH}_1(\beta)$ より $\dot{w} \in \dot{z}$ である．

$(\forall \beta \lt \alpha\ \mathrm{IH}_1(\beta)) \Rightarrow \mathrm{IH}_2(\alpha)$ について． $p \Vdash \dot{x} = \dot{y}$ かつ $p \Vdash \dot{x} \in \dot{A}$ とする．このとき $p \Vdash \dot{y} \in \dot{A}$ を示す． $q \le p$ とする．このとき $p \Vdash \dot{y} \in \dot{A}$ の定義より， $r \le q$ と $(\dot{z}, s) \in \dot{A}$ がとれて， $r \le s$ かつ $r \Vdash \dot{x} = \dot{z}$ . すると $r$ は $\dot{x} = \dot{y}$ と $\dot{x} = \dot{z}$ を強制するので $\forall \beta \lt \alpha\ \mathrm{IH}_1(\beta)$ より $r \Vdash \dot{y} = \dot{z}$ . これで $p \Vdash \dot{y} \in \dot{A}$ が言えた． □

命題3
$P$ を半順序集合とする．このとき上記の論理公理のうち11番は最大元 $1$ で強制される．

証明． $p \Vdash \dot{A} = \dot{B}$ かつ $p \Vdash \dot{x} \in \dot{A}$ とする．このとき $p \Vdash \dot{x} \in \dot{B}$ を示す． $q \le p$ とする．このとき $p \Vdash \dot{x} \in \dot{A}$ より $r \le q$ と $(\dot{z}, s) \in \dot{A}$ がとれて， $r \le s$ かつ $r \Vdash \dot{z} = \dot{x}$ .すると $p \Vdash \dot{A} = \dot{B}$ の定義より $r \Vdash \dot{z} \in \dot{B}$ . すると $r$ は $\dot{z} \in \dot{B}$ と $\dot{z} = \dot{x}$ をともに強制するから論理公理の10番が強制されることはすでに証明済みなので， $r \Vdash \dot{x} \in \dot{B}$ . □