Zornの補題・極大原理 : 選択公理

Zorn

の補題・極大原理と選択公理

alg-d

http://alg-d.com/math/ac/

2015

年

12

月

20

日

4. Rがconnected ⇐⇒ xRyまたはx = yまたはyRx

5. Rが前順序関係⇐⇒ Rが反射的かつ推移的 6. Rが順序関係⇐⇒ Rが反対称的な前順序関係 7. Rが全順序関係_{⇐⇒ R}がconnectedな順序関係 8. x ∈ Xが極大元⇐⇒任意のy∈ X に対して「xRyならばyRx」 9. x ∈ Xが最小元⇐⇒任意のy∈ X \ {x}に対してxRy 10. x ∈ XがY ⊂ X の上界_⇐⇒任意のy ∈ Y \ {x}に対してyRx 11. Rが整列順序関係_{⇐⇒ R}が順序関係で，任意のY (̸= ∅) ⊂ X に対して(Y, R)が 最小元を持つ． 12. X が有限性を持つ⇐⇒「x ∈ X ⇐⇒任意の有限部分集合y⊂ xに対してy∈ X」 13. x ∈ Xに対してx↓ :={y ∈ X | yRx} 14. Y ⊂ X が鎖⇐⇒ (Y, R)が全順序集合 15. R−1 :={⟨a, b⟩ ∈ X × X | ⟨b, a⟩ ∈ R} 16. R :={⟨a, b⟩ ∈ X × X | ⟨a, b⟩ /∈ R} 17. I := {⟨a, a⟩ ∈ X × X | a ∈ X} 定義. (X,≤)を順序集合とする． 1. Y ⊂ X が反鎖⇐⇒任意のx, y ∈ Y に対して「x̸= yならばx̸≤ y, y ̸≤ x」

2. (X,≤)がramified ⇐⇒任意の元x∈ X に対し(x↓,≤)が鎖になる 定理 1. 次の命題は(ZF上)同値． 1. Zornの補題． 2. 集合X 上の推移的関係Rに対して極大鎖Y ⊂ Xが存在する． 3. 順序集合(X,⊂)は極大鎖を持つ． 4. 順序集合(X,⊂)が「任意の鎖C ⊂ X に対してあるx ∈ X が存在して，任意の y∈ Cに対してy ⊂ x」を満たすならば，X の極大元が存在する． 5. 順序集合(X,⊂)が「任意の鎖C ⊂ X に対して ∪ y∈C y∈ X」を満たすならばX は 極大元を持つ． 6. 有限性をもつ非空集合X は(⊂に関する)極大元をもつ．(Tukeyの補題) 7. 任意の前順序集合(X,≤)は極大鎖を持つ．

8. 任意の順序集合(X,≤)は極大鎖を持つ．(Hausdorff’s Maximal chain Condition)

9. 任意の順序集合(X,≤)の任意の鎖は，X のある極大鎖に含まれる．

10. 任意の前順序集合(X,≤)は極大反鎖を持つ．

11. 任意の順序集合(X,≤)は極大反鎖を持つ．(Kurepa’s Maximal Antichain Con-dition) 証明. (1 =⇒ 2) Rを集合X 上の推移的関係とする．L :={Y ⊂ X | (Y, R)は鎖}とし て，⊂でLに順序を入れる．この(L,⊂)はZornの補題の仮定を満たす． . ..) C ⊂ Lを鎖として，Z := ∪ Y∈C Y と置く．(Z, R)が全順序集合である事を示す． (i)反射律 任意のx ∈ Z を取る．Z の定義よりあるY ∈ C が存在してx ∈ Y となる．よって (Y, R)が順序集合であることよりxRxである． (ii)反対称律 x, y ∈ Z に対し xRy かつyRx であるとする．Z の定義と C が鎖であることから x, y ∈ Y となるY ∈ C の存在が分かる．このとき(Y, R)が順序集合であることより x = y． (iii)推移律 Rが推移的関係であることから明らか． (iv) connected x, y ∈ Z を取る．Z の定義とC が鎖であることからx, y ∈ Y となるY ∈ C の存在

