任意の集合上に全順序が存在する (Zornの補題の練習問題)

[1] $X$上の順序関係全体が順序集合になること

　$X$上の2項関係$R$が順序関係であるとは、次の順序の公理をみたすこと：

• 反射律： $\forall x\in X(xRx)$
• 反対称律： $\forall x,y\in X(xRy\wedge yRx\Rightarrow x=y)$
• 推移律： $\forall x,y,z\in X(xRy\wedge yRz\Rightarrow xRz)$

　$X$上の任意の2項関係は、$X\times X$の部分集合である。そこで、$X$上の順序関係全体の集合$P$は
　　　　$P:=\{R\in 2^{X\times X}:R$は$X$上の反射的・反対称的・推移的関係$\}$
として定義され、分出公理によって$P$は集合になる。
　$P$上の包含関係$\subseteq$は$2^{X\times X}$上の包含順序の部分関係であり、$(P,\subseteq )$は順序集合になる。

[2] $P$が空でないこと

　$X$上の関係$\mathrm{Eq}\subseteq X\times X$を以下で定義する：
　　　　$\mathrm{Eq}:=\{(x,x):x\in X\}$
　このとき明らかに$\mathrm{Eq}$は順序の公理をみたすから、$\mathrm{Eq}\in P\ne \varnothing$である。

[3] $(P,\subseteq )$が帰納的であること

　$C$を$P$の空でない全順序部分集合とする。$R^{\prime }\subseteq X\times X$を以下で定義する：
　　　　$R^{\prime }:=\bigcup _{R\in C}R$
　任意の$R\in C$について$R\subseteq R^{\prime }$だから、$R^{\prime }$は$C$の上界。そこで$R^{\prime }\in P$、つまり$R^{\prime }$が順序の公理をみたすことを示せばよい。

　　【3.a】反射律： $\forall x\in X(x{R}^{\prime }x)$
　任意の$R\in C$は反射的だから、任意の$x\in X$について、$(x,x)\in R\subseteq R^{\prime }$となる。

　　【3.b】反対称律： $\forall x,y\in X(x{R}^{\prime }y\wedge y{R}^{\prime }x\Rightarrow x=y)$
　$x{R}^{\prime }y$、$y{R}^{\prime }x$とすると、$(x,y)$及び$(y,x)$を$R^{\prime }$が含むことから、$(x,y)\in R_1$、$(y,x)\in R_2$なる、$R_1,R_2\in C$が存在する。$C$は全順序集合なので$R_1\subseteq R_2$か$R_2\subseteq R_1$だが、$R_1\subseteq R_2$なら$R_2$を、$R_2\subseteq R_1$なら$R_1$を$R$とおく。すると$(x,y),(y,x)\in R$であり、$R$の反対称性より$x=y$となる。

　　【3.c】推移律： $\forall x,y,z\in X(x{R}^{\prime }y\wedge y{R}^{\prime }z\Rightarrow x{R}^{\prime }z)$
　$x{R}^{\prime }y$、$y{R}^{\prime }z$とすると、$(x,y)$及び$(y,z)$を$R^{\prime }$が含むことから、$(x,y)\in R_1$、$(y,z)\in R_2$なる、$R_1,R_2\in C$が存在する。$C$は全順序集合なので$R_1\subseteq R_2$か$R_2\subseteq R_1$だが、$R_1\subseteq R_2$なら$R_2$を、$R_2\subseteq R_1$なら$R_1$を$R$とおく。すると$(x,y),(y,z)\in R$であり、$R$の推移性より$(x,z)\in R\subseteq R^{\prime }$となる。

　よって、$R^{\prime }\in P$である。

　さて、以上[1]～[3]より$(P,\subseteq )$は空でない帰納的順序集合であり、Zornの補題により$(P,\subseteq )$は極大元を有するが、そのひとつを$R_0$と書く。

[4] $R_0$が$X$上の全順序関係であること

