任意の集合上に全順序が存在する (Zornの補題の練習問題)
順序集合$P$の任意の空でない全順序部分集合が$P$において上界を持つとき、$P$は帰納的であるという。
空でない帰納的順序集合には極大元が存在する。
ツォルンの補題を使った証明はだいたいワンパターンで、存在を主張したい数学的対象と同種の数学的対象からなる順序集合を作り(以下の証明の[1])、その集合が補題の条件をみたすことを示し([2], [3])、補題によって存在が保証された極大元が求める数学的対象であることを証明して([4])、万事至れりとなる。
示すことが多いので、証明はだいたいゴチャゴチャして長くなりがちである(でも発想とか要らないので、地道にやってゆけば誰でも証明できる)。
$X$を任意の集合とする。$X$上に全順序が存在する。
[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$が得られた。（証明終）