が分かる．このとき(Y, R)の全順序性からxRyまたはyRxである． 以上より(Z, R)は全順序である．故にZ ∈ L．従ってZ はCの上界である． よってZornの補題より極大元Y ∈ Lが存在するが，これが極大鎖である． (2 =⇒ 3) ⊂は推移的だから，仮定2より_⊂によって全順序付けされる極大部分集合が 存在するが，これは明らかに(X,⊂)の極大鎖である． (3 =⇒ 4) 仮定3より極大鎖Y ⊂ X が存在する．このY に4の仮定を適用すると，あ るx ∈ X が存在して，任意のy∈ Y に対してy ⊂ xとできる．このxがX の極大元で ある． (4 =⇒ 5) 明らか． (5 =⇒ 6) X が有限性を持つとする．順序集合(X,⊂)が5の仮定を満たすことを示せ ばよい．C _{⊂ X} を鎖としてx := ∪ y∈C yと置く．z _{⊂ x}を任意の有限部分集合とする．x の定義とz が有限集合であることからz ⊂ y1∪ y2∪ · · · ∪ ynとなるyi ∈ Cが存在する． (C,⊂)が全順序であるからy := max{y1, y2,· · · , yn}が存在してz ⊂ y となることが分 かる．y_{∈ C ⊂ X}，即ちy ∈ X だからXが有限性を持つ事よりz ∈ X である． 従って再びX が有限性を持つ事からx∈ X である． (6 =⇒ 7) C := {Y ⊂ X | Y は鎖 }は空ではない．明らかにC は有限性を持つので， Tukeyの補題より極大元を持つ． (7 =⇒ 8)は明らか． (8 =⇒ 9) C ⊂ X を鎖とする． Y :={y ∈ X |任意のx∈ C に対してx ≤ yまたはy≤ x} とする．明らかにC ⊂ Y である．(Y,≤)は順序集合だから，仮定 8より極大鎖D ⊂ Y を持つ．C ⊂ Dである． . ..) C ̸⊂ Dと仮定する．x∈ C \ D が取れる．Dの極大性よりD∪ {x} ⊂ Y は鎖で はない．故にあるy ∈ D ⊂ Y が存在してx ̸≤ y かつy ̸≤ xとなるが，それはY の 定義に矛盾する． 鎖Ce ⊂ X がD ⊂ eC を満たすとする．するとC ⊂ D ⊂ eC だから Y の定義により e C ⊂ Y である．即ちCeはY の鎖でもある．故にDの極大性によりC = De である．即 ちDはCを含むXの極大鎖である． (9 =⇒ 8)明らか． (8 =⇒ 1) Zornの補題と同値な整列可能定理を示す．その為に X を任意の集合とし

A :={f : α −→ A | αは順序数でf は単射}と置く．(A,⊂)は順序集合である．よって 極大鎖C を持つ．するとg := ∪ f∈C f はある順序数からX への単射である．C の極大性 からgは全射．故にX は整列可能である． (6 =⇒ 10) C := {Y ⊂ X | Y は反鎖}は空でない．明らかにC は有限性を持つので， Tukeyの補題より極大元を持つ． (10 =⇒ 11) 明らか． (11 =⇒ 1) Zornの補題と同値な整列可能定理を示す．その為に，整列可能定理と同値 な「全順序集合は整列可能」を示す． ※ 整列可能定理についての定理1を参照．

(X,≤)を全順序集合とする．A :={(Y, y) | Y ⊂ X, y ∈ Y }と置き，Aの順序を

(Y, y)≤ (Z, z) ⇐⇒ Y = Z かつy≤ z で定める．(y ≤ z はX の順序である．) 仮定11より極大反鎖C ⊂ Aが存在する．X は全順序だから，明らかに C = {(Y, f(Y )) | Y ∈ P(X) \ {∅}} と書ける．この f は P(X) \ {∅}の選択関数である．よって選択公理から整列可能定理を導くのと同様にして X が整列可能なことが分かる． ※ 整列可能定理とZornの補題の定理1を参照． 定義. Xを集合とする．便宜上，次のように定める． 1. (X, R)が関係_{⇐⇒ R}はX 上の二項関係 2. (X, R)が推移⇐⇒ RはX 上の推移的関係 3. (X, R)が反対称_{⇐⇒ R}はX 上の反対称的関係 4. (X, R)が連結_{⇐⇒ R}はX 上のconnectedな関係 5. (X, R)が順序⇐⇒ (X, R)は順序集合 6. (X, R)が全⇐⇒ (X, R)は全順序集合 7. (X, R)が整列_{⇐⇒ (X, R)}は整列順序集合 8. (X, R)が有向⇐⇒ (X, R)は有向順序集合 9. (X, R)が分岐⇐⇒ (X, R)はramifiedな順序集合 10. (X, R)が森_{⇐⇒ (X, R)}は順序で，任意のx∈ X に対し(x↓, R)が整列順序集合 11. (X, R)が木⇐⇒ (X, R)が森で，最小元を持つ

