§E1.20選択公理と Zorn の補題

証明.(1)$\Rightarrow$(2)を示す。$X$を集合とする。$\Lambda=\mathcal P(X)\setminus\{\emptyset\}$とおき、$S\in\Lambda$に対して$A_S=S$とおく。$\{x\}\in\Lambda$が各$x\in X$について成り立つので$\bigcup_{S\in\Lambda}A_S=X$であり、(1)により、すべての$S\in\Lambda$に対して$c(S)\in S$を満たす写像$c\colon\Lambda\to X$が存在する。

$e=\{x\in X\mid x\notin x\}$とおく。この集合は§E1.13 定義 2.1により存在する。$e\in X$と仮定すると、$e$の定義により、$e\in e$であることと$e\notin e$であることが同値になって矛盾する。したがって$e\notin X$である。

§E1.17 系 2.6 (2)により、順序数の全体で定義された対応$F$で、各順序数$\alpha$に対して

を満たすものがただ一つ定まる。ここで$F[\alpha]=\{F(\beta)\mid\beta<\alpha\}$であり、これは§E1.13 定義 5.1により集合である。

$F(\alpha)=e$を満たす順序数が存在することを示す。存在しないとすると、すべての順序数$\alpha$に対して$F(\alpha)\in X\setminus F[\alpha]$である。$\beta<\alpha$ならば$F(\beta)\in F[\alpha]$であるから$F(\alpha)\neq F(\beta)$であり、相異なる順序数の$F$による値は相異なる。$Y=\{x\in X\mid F(\alpha)=x$を満たす順序数$\alpha$が存在する$\}$は§E1.13 定義 2.1により集合であり、各$x\in Y$に対して$F(\alpha)=x$を満たす順序数$\alpha$はただ一つである。§E1.13 定義 5.1により、この対応による$Y$の像は集合である。この像は順序数の全体に一致するから、§E1.16 命題 2.6に矛盾する。

$F(\alpha_1)=e$を満たす順序数$\alpha_1$を取る。$\{\beta\in\alpha_1\cup\{\alpha_1\}\mid F(\beta)=e\}$は空でない順序数の集合であるから、§E1.16 命題 2.5 (3)により最小元$\theta$をもつ。$\beta<\theta$ならば$\beta<\alpha_1$であるから$F(\beta)\neq e$であり、したがって$F(\beta)\in X\setminus F[\beta]$である。上と同じ理由で、$\beta<\gamma<\theta$ならば$F(\beta)\neq F(\gamma)$である。$F(\theta)=e$であるから$X\setminus F[\theta]=\emptyset$であり、$F[\theta]\subseteq X$とあわせて$F[\theta]=X$である。したがって$\beta\mapsto F(\beta)$は$\theta$から$X$への全単射である。$\theta$は順序数であるから所属関係について整列している。$x\preceq y$を、$F(\beta)=x$を満たす$\beta<\theta$と$F(\gamma)=y$を満たす$\gamma<\theta$について$\beta\leq\gamma$が成り立つことと定めると、$\preceq$は$X$上の整列順序である。

(2)$\Rightarrow$(3)を示す。$P$を空でない poset とし、$P$の任意の鎖が$P$に上界をもつとする。(2)により$P$上の整列順序$\preceq$を取る。§E1.16 定理 3.1により、順序数$\theta$と、$\alpha\mapsto p_\alpha$で与えられる$\theta$から$(P,\preceq)$への順序同型が存在する。§E1.17 定理 2.1により、$\theta$を添字集合とする族$(t_\alpha)_{\alpha<\theta}$で、$t_\alpha=1$であることが「$\beta<\alpha$かつ$t_\beta=1$を満たすすべての$\beta$に対して$p_\beta<p_\alpha$が成り立つ」ことと同値であり、そうでないとき$t_\alpha=0$であるものがただ一つ定まる。

$C=\{p_\alpha\mid\alpha<\theta,\ t_\alpha=1\}$とおく。$t_\alpha=t_\gamma=1$かつ$\alpha<\gamma$ならば、$t_\gamma=1$であることの定義により$p_\alpha<p_\gamma$であるから、$C$の任意の二元は比較可能であり、$C$は$P$の鎖である。仮定により$C$は$P$に上界$u$をもつ。

