集合と関係 (8)Zornの補題
定理8(Zornの補題)
空でない順序集合$~(X,R)~$において、任意の鎖が上界をもつとき、$(X,R)~$は極大元をもつ。
$(X,R)~$を空でない順序集合とし、任意の鎖は上界をもつとする。
$(X,R)~$の鎖全体の集合を$~\mathcal{A}~$とおく。
空集合は鎖なので$~\emptyset\in\mathcal{A}~$となり、$\mathcal{A}\neq\emptyset~$である。
Tukeyの補題(定理7)より、順序集合$~(\mathcal{A},\subset)~$は極大元$~C~$をもつ。
さらに、仮定より$~C~$の上界$~b\in X~$が存在する。
$b~$が極大元でないと仮定すると、$bRy,b\neq y~$を満たす$~y\in X~$がとれる。
${}^{\forall}x\in C,xRb~$なので、$C\cup\{y\}~$は$~(X,R)~$の鎖である。
さらに、$C\subsetneq C\cup\{y\}~$となるが、これは$~C~$の極大性に矛盾する。
よって、$b~$は$~(X,R)~$における極大元である。
以上よりZornの補題が示された。
$$\square$$
$(X,R)~$の鎖全体の集合を$~\mathcal{A}~$とおく。
主張8.1
$\mathcal{A}~$は有限特性をもつ。
$A\in\mathcal{A}~$を任意にとると、$A~$は鎖なので、$A~$任意の部分集合は鎖となり$~\mathcal{A}~$に含まれる。
逆に、$A\notin\mathcal{A}~$とすると、$A~$は鎖ではないので$~R~$により比較ができない元$~a,a'\in A~$がとれる。
$\{a,a'\}\subset A~$を考えるとこれは有限部分集合であり、鎖ではないので$~\{a,a'\}\notin\mathcal{A}~$となる。
$$\square$$
逆に、$A\notin\mathcal{A}~$とすると、$A~$は鎖ではないので$~R~$により比較ができない元$~a,a'\in A~$がとれる。
$\{a,a'\}\subset A~$を考えるとこれは有限部分集合であり、鎖ではないので$~\{a,a'\}\notin\mathcal{A}~$となる。
空集合は鎖なので$~\emptyset\in\mathcal{A}~$となり、$\mathcal{A}\neq\emptyset~$である。
Tukeyの補題(定理7)より、順序集合$~(\mathcal{A},\subset)~$は極大元$~C~$をもつ。
さらに、仮定より$~C~$の上界$~b\in X~$が存在する。
$b~$が極大元でないと仮定すると、$bRy,b\neq y~$を満たす$~y\in X~$がとれる。
${}^{\forall}x\in C,xRb~$なので、$C\cup\{y\}~$は$~(X,R)~$の鎖である。
さらに、$C\subsetneq C\cup\{y\}~$となるが、これは$~C~$の極大性に矛盾する。
よって、$b~$は$~(X,R)~$における極大元である。
以上よりZornの補題が示された。
逆に、Zornの補題を仮定するとTukeyの補題を示すことができる。
$\mathcal{A}~$を有限特性をもつ空でない集合族とする。
任意に鎖$~\mathcal{C}\subset\mathcal{A}~$をとる。
任意の$~C\in\mathcal{C}~$について$~\displaystyle C\subset\bigcup\mathcal{C}~$となるのは明らかである。
補題6より、$\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$となるので$~\displaystyle\bigcup\mathcal{C}~$は$~\mathcal{C}~$の上界である。
任意の鎖$~\mathcal{C}\subset\mathcal{A}~$について上界が見つかったので、Zornの補題より$~(\mathcal{A},\subset)~$は極大元をもつ。
よって、Tukeyの補題は示された。
任意に鎖$~\mathcal{C}\subset\mathcal{A}~$をとる。
任意の$~C\in\mathcal{C}~$について$~\displaystyle C\subset\bigcup\mathcal{C}~$となるのは明らかである。
補題6より、$\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$となるので$~\displaystyle\bigcup\mathcal{C}~$は$~\mathcal{C}~$の上界である。
任意の鎖$~\mathcal{C}\subset\mathcal{A}~$について上界が見つかったので、Zornの補題より$~(\mathcal{A},\subset)~$は極大元をもつ。
よって、Tukeyの補題は示された。
つまり、Tukeyの補題とZornの補題は同値な命題であることがわかる。