12. (X, R)が推連⇐⇒ (X, R)は推移かつ連結である 13. (X, R)が反連_{⇐⇒ (X, R)}は反対称かつ連結である 以上のように定めたとき，MP(P, Q)で命題 X は任意の集合で，(X, R)はP であるとする．もし 任意のY ⊂ X に対して「(Y, R)がQになるならばY はX に上界を持つ」 が成り立つならば，X は極大元を持つ． を表す．例えばMP(順序, 全)はZornの補題である． 定理 2. Zornの補題⇐⇒ MP(推移, 整列) 証明. ⇐=は明らか．逆=⇒を示す．その為に定理1の2を用いる． Rを集合X 上の推移的関係とし，任意の部分整列順序は上界を持つとする．部分集合 Y ⊂ X に対してY⇓ := ∪ y∈Y y↓ ={z ∈ X |あるy ∈ Y が存在してzRy}と書くことにす る．_{W := {Y ⊂ X | (Y, R)}は整列順序集合_}と置く．_W 上の関係_≤を Y ≤ Z ⇐⇒ Y ⊂ ZかつZ∩ Y⇓⊂ Y と定める．≤はW の推移的関係である． . ..) Y ≤ ZかつZ ≤ W であるとする．即ちY ⊂ Z ⊂ W, Z∩Y⇓ ⊂ Y, W ∩Z⇓ ⊂ Z である．よってY ⊃ Z ∩ Y⇓ ⊃ (W ∩ Z⇓)∩ Y⇓ = W ∩ Y⇓ となるからY ≤ W で ある． 故に定理1の2により極大鎖_{V ⊂ (W, ≤)}が存在する．Z := ∪ Y∈V Y とする．明らかに (Z, R)は順序集合である．任意のA(̸= ∅) ⊂ Z を取る．Z の定義からあるY ∈ V が存在 してY∩A ̸= ∅である．Y _{∈ V ⊂ W}だから，(Y, R)は整列順序．よってx := min(Y ∩A)

が存在する．このxはAの最小元でもある． . ..) y ∈ A, y ̸= xとする． (i) y ∈ Y のとき．明らかにxRyである． (ii) y /∈ Y のとき．あるY′ ∈ V についてy ∈ Y′となるが，(V, ≤)は鎖であるから Y ≤ Y′でなければならない．従ってY′∩ Y⇓ ⊂ Y であるからy /∈ Y⇓である．よっ て，x∈ Y だから¬yRxである．x, y ∈ Y′ で(Y′, R)が鎖であることからxRyでな けらばならない． (i)(ii)よりxはAの最小元である．

よって (Z, R) は整列順序集合である事が分かる．故に Z ∈ W である．この Z は (W, ≤)の極大元である． . ..) W ∈ W が Z ≤ W を満たすとする．Z の定義から，任意の Y ∈ V に対し Y ≤ Z，よってY ≤ W である．即ちV ∪ {W }は(W, ≤)の鎖である．V の極大性 から_{V = V ∪ {W }}となる，従ってW ∈ V，よってW ≤ Z となる．即ちZ は極大 元である． (Z, R) ⊂ Xは整列順序だったから，MP(推移, 整列)の仮定によりZ の上界x ∈ X が 存在する． y ∈ X がxRyを満たすとする．勿論yはZ の上界である．yRzとなるz ∈ Z が存在 する． . ..) 「全てのz ∈ Z に対し ¬yRz」と仮定する．(Z ∪ {y}, R)は整列順序だから， Z ∈ W の極大性からZ = Z∪ {y}である．従ってy∈ Z，故に_¬yRyである．一方

xがZ の上界であることからyRxであり，ゆえにxRyからyRyとなり矛盾する．

このとき推移律からxRz である．するとxがZ の上界であることからz = xまたは zRxであるが，どちらにしてもyRx である．従ってxが(X, R)の極大元であることが 分かった． 定理 3. P, Qが次のいずれかであるとき，MP(P, Q)はZornの補題と同値である． P =推移,順序,分岐,森 Q =連結,反連,推連,全,有向,整列 証明. まず，定理2 で示したように Zornの補題 ⇐⇒ MP(推移, 整列) である．次に， MP(森, 有向) =⇒ MP(森, 連結)である． . ..) (X,≤)を森とし，X の任意の部分連結集合が上界を持つとする．Y ⊂ X を部 分有向集合とする．x, y _{∈ Y} とすると，Y は有向集合だからあるz ∈ Y が存在して x≤ z, y ≤ z である．よってx, y∈ z↓ ⊂ Xであり，今Xは森だからz↓は整列順序 集合．故にx≤ yまたはy≤ xである．即ち，Y は連結である．従って上界を持つ． 故に仮定のMP(森, 有向)からXは極大元を持つ． P =⇒ P′, Q =⇒ Q′ であればMP(P′, Q) =⇒ MP(P, Q)，MP(P, Q) =⇒ MP(P, Q′)

