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

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

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

• 反射律： $∀x∈X (x R x)$
• 反対称律： $∀x,y∈X (x R y ∧ y R x ⇒ x = y)$
• 推移律： $∀x,y,z∈X (x R y ∧ y R z ⇒ x R z)$

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

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

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

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

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

　　【3.a】反射律： $∀x∈X(x R' x)$
　任意の$R∈C$は反射的だから、任意の$x∈X$について、$(x,x)∈R⊆R'$となる。

　　【3.b】反対称律： $∀x,y∈X(x R' y ∧ y R' x ⇒ x = y)$
　$x R' y$、$y R' x$とすると、$(x,y)$及び$(y,x)$を$R'$が含むことから、$(x,y)∈R_1$、$(y,x)∈R_2$なる、$R_1,R_2∈C$が存在する。$C$は全順序集合なので$R_1⊆R_2$か$R_2⊆R_1$だが、$R_1⊆R_2$なら$R_2$を、$R_2⊆R_1$なら$R_1$を$R$とおく。すると$(x,y),(y,x)∈R$であり、$R$の反対称性より$x = y$となる。

　　【3.c】推移律： $∀x,y,z∈X(x R' y ∧ y R' z ⇒ x R' z)$
　$x R' y$、$y R' z$とすると、$(x,y)$及び$(y,z)$を$R'$が含むことから、$(x,y)∈R_1$、$(y,z)∈R_2$なる、$R_1,R_2∈C$が存在する。$C$は全順序集合なので$R_1⊆R_2$か$R_2⊆R_1$だが、$R_1⊆R_2$なら$R_2$を、$R_2⊆R_1$なら$R_1$を$R$とおく。すると$(x,y),(y,z)∈R$であり、$R$の推移性より$(x,z)∈R⊆R'$となる。

　よって、$R'∈P$である。

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

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

　背理法。$R_0$が全順序でないと仮定する。
　このとき、$t,u∈X$が存在して、$(t,u)∈R_0$にも$(u,t)∈R_0$にもならない。そこで$R_0'$を以下の通り定める：
　　　　$Δ := \{(x,y)∈X×X : x R_0 t ∧ u R_0 y\}$
　　　　$R_0' := R_0∪Δ$
　定義より$R_0⊆R_0'$。$R_0$は$P$の極大元だから、もし$R_0'∈P$であるとすれば、$R_0 = R_0'$となるはず。しかし$R_0≠R_0'$である。実際$(t,u)∈Δ$であり、$(t,u)∉R_0$だが$(t,u)∈R_0'$なので。これは矛盾。

　そこで$R_0'∈P$、つまり$R_0'$が順序の公理をみたすことを示せば証明が完成する。

　　【4.a】反射律： $∀x∈X(x R_0' x)$
　$R_0$の反射性より、任意の$x∈X$について$(x,x)∈R_0⊆R_0'$となる。

　　【4.b】反対称律： $∀x,y∈X(x R_0' y ∧ y R_0' x ⇒ x = y)$
　$R_0'$が反対称的でなければ、$(x,y),(y,x)∈R_0' ∧ x≠y$なる$x,y∈X$がある。$x≠y$と$R_0$の反対称性とより、$(x,y)∉R_0$か$(y,x)∉R_0$である。
　$(x,y)∉R_0$のとき、$(x,y)∈Δ$なので、$x R_0 t$かつ$u R_0 y$である。ここで$(y,x)∈R_0$なら、$u R_0 y ∧ y R_0 x ∧ x R_0 t$と$R_0$の推移性とより$u R_0 t$が言えて、$(u,t)∉R_0$に反する。他方$(y,x)∉R_0$なら、$(y,x)∈Δ$で、$u R_0 x$。$u R_0 x ∧ x R_0 t$と$R_0$の推移性とより$u R_0 t$となり、同様に矛盾する。
　$(y,x)∉R_0$のときも同様。

　　【4.c】推移律： $∀x,y,z∈X(x R_0' y ∧ y R_0' z ⇒ x R_0' z)$
　$R_0'$が推移的でなければ、$(x,y),(y,z)∈R_0'$かつ$(x,z)∉R_0'$であるような、$x,y,z∈X$がある。$(x,z)∉R_0'$なので$(x,z)∉Δ$であり、$x R_0 t$でないか$u R_0 z$でないかである(★)。また、$R_0'⊇R_0$なので$(x,z)∉R_0$でもあり、$R_0$の推移性より、$(x,y)∉R_0$か$(y,z)∉R_0$である。

　　　　【4.c.i】$(x,y)∉R_0$の場合
　このとき$(x,y)∈Δ$なので、$x R_0 t$かつ$u R_0 y$である。$x R_0 t$なので、(★)より$u R_0 z$でない。
　$(y,z)∈R_0$であるとすれば、$u R_0 y ∧ y R_0 z$と$R_0$の推移性とより、$u R_0 z$となって矛盾する。
　$(y,z)∈R_0$でないとすれば、$(y,z)∈Δ$で、やはり$u R_0 z$となって矛盾する。

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

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