$u<v$を満たす$v\in P$が存在したとする。$\alpha\mapsto p_\alpha$は全射であるから、$v=p_\gamma$を満たす$\gamma<\theta$が存在する。$\beta<\gamma$かつ$t_\beta=1$を満たす$\beta$に対して$p_\beta\in C$であり、$u$が$C$の上界であるから$p_\beta\leq u<v=p_\gamma$である。したがって$t_\gamma=1$であり、$v\in C$である。$u$が$C$の上界であるから$v\leq u$となり、$u<v$に矛盾する。よって$u$は$P$の極大元である。

(3)$\Rightarrow$(1)を示す。$I$を集合とし、$(A_i)_{i\in I}$を空でない集合からなる族とする。$U=\bigcup_{i\in I}A_i$とおく。$J\subseteq I$と、定義域が$J$、終域が$U$であり$g(i)\in A_i$（$i\in J$）を満たす写像$g$のグラフ$\Gamma$との対$(J,\Gamma)$の全体を$P$とする。$\Gamma\subseteq I\times U$であるから、$P$は§E1.13 定義 3.1 (3)で得られる集合$\mathcal P(I)\times\mathcal P(I\times U)$からの§E1.13 定義 2.1による分出で得られる集合である。定義域と終域が対から復元されるので、以下では$P$の元を、対応する写像$g$を用いて$(J,g)$と書く。

$(J,g)\preceq(K,h)$を、$J\subseteq K$かつ$h(i)=g(i)$（$i\in J$）が成り立つことと定める。$\preceq$は反射的かつ推移的である。$(J,g)\preceq(K,h)$かつ$(K,h)\preceq(J,g)$ならば$J=K$であり、$J$の各元での値が一致し、終域はいずれも$U$であるから$g=h$である。したがって$(P,\preceq)$は poset である。

$\mathcal C$を$P$の鎖とする。$J^{*}=\bigcup\{J\mid (J,g)\in\mathcal C\}$とおく。$i\in J\cap K$かつ$(J,g),(K,h)\in\mathcal C$ならば、$(J,g)\preceq(K,h)$と$(K,h)\preceq(J,g)$のいずれかが成り立ち、どちらの場合も$g(i)=h(i)$である。したがって、$i\in J^{*}$に対して$i\in J$を満たす$(J,g)\in\mathcal C$を取り$g^{*}(i)=g(i)$と定めると、この値は$(J,g)$の取り方に依存しない。$g^{*}(i)\in A_i$であるから$(J^{*},g^{*})\in P$であり、$(J^{*},g^{*})$は$\mathcal C$の上界である。$\mathcal C=\emptyset$の場合には$J^{*}=\emptyset$であり、$g^{*}$は$\emptyset$から$U$への空写像である。この元も$P$に属するから、とくに$P\neq\emptyset$である。

(3)により$P$は極大元$(J,g)$をもつ。$J\neq I$とすると$i_0\in I\setminus J$が存在する。$A_{i_0}\neq\emptyset$であるから$b\in A_{i_0}$を取ることができ、$J'=J\cup\{i_0\}$と、$g'(i)=g(i)$（$i\in J$）および$g'(i_0)=b$によって定まる写像$g'\colon J'\to U$に対して$(J',g')\in P$である。$(J,g)\preceq(J',g')$かつ$(J,g)\neq(J',g')$であるから、$(J,g)$の極大性に矛盾する。したがって$J=I$であり、$g$は族$(A_i)_{i\in I}$の選択関数である。

以上の三つの含意により、三つの主張は互いに同値である。▨

証明.§E1.2 定義 5.1により、$\prod_{i\in I}A_i$の元とは、すべての$i\in I$に対して$x(i)\in A_i$を満たす、$I$を添字集合とする族$x$である。これは族$(A_i)_{i\in I}$の選択関数と同じ値の指定であるから、定理 2.1 (1)により(1)が成り立つ。

$g\colon Y\to X$を全射とし、$x\in X$に対して$B_x=g^{-1}(\{x\})$とおく。$g$が全射であるから$B_x\neq\emptyset$である。各$y\in Y$は$B_{g(y)}$に属するから$\bigcup_{x\in X}B_x=Y$である。定理 2.1 (1)により族$(B_x)_{x\in X}$の選択関数$t\colon X\to Y$が存在し、$t(x)\in g^{-1}(\{x\})$、すなわち$g(t(x))=x$である。よって(2)が成り立つ。▨