である．またP =⇒ QであることをP −→ Qと書いて図示すると次のようになる． 整列 全 森 推連 反連 有向 分岐 順序 推移 連結 反対称 任意 以上により次の図式が分かる． 選択公理 MP(推移,整列) MP(推移,全) MP(推移,推連) MP(推移,有向) MP(推移,反連) MP(推移,連結) MP(推移,整列) MP(推移,全) MP(推移,推連) MP(推移,有向) MP(推移,反連) MP(推移,連結) MP(分岐,整列) MP(分岐,全) MP(分岐,推連) MP(分岐,有向) MP(分岐,反連) MP(分岐,連結) MP(森,整列) MP(森,全) MP(森,推連) MP(森,有向) MP(森,反連) MP(森,連結) よって後はMP(森, 連結) =⇒ MP(推移, 整列)を示せばよい． (X, R) を推移とし，X の任意の部分整列順序が上界を持つとする．W := {Y ⊂ X | (R,≤)は整列順序_}と置く．_W の二項関係_≤を Y ≤ Z ⇐⇒ Y = Zまたはあるz ∈ Z が存在してY = z↓ と定める．すると(W, ≤)は森である．連結部分集合V ⊂ W を取ると，明らかに ∪ Y∈V Y が_V の上界である．故にMP(森, 連結)により_W は極大元Y ∈ W を持つ．Y _{⊂ X} は 部分整列順序だから，上界x∈ X を持つ．このxがXの極大元である．故にMP(推移, 整列)が示された．

定理 4. Zornの補題⇐⇒ MP(有向, 整列) 証明. (=⇒) MP(推移, 整列) =⇒ MP(有向, 整列)であるから明らか． (⇐=) MP(有向, 整列) =⇒ MP(森, 整列)を示せばよい． (X,≤)を森として，Xの部分整列順序は上界を持つとする． X は整列可能でないと仮定する．W := {(Y, R) | Y ⊂ X, (Y, R) は整列順序}と置 く．_W の順序_⊏を (Y, R)⊏ (Z, S) ⇐⇒ Y ⊊ Z または(Y = ZかつR = S) で定める．(W, ⊏)は有向集合である． . ..) (Y, R), (Z, S) ∈ Wとする． (i) Y ̸= Z のとき． V := Y ∪ Z として，V 上の整列順序T を aT b ⇐⇒    a, b∈ Y かつaRb または a, b∈ Z \ Y かつaSb または a ∈ Y かつb∈ Z \ Y で定めれば(V, T ) ∈ W, (Y, R) ⊏ (V, T ), (Z, S) ⊏ (V, T )である． (ii) Y = Z のとき． Xは整列可能でないから，Y ⊊ Xである．そこでx∈ X\Y を一つ取りV := Y∪{x} と置く．V 上の整列順序T を aT b ⇐⇒ (a, b ∈ Y かつaRb)またはb = x で定めれば(V, T ) ∈ W, (Y, R) ⊏ (V, T ), (Z, S) ⊏ (V, T )である． V ⊂ (W, ⊏) を 部 分 整 列 順 序 と す る ．Z := ∪ (Y,R)∈V Y と 置 く ．z _{∈ Z} に 対 し て (Yz, Rz) :=⊏-min{(Y, R) ∈ V | z ∈ Y }とする．Z の順序Sを zSw⇐⇒ ((Yz, Rz)⊏ (Yw, Rw)かつYz ̸= Yw)または((Yz, Rz) = (Yw, Rw)かつzRzw) で定めると，(Z, S)は整列順序である．故に(Z, S)∈ W はVの上界である．故に仮定の MP(有向, 整列)により(W, ⊏)は極大元(Y, R)を持つ．このとき明らかにY = X であ り，X が整列可能でないことに矛盾する． 従って X は整列可能である．(X, R)を整列順序とする．|λ| ̸≤ |X| を満たす順序数λ

