第I章 演習問題 [9]

(a)→(b)の証明:  集合 \(X\) を整列順序づけする関係 \(<_X\) があったとして, \(Y\in\mathcal{P}(X)\setminus\{0\}\) にその \(<_X\)-最小要素を対応させる関数 \(C\) を考えればよい.

(b)→(a)の証明:  ヒントに従い, \(p\notin X\) なる \(p\) をひとつ選び, \(\mathcal{P}(X)\setminus\{0\}\) からの選択関数 \(C\) を, \(Y\notin\mathcal{P}\setminus\{0\}\) のとき \(C(Y)=p\) として定義域を \(\mathbf{V}\) 全体に拡張しよう. この \(C\) によって再帰的に \[ F(\alpha)=C\big(X\setminus\{\,F(\xi)\,:\,\xi<\alpha\,\}\big) \] と定義される \(F\) は, 定義域が \(\mathbf{ON}\) 全体なので厳密にいえば関数ではない. だがクラスとしての演算としてこの \(F\) が定まることは間違いない.

内包性公理により \[ Y=\big\{\,x\in X\,:\,\exists\alpha(x=F(\alpha))\,\big\} \] で定まる \(Y\) は集合である. \(x\in Y\) のとき \(x=F(\alpha)\) をみたす順序数 \(\alpha\) は一意的に定まるから, \[ \begin{align} A = &\big\{\,\alpha\,:\,\alpha\in\mathbf{ON}\land F(\alpha)\in X\,\big\} \\ = &\big\{\,\alpha\,:\, \exists x\in Y\big(\,x=F(\alpha)\land \alpha\in\mathbf{ON}\,\big)\,\big\} \end{align} \] で定まる \(A\) は置換公理により集合である. \(\mathbf{ON}\neq A\) だから, \(\beta=\min\{\,\gamma\,:\,\gamma\in\mathbf{ON}\land \gamma\notin A\,\}\) とおこう. すると \[ \forall\alpha<\beta\big(\,F(\alpha)\in X\,\big)\quad\text{かつ}\quad F(\beta)=p \] となる. これは, \(X\setminus\{\,F(\alpha)\,:\,\alpha<\beta\,\}\notin\mathcal{P}(X)\setminus\{0\}\) を意味するが, もちろん \(X\setminus\{\,F(\alpha)\,:\,\alpha<\beta\,\}\in\mathcal{P}(X)\) ではあるわけだから, \(X\setminus\{\,F(\alpha)\,:\,\alpha<\beta\,\}=0\) すなわち \(\{\,F(\alpha)\,:\,\alpha<\beta\,\}=X\) ということである. こうして得られる \(F\restriction \beta\) は \(\beta\) と \(X\) の間の全単射であり, \(X\) は整列順序づけ可能である.

ヒントに示された \(p\neq X\) という式は本当は \(p\notin X\) が正しい. 正誤表に載せておかなくては.

解答者: 藤田 博司 (公開日: 2011年5月28日)

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

演習問題一覧に戻る