証明.$P$の鎖の全体を$\mathcal K$とする。鎖は$P$の部分集合であるから、$\mathcal K$は$\mathcal P(P)$からの§E1.13 定義 2.1による分出で得られる集合であり、包含関係について poset である。

$\mathcal D$を$(\mathcal K,\subseteq)$の鎖とし、$U=\bigcup\mathcal D$とおく。$x,y\in U$とすると、$x\in C_1$かつ$y\in C_2$を満たす$C_1,C_2\in\mathcal D$が存在する。$\mathcal D$が包含関係について鎖であるから$C_1\subseteq C_2$または$C_2\subseteq C_1$であり、いずれの場合も$x$と$y$は$\mathcal D$の一つの元に属する。その元は$P$の鎖であるから、$x$と$y$は比較可能である。したがって$U$は$P$の鎖であり、$U\in\mathcal K$である。$\mathcal D$の各元は$U$に含まれるから、$U$は$\mathcal D$の上界である。$\mathcal D=\emptyset$の場合には$U=\emptyset$であり、空集合は$P$の鎖であるから$U\in\mathcal K$である。とくに$\mathcal K\neq\emptyset$である。

定理 2.1の定理 2.1 (3)により、$\mathcal K$は極大元$C$をもつ。$C\subsetneq D$を満たす$P$の鎖$D$が存在すれば$D\in\mathcal K$となり、$C$の極大性に矛盾する。したがって$C$は求める鎖である。▨

証明.(1)$\Rightarrow$(2)を示す。$X\neq\emptyset$であるから$a\in X$を取ることができ、(1)をこの$a$に対して適用すれば、第$0$項の条件を落とした主張が得られる。

(2)$\Rightarrow$(1)を示す。$X$と$R$を(1)の条件のとおりに取り、$a\in X$を任意に指定する。$n\in\omega$に対して、$n$を添字集合とする$X$の元の族を長さ$n$の列という。長さが正である列$s$であって、$s(0)=a$が成り立ち、$k+1$が$s$の長さより小さいすべての$k$に対して$s(k)Rs(k+1)$が成り立つものの全体を$H$とする。族はそのグラフによって定まり、グラフは$\omega\times X$の部分集合であるから、$H$は$\mathcal P(\omega\times X)$からの§E1.13 定義 2.1による分出で得られる集合である。第$0$項が$a$である長さ$1$の列は$H$に属するから$H\neq\emptyset$である。

$s,t\in H$に対して、$s$の長さを$n$とするとき、$t$の長さが$n+1$であり$t(k)=s(k)$（$k<n$）が成り立つことを$sR't$と定める。$s\in H$の長さを$n$とすると$n\geq1$であるから$m+1=n$を満たす$m\in\omega$が存在し、$R$の条件により$s(m)Rz$を満たす$z\in X$が存在する。$t(k)=s(k)$（$k<n$）および$t(n)=z$によって定まる長さ$n+1$の列$t$は$H$に属し、$sR't$を満たす。よって$H$と$R'$は(2)の条件を満たす。

(2)を$H$と$R'$に適用すると、すべての$n\in\omega$に対して$s_nR's_{n+1}$を満たす族$(s_n)_{n\in\omega}$が得られる。$s_0$の長さを$m_0$とすると、$s_n$の長さは$m_0+n$であり、$n\leq n'$ならば$s_{n'}$は$s_n$の定義域上で$s_n$と一致する。$k\in\omega$に対して$k<m_0+n$を満たす$n$を取り$x_k=s_n(k)$と定めると、この値は$n$の取り方に依存しない。$s_0\in H$であるから$x_0=s_0(0)=a$である。また各$k\in\omega$に対して$k+1<m_0+n$を満たす$n$を取ると、$s_n\in H$であるから$x_kRx_{k+1}$である。よって(1)が成り立つ。▨