を取る．X に含まれない元∞ /∈ X を一つ取っておく．f : λ−→ X ∪ {∞}を f (α) :=    R- min{x ∈ X \ {f(β) | β < α}任意のβ < αに対してf (β)≤ x} (このような最小元が存在するとき) ∞ (最小元が存在しないとき) で定める．f の定義から，f (α) = f (β)̸= ∞ならばα = βである．λの取り方からf は 単射でないので，f (α) =∞となるα < λは存在する．そこでγ := min{α < λ | f(α) = ∞}と置く．Y :=_{{f(β) | β < γ}}とすればY ⊂ (X, ≤)は部分整列順序である．故に上 界x∈ X を持つ．このときxが極大元である． 定理 5. 次の命題は(ZF上)同値． 1. Zornの補題． 2. 順序集合X が「X の部分整列順序は上界を持つ」を満たすならば，X の極大元が 存在する． 3. 順序集合X が「X の部分整列順序は上限を持つ」を満たすならば，X の極大元が 存在する． 4. 順序集合X が「X の鎖は上限を持つ」を満たすならば，X の極大元が存在する． 5. 順序集合(X,⊂)が「任意の部分整列順序Y ⊂ X に対して ∪ y∈Y y ∈ X」を満たす ならばX は極大元を持つ． 証明. 2はMP(順序, 整列)だから，定理3により1⇐⇒2である．また2=⇒3，3=⇒4， 3=⇒5は明らか． 4=⇒1と5=⇒1は定理1の条件5が成り立つことから分かる． MS(P, Q)で命題 (X, R)がP のとき，集合_{{Y ⊂ X | (Y, R)}はQである_}は_⊂に関する極大元を持つ を表すとする． 定理 6. 次の(P, Q)に対してZornの補題⇐⇒ MS(P, Q)である． • P =関係，推移，Q =反対称，連結，反連，推連，順序，全，有向，分岐 • P =反対称，Q =連結，反連，推連，全，有向，分岐 • P =連結，Q =反対称，連結，順序，全，有向，分岐 • P =順序，Q =連結，反連，推連，全，有向，分岐

• P =有向，Q =連結，反連，推連，全，分岐 • P =分岐，Q =連結，反連，推連，全，有向 • P =森，Q =連結，反連，推連，全，有向，整列 証明. (1) P =⇒ P′ならばMP(P′, Q) =⇒ MP(P, Q)である． (2) 関係R⊂ X × X に対して「(X, R)が連結⇐⇒ (X, R)が反対称」「(X, R∪ I) が 全_{⇐⇒ (X, R ∪ I)}が全」が成り立つ．故にMP(反対称, 連結) ⇐⇒ MP(連結, 反対称)と MP(反対称,反連)⇐⇒ MP(連結,反連)とMP(反対称,全)⇐⇒ MP(連結,全)とMP(関 係, 反対称) ⇐⇒ MP(関係, 連結)が分かる． (3) 次の同値は明らかである． • MP(推移, 反対称) ⇐⇒ MP(推移, 順序) • MP(連結, 順序) ⇐⇒ MP(連結, 全) ⇐⇒ MP(連結, 有向) ⇐⇒ MP(連結, 分岐) • MP(有向, 連結) ⇐⇒ MP(有向, 反連) ⇐⇒ MP(有向, 推連) ⇐⇒ MP(有向, 全) ⇐⇒ MP(有向, 分岐) • MP(森,連結)⇐⇒ MP(森,反連)⇐⇒ MP(森,推連)⇐⇒ MP(森,全)⇐⇒ MP(森, 有向) ⇐⇒ MP(森, 整列) 以上の(1)(2)(3) を合わせると，次の図式が得られる．(→は(1)， は(2)， は

(3)による．またMS(P, Q)を P Q で表した．四角い枠については後述．) 関係 反対称 関係 連結 関係 反連 関係 推連 関係 順序 関係 全 関係 有向 関係 分岐 反対称 連結 反対称 反連 反対称 推連 反対称 全 反対称 有向 反対称 分岐 推移 反対称 推移 連結 推移 反連 推移 推連 推移 順序 推移 全 推移 有向 推移 分岐 連結 反対称 連結 反連 連結 順序 連結 全 連結 有向 連結 分岐 順序 連結 順序 反連 順序 推連 順序 全 順序 有向 順序 分岐 有向 連結 有向 反連 有向 推連 有向 全 有向 分岐 分岐 連結 分岐 反連 分岐 推連 分岐 全 分岐 有向 森 連結 森 反連 森 推連 森 全 森 有向 森 整列 また，Q = 反対称，連結，反連，推連，順序，全，有向，分岐のとき，Zornの補題=⇒ MP(関係, Q)である．よって後は「図中で四角に囲まれた命題=⇒ Zornの補題」，即ち 次の(i)(i)(iii)を示せばよい． (i) MS(有向, 全) =⇒ Zornの補題 定理1の条件 8「任意の順序集合は極大鎖を持つ」を示す．(X,≤)を順序集合とする． C := {Y ⊂ X | (Y, ≤)は鎖}とすると(C, ⊃)は有向集合になる．よって仮定のMS(有 向, 全)により極大な部分全順序_{M ⊂ C}が存在する．このときZ := ∪ Y∈M Y と置けば明 らかにこのZ ⊂ Xが極大鎖である． (ii) MS(森, 全) =⇒ Zornの補題 MP(順序,整列)を示す．(X,≤)を順序集合として，X の部分整列順序は上界を持つとす

