Zornの補題

Zornの補題

集合Xにおける関係≦が、 (1) x≦x、 (2) x≦y, y≦z ⇒ x≦z、 (3) x≦y, y≦x ⇒ x=y を満たすとき、(X;≦)を順序集合といいます。 Xの元x,yがx≦yまたはy≦xを満たすときx,yは比較可能であるといいます。 Xの任意の2元が比較可能であるとき、(X;≦)は全順序集合または鎖であるといいます。 Y⊆Xとすると(Y;≦)も順序集合となります。 (Y;≦)が鎖のとき(X;≦)に含まれる鎖といいます。 Y⊆Xに対して、a∈Xが任意のx∈Yに対してx≦aとなるとき、 aをYの上界といいます。 Yの上界全体の集合をu.b.Yと書きます。 u.b.Y≠φのとき、Yは上に有界であるといいます。

集合Xの部分集合全体の集合をXのべき集合といい、P(X)と書きます。

命題(Zornの補題) (X;≦)は順序集合とし、それに含まれる任意の鎖は上に有界であるとすると、 Xには極大元が存在する。

定義 GをXに含まれる鎖全体の集合とします。 (G={C∈P(X)|任意のx,y∈Cは比較可能}) f:G→Gを次のように定義します。

選出公理により、g:P(X)-{φ}→Xで Xの空でない各部分集合Aに対しg(A)∈Aとなるものがあります。 C∈Gとすれば仮定によりu.b.C≠φ。 もしu.b.C-C≠φならば、f(C)=C∪{g(u.b.C-C)}とします。 (f(C)∈Gとなります。) u.b.C-C=φならば、f(C)=Cとします。

f(C)=Cとすると、u.b.C⊆Cとなります。 x0∈u.b.Cとします。 もしx0<x∈Xとなるxがあったとすれば x∈u.b.C-Cとなってu.b.C-C=φに反するからx0はXの極大元となります。

定義 Gの部分集合Tで次の3条件を満たすものを塔といいます。 (i) φ∈T, (ii) C∈T⇒f(C)∈T, (iii) Tの部分集合Dで(D;⊆)が鎖をなすならば、∪C∈DC∈Tとなる。

Gは塔である。

証明 (i) φの任意の2元は比較可能なので、φ∈G。

(ii) C∈Gとすると、f(C)の定義よりf(C)∈G。

(iii) D⊆Gとし、(D;⊆)は鎖をなしているとすれば、 Dの元全体の和集合はGの元となることを示します。 x, x'∈∪C∈DCが比較可能であることを示せばよい。 x∈C, x'∈ C', C, C'∈D となるようなC, C'が存在します。 (D;⊆)は鎖であるから、C⊆C'またはC'⊆C。 C'⊆Cとすればx, x'∈Cとなり、 x, x'は比較可能となります。 C⊆C'とすればx, x'∈C'となり、 x, x'は比較可能となります。

すべての塔の共通部分T0は最小の塔となる。

証明 (i) 任意の塔Tに対してφ∈Tなので φ∈∩Tは塔T=T0となります。

(ii) C∈∩Tは塔T=T0とすると 任意の塔Tに対してC∈Tとなるのでf(C)∈Tとなります。 f(C)∈∩Tは塔T=T0となります。

(iii) D⊆T0=∩Tは塔Tとし、 (D;⊆)は鎖をなしているとすれば、 Dの元全体の和集合はT0の元となることを示します。 任意の塔Tに対してD⊆Tであり(D;⊆)は鎖をなしているので ∪C∈DC∈Tとなります。 よって∪C∈DC∈∩Tは塔T=T0となります。

(T0;⊆)は鎖となる。

証明 T0のどの元とも比較可能な T0の元全体の集合をSとし、 S=T0を示せばよい。 (φ∈SだからS≠φ)

(1) C'∈SのときV(C')={C∈T0|C⊆C'またはp(C')⊆C} とおけばV(C')は塔となる。

証明 (i) φ⊆C'なのでφ∈V(C')となります。