証明.定理 2.1 (1)から(1)を示す。$X$を空でない集合、$R\subseteq X\times X$を、任意の$x\in X$に対して$xRy$を満たす$y\in X$が存在するという条件を満たす二項関係とし、$a\in X$とする。$x\in X$に対して$S_x=\{y\in X\mid xRy\}$とおくと$S_x\neq\emptyset$である。定理 2.1 (1)により族$(S_x)_{x\in X}$の選択関数が存在し、その値はすべて$X$に属するから、$xRc(x)$（$x\in X$）を満たす写像$c\colon X\to X$が得られる。§E1.17 定理 2.1により、$x_0=a$および$x_{n+1}=c(x_n)$（$n\in\omega$）を満たす族$(x_n)_{n\in\omega}$がただ一つ定まる。$x_nRc(x_n)=x_{n+1}$であるから、(1)が成り立つ。

(1)$\Rightarrow$(2)を示す。$(A_n)_{n\in\omega}$を空でない集合からなる族とし、$U=\bigcup_{n\in\omega}A_n$とおく。$Z=\{(n,a)\in\omega\times U\mid a\in A_n\}$とおくと、$Z$は§E1.13 定義 2.1による分出で得られる集合である。$A_0\neq\emptyset$であるから$a_{*}\in A_0$を取ることができ、$(0,a_{*})\in Z$であるから$Z\neq\emptyset$である。

$(n,a),(m,b)\in Z$に対して、$m=n+1$が成り立つことを$(n,a)T(m,b)$と定める。$(n,a)\in Z$とすると$A_{n+1}\neq\emptyset$であるから$b\in A_{n+1}$を取ることができ、$(n+1,b)\in Z$が$(n,a)T(n+1,b)$を満たす。よって$Z$と$T$は(1)の条件を満たす。

$(0,a_{*})$を第$0$項として(1)を適用すると、$Z$の元の族$((n_k,b_k))_{k\in\omega}$で、$(n_0,b_0)=(0,a_{*})$を満たし、すべての$k\in\omega$に対して$n_{k+1}=n_k+1$を満たすものが得られる。$n_0=0$であるから、$k$についての帰納法により$n_k=k$である。$(k,b_k)\in Z$であるから$b_k\in A_k$であり、族$(b_k)_{k\in\omega}$が(2)の結論を与える。▨

証明.(1)$\Rightarrow$(2)を示す。$X=\emptyset$の場合、$f\colon I\to X$が存在すれば$I=\emptyset$であり、$\emptyset$から$\emptyset$への空写像$s$が$f\circ s=\operatorname{id}_{X}$を満たす。$X\neq\emptyset$とする。$X$は高々可算であるから、§E1.18 定理 3.3により全射$e\colon\mathbb N_{\geq 0}\to X$が存在する。§E1.16 注意 4.10により$\mathbb N_{\geq 0}$は$\omega$に等しいから、$e$を$\omega$を定義域とする全射とみなす。$n\in\omega$に対して$A_n=f^{-1}(\{e(n)\})$とおくと、$f$が全射であるから$A_n\neq\emptyset$である。(1)により、$i_n\in A_n$（$n\in\omega$）を満たす族$(i_n)_{n\in\omega}$が存在する。$x\in X$に対して$e(n)=x$を満たす$n\in\omega$が存在し、$\omega$は所属関係について整列しているから、そのうち最小のものを$n(x)$と書くことができる。$s(x)=i_{n(x)}$によって写像$s\colon X\to I$を定めると、$s(x)\in A_{n(x)}=f^{-1}(\{x\})$であるから$f(s(x))=x$である。

(2)$\Rightarrow$(1)を示す。$(A_n)_{n\in\omega}$を空でない集合からなる族とし、$U=\bigcup_{n\in\omega}A_n$とおく。$I=\{(n,a)\in\omega\times U\mid a\in A_n\}$とおくと、$I$は§E1.13 定義 2.1による分出で得られる集合である。$f(n,a)=n$によって写像$f\colon I\to\omega$を定めると、各$A_n$が空でないから$f$は全射である。$\omega$は§E1.18 定義 1.2の意味で可算であり、とくに高々可算である。(2)により、$f\circ s=\operatorname{id}_\omega$を満たす写像$s\colon\omega\to I$が存在する。$s(n)$の第一成分は$f(s(n))=n$に等しいから$s(n)=(n,a_n)$と書くことができ、$I$の定義により$a_n\in A_n$である。よって族$(a_n)_{n\in\omega}$が(1)の結論を与える。▨