る．W := {Y ⊂ X | (Y, ≤)は整列順序}として，W に順序⊴を Y ⊴ Z ⇐⇒ Y = Zまたはあるz ∈ Z が存在してY = z↓ で定める．すると(W, ⊴)は森になる．よって仮定のMS(森, 全)により極大な部分全順 序_{V ⊂ W} が存在する．このときZ := ∪ Y∈V Y と置けば明らかにZ ∈ W だから，Z の上 界x∈ X が存在する．このxが極大元である． (iii) MS(推移, 反対称) =⇒ Zornの補題 選択集合の存在を示す．その為に_{Xλ}λ∈Λ を互いに素な非空集合の族とする．X := ∪ λ∈Λ Xλに関係Rを xRy⇐⇒あるλ ∈ Λが存在してx, y ∈ Xλ と定める．Rは勿論推移的であるから，仮定のMS(推移, 反対称)により極大な Y を得 る．このY が{Xλ}λ∈Λ の選択集合である． MS′(P, Q)で命題 (X, R)がP であり，Y ⊂ X で(Y, R)がQであるとする． このとき集合_{{Z ⊂ X | Y ⊂ Z}，(Z, R)はQである_}は_⊂に関する極大元を持つ を表すとする． 定理7. 定理6で述べた組(P, Q)のうち，(森,整列)を除いてZornの補題⇐⇒ MS′(P, Q) である． 証明. 定理 6 と同 様 に し て Zorn の 補 題 =⇒ MS′(P, Q) が分 か る ．一 方，明 らか に MS′(P, Q) =⇒ MS(P, Q)であるからMS′(P, Q) =⇒ Zornの補題である． 定理 8. Zornの補題 ⇐⇒順序集合X が「下の条件 (∗)を満たす任意のA ⊂ X が上界を持つ」を満たすなら ば，X は極大元を持つ． (∗) 任意の元x, y ∈ Aに対し_{{x, y} ⊂ A}はAに上界を持つ． 証明. (=⇒) X を順序集合とする．(∗)を満たすA⊂ X が上界を持つとする．C ⊂ X を 任意の鎖とすると鎖は(∗)を満たすから，Cは上界を持つ．従ってZornの補題よりX は 極大元を持つ．

(⇐=) 選択公理を示す．{Xλ}λ∈Λを非空集合の族とする．X :={f : Γ −→ ∪ λ∈ΛXλ| Γ⊂ Λ, f(λ) ∈ Xλ} と定める．X に⊂で順序を入れる． A ⊂ X が (∗) を 満 た す と す る ．g := ∪ f∈A f と 置 く ．λ ∈ dom(g) を 取 る ． dom(f1), dom(f2)∋ λとなる任意のf1, f2 ∈ Aを取る．条件(∗)より，{f1, f2}はA に 上界hを持つ．このとき h(λ) = f1(λ) = f2(λ) である．よってg(λ)は一意に定まる． 故にgは写像であり，g∈ X となる．明らかにgはAの上界である． よって仮定よりX は極大元を持つが，それが選択関数である． 定理 9. Zornの補題 ⇐⇒任意の集合Xは次の条件を満たす極大部分集合Y ⊂ X を持つ． 任意の元a, b∈ Y に対してa∈ bまたはa = bまたはb∈ a 証明. (=⇒) Tukeyの補題(定理1の6)により明らか． (⇐=) 整列可能定理を示す．X を任意の集合として W := {(Y, R) | Y ⊂ X, R ⊂ Y × Y, (Y, R)は整列順序_}と定める．_Wに順序関係 ≦ を次のように定義する． (Y, R) < (Z, S)⇐⇒あるz ∈ Z が存在して(Y, R) = (z↓, S). すると(W, ≤)は木である．_W 上の写像f を f (Y, R) :={{R}}∪{f (W, T )(W, T )∈ W, (W, T ) < (Y, R)} で定める．

