第III章 演習問題 [19]

この問題では \(\mathrm{ZF}\) から冪集合公理と無限公理を削除し, 置換公理図式を \(\mathrm{AR}^*\) 図式に, 基礎の公理を \(\mathrm{AF}^*\) 図式に差し替えた \(\mathrm{ZF}^*-\mathrm{P}-\mathrm{Inf}\) で議論する.

(a) 推移閉包の存在証明 集合 \(y\) は推移的で \(x\subset y\) であるという内容の式を \(\phi(x,y)\) としよう. この式について \(\forall a\exists b\,\phi(a,b)\) を証明したい. そのため, ひとまず \[ \forall x\in a\exists y\,\phi(x,y)\tag{1} \] を仮定する. すると \(\phi\) についての \(\mathrm{AR}^*\) 図式により, \[ \exists c\forall x\in a\exists y\in c\,\phi(x,y) \] となる. 内包性公理によって \(c\) から推移的集合である要素だけを抜きだすことができるので, 最初から \(c\) の要素はすべて推移的集合ばかりだと仮定してもさしつかえない. ここで \(b = a\cup \bigcup c\) とおこう. あきらかに \(a\subset b\) である. \(b\) が推移的集合であることを見るため \(s\in t\in b\) だったとしよう. (i) もしも \(t\in a\) なら, 式(1)により \(t\subset y\in c\) となる \(y\) がとれるが \(y\) が推移的集合であるから \(s\in t\subset y\) であり, したがってまた \(s\in y\subset \bigcup c\subset b\) である. (ii) もしも \(t\in \bigcup c\) ならある \(y\in c\) について \(t\in y\) だが \(y\) が推移的集合なので \(t\subset y\) で, 以下(i)と同様にして \(s\in b\) となる. こうしていずれにせよ \(s\in t\in b\) から \(s\in b\) が導かれることになり, \(b\) が推移的集合とわかった. \(b\) は \(a\) を部分集合として含む推移的集合であるから \(\phi(a,b)\) である. こうして, 仮定(1)から \[ \exists y\,\phi(a,y) \]が示された, そこで \(x\) についての式 \(\exists y\,\phi(x,y)\) についての \(\mathrm{AF}^*\) 図式により \[ \forall a\exists b\,\phi(a,b) \] が成立する. つまり, 任意の集合は, なんらかの推移的集合の部分集合になっている.

さて, ここで集合 \(A\) に対して, \(\phi(A,B)\) をみたす集合 \(B\), すなわち \(A\) を部分集合として含む推移的集合 \(B\) をひとつ固定しよう. そして内包性公理により \[ T = \big\{\,x\in B\,:\,\forall B'(\,\phi(A,B')\rightarrow x\in B'\,)\,\big\} \] とおくと, この \(T\) は \(A\) を部分集合として含む推移的集合すべての共通部分であり, とりもなおさず \(A\) の推移閉包 \(\mathrm{tr\,cl}(A)\) である.

(b) 関係 \(\in\) に関する超限再帰的定義 クラス写像 \(\mathbf{F}:\mathbf{V}\times\mathbf{V}\to\mathbf{V}\) が与えられたとする. 変数 \(f\) に対する次の三つの条件の連言を \(\theta(f)\) と書くことにする:

(イ) \(f\) は関数である,
(ロ) \(f\) の定義域は推移的集合である
(ハ) \(f\) の定義域に属するすべての集合 \(y\) について \[ f(y)=\mathbf{F}(y,f\restriction y) \] が成立する

この式 \(\theta\) から, さらに (一意性条件) \[ \phi(x)\;\leftrightarrow\;\forall f\forall f'\Big[\, \theta(f)\land\theta(f')\land x\subset\mathrm{dom}(f)\cap \mathrm{dom}(f')\, \rightarrow\, f\restriction \mathrm{tr\,cl}(x)=f'\restriction \mathrm{tr\,cl}(x) \,\Big] \] という式 \(\phi(x)\) と, (存在条件) \[ \psi(x)\;\leftrightarrow\;\exists f\Big[\,\theta(f) \land x\subset\mathrm{dom}(f)\,\Big] \] という式 \(\psi(x)\) を定めよう. 条項(ハ)により \(\forall x\in a\,\phi(x)\rightarrow\phi(a)\) は簡単に確かめられる. したがって \(\mathrm{AF}^*\) によって \(\forall x\phi(x)\) である.