(ii) C∈V(C')ならばC⊆C'またはp(C')⊆C。 C⊆C'ならばC=C'またはC⊂C'。 C=C'ならばf(C')=f(C)。 C⊂C'とします。 T0は塔でC∈T0であるからf(C)∈T0。 Sの定義からC'⊆f(C)またはf(C)⊆C'。 C'⊆f(C)とするとC⊂C'だからf(C)=Cとはならないので、 f(C)=C∪{x}となるxが存在します。 C⊂C'⊆f(C)=C∪{x}となるので、f(C)=C'。 よってf(C)⊆C'。 f(C')⊆CならばC⊆f(C)からf(C')⊆f(C)。

(iii) D⊆V(C'), (D;⊆)は鎖とします。 D'=∪C∈DCとおきます。 すべてのC∈Dが、C⊆C'とすると、D'⊆C'となります。 あるC∈Dが、C⊆C'ではないとすると、C∈V(C')であることから、 f(C')⊆Cとなり、f(C')⊆C⊆D'となります。

(2) Sは塔となる。

証明 (i) 任意のC∈T0に対してφ⊆Cなので、φ∈Sとなります。

(ii) (1)よりT0=V(C')。 T0の任意の元CとSの任意の元C'に対して C⊆C'またはf(C')⊆Cとなります。 C⊆C'のときはC⊆f(C')となりf(C')∈S。

(iii) D⊆S, (D;⊆)は鎖とします。 D'=∪C∈DCとおきます。C'∈C(X)とします。 すべてのC∈Dが、C⊆C'とすると、D'⊆C'となります。 あるC∈Dが、C⊆C'ではないとすると、C∈Sであることから、 C'⊆Cとなり、C'⊆C⊆D'となります。

T0が塔になること、 T0が鎖になることの証明を詳しく見てみます。

T0が塔になることの証明

Xを集合、O⊆Xとします。 G⊆P(X)、 P⊆P(G)で

をみたすものとします。 f: G→G を をみたすものとします。 と定義すると以下のことが成り立ちます。

次のように定義します。

T0∈T*

証明 (i) T0∈T1
Y∈T1 (∀Y∈T*)
⇔ Init(Y)∈Y (∀Y∈T*)
⇒ ∩{Init(Y)|Y∈T*}⊆∩T*
⇒ Init(∩T*)⊆∩T*
⇔ ∩T*∈T1
⇒ T0∈T1

(ii) T0∈T2
Y∈T2 (∀Y∈T*)
⇔ Suc(Y)⊆Y (∀Y∈T*)
⇒ ∩{Suc(Y)|Y∈T*}⊆∩T*
⇒ Suc(∩T*)⊆∩T*
⇔ ∩T*∈T2
⇒ T0∈T2

(iii) T0∈T3
Y∈T3 (∀Y∈T*)
⇔ Lim(Y)⊆Y (∀Y∈T*)
⇒ ∩{Lim(Y)|Y∈T*}⊆∩T*
⇒ Lim(∩T*)⊆∩T*
⇔ ∩T*∈T3
⇒ T0∈T3

T0が鎖になることの証明

次のように定義します。

次のことが成り立ちます。

∀C∈G(C∈S ⇒ T0∩V(C)∈T*)

証明 (i) T0∩V(C)∈T1
O⊆C
⇔ O∈L(C)
⇒ O∈V(C)
⇔ V(C)∈T1
⇒ T0∩V(C)∈T1

(ii) T0∩V(C)∈T2
Suc(V(C))=Suc(L(C)∪U(f(C)))=Suc(L(C))∪Suc(U(f(C)))
Suc(U(f(C)))⊆U(f(C))
Suc(T0)⊆T0⊆S(C)
Suc(T0∩V(C))⊆S(C)∩(Suc(L(C))∪Suc(U(f(C)))) =L(C)∪(U(C)∩Suc(L(C)))∪U(f(C))⊆V(C)
⇒ T0∩V(C)∈T2

(iii) T0∩V(C)∈T3
Lim(L(C)∪U(f(C)))⊆L(C)∪U(f(C))
⇔ Lim(V(C))⊆V(C)
⇔ V(C)∈T3
⇒ T0∩V(C)∈T3

T0∩S∈T*

証明 (i) T0∩S∈T1
O⊆C (∀C∈T0)
⇔ O∈L(C) (∀C∈T0)
⇒ O∈S(C) (∀C∈T0)
⇔ O∈∩{S(C)|C∈T0}=S
⇔ S∈T1
⇒ T0∩S∈T1

(ii) T0∩S∈T2
{f(C)}⊆{D∈G|V(C)⊆S(D)}⊆{D∈G|T0⊆S(D)}=S (∀C∈S)
⇒ Suc(S)={f(C)|C∈S}⊆S
⇔ S∈T2
⇒ T0∩S∈T2

(iii) T0∩S∈T3
Lim(L(C)∪U(C))⊆L(C)∪U(C) (∀C∈G)
⇔ Lim(S(C))⊆S(C) (∀C∈G)
⇔ S(C)∈T3 (∀C∈G)
⇒ S=∩{S(C)|C∈T0}∈T3
⇒ T0∩S∈T3