(i) f (Y, R) = f (Z, S)⇐⇒ (Y, R) = (Z, S) . ..) ⇐= は明らか．=⇒ を示す．f (R) = f (S) かつ (Y, R) ̸= (Z, S) であるとす る．するとR ̸= S であるから_{{R} ̸= {S}}となる．よって，f (R) _{⊂ f(S)}だから {R} ∈ {f(W, T ) | (W, T ) ∈ W, (W, T ) < (Z, S)}でなければならない．故にある (W, T ) < (Z, S)が存在して R = f (W, T )となる．よって{T } ∈ f(W, T ) = R ⊂ Y × Y となり矛盾する．

(ii) f (Y, R)∈ f(Z, S) ⇐⇒ (Y, R) < (Z, S) .

..) ⇐= はf の定義から明らか．f (Y, R) ∈ f(Z, S)とする．すると f の定義より f (Y, R) = {S}かf (Y, R) ∈ {f(W, T ) | (W, T ) ∈ W, (W, T ) < (Z, S)}のどちら かである．しかしf (Y, R) = {S}はありえない．故にある(W, T ) < (Z, S)が存在

してf (Y, R) = f (W, T )と書ける．すると(i)により(Y, R) = (W, T )となるから，

(Y, R) < (Z, S)である．

集合f (W)に仮定を適用して，Q ⊂ f(W)を得る．V := f−1(Q)と定める．(i)(ii)によ り，_{V ⊂ W} は「任意の(Y, R), (Z, S)∈ V に対し(Y, R) < (Z, S)または(Y, R) = (Z, S)

または(Z, S) < (Y, R)」を満たす極大部分集合である．W := ∪ (Y,R)∈V Y, T := ∪ (Y,R)∈V R とすれば，明らかに(W, T )∈ Wである． X ̸= W と仮定する．x _{∈ X \ W} を取る．T := Te ∪ (W × {x}) ∪ {⟨x, x⟩} と 置くと (W ∪ {x}, eT ) ∈ W である．V := V ∪ {(W ∪ {x}, ee T )} を考えると，これは 「任意の (Y, R), (Z, S) ∈ eV に対し (Y, R) < (Z, S) または (Y, R) = (Z, S) または

(Z, S) < (Y, R)」を満たす．明らかに _{V ⊊ eV} だから _V の極大性に矛盾する．よって X = W であり，T はXを整列する． 定理 10. 集合X と整数n≥ 2に対して，UN(X, n)で次の命題を表すとする． 任意のR⊂ Xnに対して_{{Y ⊂ X | Y}n_{⊂ R}は(⊂に関する)極大元をもつ．} n≥ 2を整数とするとき，次の命題は(ZF上)同値． 1. Zornの補題 2(n). 任意のX に対してUN(X, n) 3. あるn≥ 2が存在して任意のX に対しUN(X, n) 4. 任意のX に対してあるn≥ 2が存在してUN(X, n) 証明. 1=⇒2(n)と2(n)=⇒3と3=⇒4は明らか． (4=⇒2(2)) R ⊂ X × X を二項関係とする．仮定4 により，あるn ≥ 2が存在して UN(X, n)が成り立つ．そこでR× Xn−2 にUN(X, n)を適用して極大なY を得る．こ のY は明らかに_{{Y ⊂ X | Y}2 _{⊂ R}の極大元である．} (2(2)=⇒1) 2(2) =⇒ MS(関係, 連結)を示せばよい．R _{⊂ X × X} を二項関係とする． R∪ R−1∪ I に2(2)を適用して{Y ⊂ X | Y2 _{⊂ R ∪ R}−1_{∪ I}の極大元Y を得る．明ら} かに，このY が{Y ⊂ X | (Y, R)は連結}の極大元である． 定義. 集合X 上の二項関係を次のように定義する． 1. xDy ⇐⇒ x ∩ y = ∅ 2. xKy ⇐⇒ x ⊂ yまたはy⊂ x

3. xJ y ⇐⇒ x ̸⊂ yかつy ̸⊂ xかつx∩ y ̸= ∅ R⊂ Xを関係とする．部分集合Y ⊂ X が「任意の異なる二元x, y ∈ Y に対しxRy」を 満たすとき，Y はproperty Rを持つということにする． 定理 11. 関係Rに対しN(R)で次の命題を表すとする． 任意のX に対し{Y ⊂ X | Y はproperty Rを持つ}は極大元をもつ このとき Zornの補題⇐⇒ N(D) ⇐⇒ N(D) ⇐⇒ N(K) ⇐⇒ N(J) ⇐⇒ N(J) 証明. (Zornの補題=⇒ N(J)) Tukeyの補題より明らか． (N(J ) =⇒ N(D)) 任意の集合X をとる．uを「任意のx, y ∈ Xに対し_{⟨x, u⟩ /∈ y}」を 満たすように取り，x _{∈ X}に対しf (x) := x∪ {⟨x, u⟩}と定める．仮定N(J )をf (X)に 適用すると，property J を持つ極大部分集合S ⊂ f(X)の存在が分かる．Y := f−1(S) と定める．