　背理法。$R_0$が全順序でないと仮定する。
　このとき、$t,u\in X$が存在して、$(t,u)\in R_0$にも$(u,t)\in R_0$にもならない。そこで$R_0^{\prime }$を以下の通り定める：
　　　　$\Delta :=\{(x,y)\in X\times X:x{R}_{0}t\wedge u{R}_{0}y\}$
　　　　$R_0^{\prime }:=R_0\cup \Delta$
　定義より$R_0\subseteq R_0^{\prime }$。$R_0$は$P$の極大元だから、もし$R_0^{\prime }\in P$であるとすれば、$R_0=R_0^{\prime }$となるはず。しかし$R_0\ne R_0^{\prime }$である。実際$(t,u)\in \Delta$であり、$(t,u)\notin R_0$だが$(t,u)\in R_0^{\prime }$なので。これは矛盾。

　そこで$R_0^{\prime }\in P$、つまり$R_0^{\prime }$が順序の公理をみたすことを示せば証明が完成する。

　　【4.a】反射律： $\forall x\in X(x{R}_0^{\prime }x)$
　$R_0$の反射性より、任意の$x\in X$について$(x,x)\in R_0\subseteq R_0^{\prime }$となる。

　　【4.b】反対称律： $\forall x,y\in X(x{R}_0^{\prime }y\wedge y{R}_0^{\prime }x\Rightarrow x=y)$
　$R_0^{\prime }$が反対称的でなければ、$(x,y),(y,x)\in R_0^{\prime }\wedge x\ne y$なる$x,y\in X$がある。$x\ne y$と$R_0$の反対称性とより、$(x,y)\notin R_0$か$(y,x)\notin R_0$である。
　$(x,y)\notin R_0$のとき、$(x,y)\in \Delta$なので、$x{R}_{0}t$かつ$u{R}_{0}y$である。ここで$(y,x)\in R_0$なら、$u{R}_{0}y\wedge y{R}_{0}x\wedge x{R}_{0}t$と$R_0$の推移性とより$u{R}_{0}t$が言えて、$(u,t)\notin R_0$に反する。他方$(y,x)\notin R_0$なら、$(y,x)\in \Delta$で、$u{R}_{0}x$。$u{R}_{0}x\wedge x{R}_{0}t$と$R_0$の推移性とより$u{R}_{0}t$となり、同様に矛盾する。
　$(y,x)\notin R_0$のときも同様。

　　【4.c】推移律： $\forall x,y,z\in X(x{R}_0^{\prime }y\wedge y{R}_0^{\prime }z\Rightarrow x{R}_0^{\prime }z)$
　$R_0^{\prime }$が推移的でなければ、$(x,y),(y,z)\in R_0^{\prime }$かつ$(x,z)\notin R_0^{\prime }$であるような、$x,y,z\in X$がある。$(x,z)\notin R_0^{\prime }$なので$(x,z)\notin \Delta$であり、$x{R}_{0}t$でないか$u{R}_{0}z$でないかである(★)。また、$R_0^{\prime }\supseteq R_0$なので$(x,z)\notin R_0$でもあり、$R_0$の推移性より、$(x,y)\notin R_0$か$(y,z)\notin R_0$である。

　　　　【4.c.i】$(x,y)\notin R_0$の場合
　このとき$(x,y)\in \Delta$なので、$x{R}_{0}t$かつ$u{R}_{0}y$である。$x{R}_{0}t$なので、(★)より$u{R}_{0}z$でない。
　$(y,z)\in R_0$であるとすれば、$u{R}_{0}y\wedge y{R}_{0}z$と$R_0$の推移性とより、$u{R}_{0}z$となって矛盾する。
　$(y,z)\in R_0$でないとすれば、$(y,z)\in \Delta$で、やはり$u{R}_{0}z$となって矛盾する。

　　　　【4.c.ii】$(y,z)\notin R_0$の場合
　このときも【4.c.i】とほぼ同様にして矛盾が示せる。

　以上[1]～[4]より、$X$上の全順序関係$R_0$が得られた。（証明終）