同様に \(\forall x\psi(x)\) を示したいが, これには少し説明がいるだろう. もしも \(\forall x\in a\,\psi(x)\) であれば, \(a\) の要素 \(x\) ごとに \(\theta(f)\) かつ \(x\subset\mathrm{dom}(f)\) をみたす関数 \(f\) が少なくともひとつ, 一般には複数, 存在するが, \(\phi(x)\) がすでに示されているので, どのように \(f\) を選んでも, \(f\restriction \mathrm{tr\,cl}(x)\) は \(x\) だけによって定まる. そこでこの \(f\restriction \mathrm{tr\,cl}(x)\) を \(f_x\) と書くことにする. もしも \(x,y\in\mathrm{tr\,cl}(a)\) かつ \(z\in\mathrm{dom}(f_x)\cap \mathrm{dom}(f_y)\) であれば, (定義域の推移性により) \(z\subset \mathrm{dom}(f_x)\cap \mathrm{dom}(f_y)\) であり, しかも \(\theta(f_x)\) かつ \(\theta(f_y)\) かつ \(\phi(z)\) であるから \(f_x\restriction \mathrm{tr\,cl}(z)=f_y\restriction \mathrm{tr\,cl}(z)\) である. したがってまた \(f_x\restriction z=f_y\restriction z\) でもあり, \[ f_x(z)=\mathbf{F}(z,f_x\restriction z)=\mathbf{F}(z,f_y\restriction z)=f_y(z) \] ということになる. こうして, \(\mathrm{tr\,cl}(a)\) の各要素 \(x\) ごとに定まる関数 \(f_x\) たちは互いに両立する. 次に各 \(f_x\) の定義域に \(x\) を含めるように \[ \bar f_x=f_x\cup\big\{\,\langle x,\mathbf{F}(x,f_x\restriction x)\rangle\,\big\} \] と拡大して \(\bar f_x\) を作ろう. \(\bar f_x\) たちどうしも互いに両立する. 最後に \[ f_a = \bigcup\big\{\,\bar f_x\,:\,x\in \mathrm{tr\,cl}(a)\,\big\} \] とすると, \(\theta(f_a)\) かつ \(a\subset\mathrm{dom}(f_a)\) となり, \(\psi(a)\) が成立する. こうして \(\forall x\in a\,\psi(x)\) から \(\psi(a)\) が導かれたので, \(\mathrm{AF}^*\) により \(\forall x\psi(x)\) である.

最後に, クラス関数 \(\mathbf{G}:\mathbf{V}\to\mathbf{V}\) を \[ \mathbf{G}(x)=y\;\leftrightarrow\;\exists f\big(\,\theta(f)\land x\in \mathrm{dom}(f)\land f(x)=y\,\big) \tag{2} \] と定める. \(\forall x\phi(x)\) だったから(2)の右辺は一価関数を定め, \(\forall x\psi(x)\) だったからその関数の定義域はすべての集合を含む. また この \(\mathbf{G}\) について \[ \forall x\,\Big[\; \mathbf{G}(x)=\mathbf{F}(x,\mathbf{G}\restriction x) \;\Big] \] となることは \(\theta\) の定め方と(2)からすぐにわかる.

 

解答者: 藤田 博司 (公開日: 2011年6月10日)
2011年7月4日更新: 誤記を訂正
2011年7月7日更新: 誤記を訂正

この解答に不具合を発見した方はぜひご指摘ください.

演習問題一覧に戻る