x, y ∈ X, x ̸= y とする．定義から f (x)Kf (y)．故に f (x)J f (y) ⇐⇒ f(x)Df(y) が成り立つ．一方，f (x) ∩ f(y) = x ∩ y だから f (x)Df (y) ⇐⇒ xDy となる．即ち f (x)J f (y)⇐⇒ xDy であり，従ってY ⊂ Xはproperty Dを持ち極大である．

(N(D) =⇒ N(D)) 任意の集合 X をとる．x _{∈ X} に対しf (x) := {{x}}∪{{x, z}  z ∈ X, xDz}と置く． x, y ∈ X, x ̸= yとする．定義からf (x)Df (y)⇐⇒ xDyである．よって仮定N(D)を f (X)に適用すれば，N(D)の成立が分かる． (N(D) =⇒ Zornの補題) 選択公理を示す．{Xλ}λ∈Λ を互いに素な非空集合の族とす る．X := {{⟨0, x⟩, ⟨1, λ⟩}  λ ∈ Λ, x ∈ Xλ } とする．仮定 N(D)を X に適用して， property D を持つ極大部分集合Y ⊂ X を得る．_{{⟨0, x⟩, ⟨1, λ⟩}D{⟨0, y⟩, ⟨1, µ⟩} ⇐⇒} λ ̸= µだから，各λ∈ Λに対し_{{⟨0, xλ⟩, ⟨1, λ⟩} ∈ Y} となるようなxλ ∈ Xλが唯一つ存 在する．よって{xλ| λ ∈ Λ}が選択集合である． (Zornの補題=⇒ N(J)) Tukeyの補題より明らか． (N(J ) =⇒ N(K)) 任意の集合X をとる． ∪ x∈X xに含まれない元uを取り，x _{∈ X} に 対しf (x) := x∪ {u} と置く．すると任意のx, y ∈ X, x ̸= y に対しf (x)Df (y)となる から，f (x)J f (y)⇐⇒ f(x)Kf(y) ⇐⇒ xKy が分かる．故に仮定N(J )をf (X)に適用

すれば，N(K)の成立が分かる．

定理 12. Zornの補題⇐⇒ N(K) 証明. X を集合とするとき，Y ⊂ Xがproperty K を持つのは，Y が順序集合(X,⊂)の 反鎖となるときである． (=⇒) 定理1の条件11より明らか． (⇐=) 定理1の条件11を示す．(X,≤)を順序集合とするときA :={x↓ | x ∈ X}とす れば順序同型(X,≤) ∼= (A,⊂)が成り立つ．よって仮定から{B ⊂ A | Bはproperty K を持つ_}の極大元Bを取れば，それに対応するY ⊂ X が極大反鎖である． 定理 13. Zornの補題_⇐⇒順序集合(X,≤)が「任意の鎖は上界を持つ」を満たすとき， あるt ∈ X が存在してt :={x ∈ X | t < x}は最小元を持たない． 証明. (=⇒) Zornの補題により極大元t ∈ X が存在する．このときt = ∅は最小元を持 たない． (⇐=) Zornの補題が成り立たないと仮定する．即ち極大元を持たない順序集合(X,≤) で「任意の鎖は上界を持つ」を満たすものが存在する．X× N上の順序を辞書式順序で定 める．X× Nは「任意の鎖は上界を持つ」を満たす． . ..) C ⊂ X × Nを鎖とする．π : X_{× N −→ X}を標準射影とするとπ(C)⊂ X は鎖 である．故に上界u0 ∈ Xを持つ．X は極大元を持たないからu > u0 となるu ∈ X が存在する．このとき_{⟨u, 0⟩ ∈ X × N}はC の上界である． 一方，任意の_{⟨x, m⟩ ∈ X × N}に対して_{⟨x, m⟩}は最小元_{⟨x, m + 1⟩}を持つから仮定に 矛盾する．

参考文献

[1] H. Rubin and J. Rubin, Equivalents of the axiom of choice II, North Holland, 1985.

[2] Horst Herrlich, Axiom of Choice，Springer, 2006