Constructive Order Theory : 選択公理

Constructive Order Theory

と選択公理

alg-d

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

2012

年

4

月

15

日

定義. Xを集合とする． 1. P0(X) :=P(X) \ {∅} 2. E(X) :={{x} | x ∈ X} 3. Pfin(X) :={Y ⊂ X | Y は有限集合} 4. P0 fin(X) :=Pfin(X)\ {∅} これらは包含関係⊂により順序集合である． 定義. (X,≤)を順序集合，Y ⊂ X を部分順序とする． 写像φ : X −→ Y がcontractionである⇐⇒任意のx∈ X に対してφ(x)≤ xとなる． 定理 1. 次の命題は(ZF上)同値． 1. 選択公理 2. 任意の集合X に対して，contraction P0(X) −→ E(X)が存在する． 3. 任意の集合X に対して，contraction P0(X) −→ Pfin(X)が存在する． 証明. (1 =⇒ 2) X を任意の集合とする．P0(X) に選択公理を適用して選択関数 f : P0(X) −→ Xを得る．このとき明らかにY 7−→ {f(Y )}はcontractionである． (2 =⇒ 1) {Xλ}λ∈Λ を非空集合の族とする．X := ∪ λ∈Λ Xλ に仮定を適用して con-traction φ : P0(X) −→ E(X) を得る．任意のλ ∈ Λに対して φ(Xλ) ⊂ Xλ である． φ(Xλ)∈ E(X)だからφ(Xλ) = {xλ}と書ける．{xλ} = φ(Xλ) ⊂ Xλだからxλ ∈ Xλ となる．よって(xλ)λ∈Λ ∈ ∏ λ∈Λ Xλである． (1 ⇐⇒ 3) 同様にしてAMC⇐⇒3であることが分かる． 1

定義. (X,≤)を順序集合，s∈ X を部分順序Y ⊂ Xの上界とする． sがY のconstructive supremumである ⇐⇒ある写像ψ : X −→ Y が存在して，任意のx∈ X に対して「s≤ x ⇐⇒ ψ(x) ≤ x」 となる 命題. (X,≤)を順序集合として，Y ⊂ X はconstructive supremum s ∈ X を持つとす る．このときsはY の上限である． 証明. constructive supremum の定義から，ある写像 ψ : X −→ Y が存在して任意の x∈ X に対して「s≤ x ⇐⇒ ψ(x) ≤ x」となる．t∈ X をY の上界とすると，上界の定 義によりψ(t)≤ tであるからs≤ tとなる．よってsはY の最小上界である． 定理 2. 次の命題は(ZF上)同値． 1. 選択公理 2. (X,≤)を順序集合として，Y (̸= ∅) ⊂ X は上限sを持つとする．このときsはY のconstructive supremumである． 3. (X,≤) を完備束として，Y (̸= ∅) ⊂ X の上限を s とする．このとき s はY の constructive supremumである． 4. (X,≤)をpowerset latticeとして，Y (̸= ∅) ⊂ X の上限をs とする．このときs はY のconstructive supremumである． 証明. (1 =⇒ 2) (X, ≤)を順序集合，s∈ X をY (̸= ∅) ⊂ X の上限とする．x∈ X に対 して Ax := { Y (s ≤ xのとき) {y ∈ Y | y ≰ x} (s ≰ xのとき) と置く．s≰ xのとき，xはY の上界ではないからAx ̸= ∅である．故に集合族{Ax}x∈X に選択公理を適用すると選択関数 f : X −→ ∪ x∈X Ax ⊂ Y を得る．この f は明らかに 「s≤ x ⇐⇒ f(x) ≤ x」を満たす． 2=⇒3と3=⇒4は明らか． (4 =⇒ 1) 定理1 の条件2を示す．X を集合とする．P(X)はpowerset latticeだか ら，E(X) ⊂ P(X)の上限X はconstructiveである．故にある写像ψ :P(X) −→ E(X)

が存在して，任意のY ⊂ X に対して「X ⊂ Y ⇐⇒ ψ(Y ) ⊂ Y」となる．即ち「Y ⊊ X ⇐⇒ ψ(Y ) ̸⊂ Y」である．

Y ∈ P0(X) に対して φ(Y ) := ψ(X \ Y ) ∩ Y と置く．X \ Y ⊊ X だからψ(X \ 2

Y ) ̸⊂ X \ Y である．故に ψ(X \ Y ) ∩ Y ̸= ∅ となる．ψ(X \ Y ) ∈ E(X) だから

ψ(X \ Y ) ∩ Y ∈ E(X)である．よってφはP0(X)からE(X) への写像であるが，定義

から明らかにcontractionである．

定義. 順序集合(X,≤)がconstructively directedである

⇐⇒ある写像φ :P_fin0 (X) −→ X が存在して，任意のY ∈ P_fin0 (X)に対してφ(Y )はY

の上界である．(この写像φをconstructtive directionと呼ぶ) 定理 3. 選択公理⇐⇒任意の有向集合はconstructively directedである． 証明. (=⇒) (X, ≤)を有向集合とする．Y ∈ P_fin0 (X)に対してAY := {x ∈ X | xはY の上界}と置き{AY}Y∈P0 fin(X)に選択公理を適用すればよい． (⇐=) {Xλ}λ∈Λ を互いに素な非空集合の族とする．Λ は無限集合であるとしてよい． X := ∪ λ∈Λ XλとしてA := {A ∈ Pfin(X) |任意のλ∈ Λに対して|A ∩ Xλ| ≤ 1}と置く． A ∩ Λ = ∅としてよい．このときS :=A ∪ Λの順序≤を，s, t∈ Sに対して s < t⇐⇒ { s, t∈ Aかつ{λ ∈ Λ | s ∩ Xλ ̸= ∅} ⊊ {λ ∈ Λ | t ∩ Xλ ̸= ∅} またはs ∈ Λ, t ∈ Aかつ|t ∩ Xs| = 1 で定義する．このとき(S,≤)は有向集合である． . ..) 任意のs, t ∈ S に対して，あるu∈ S が存在してs ≤ u, t ≤ uとできることを 示せばよい． A, B ∈ Aとする．A, B は有限集合でΛは無限集合だから，ある µ∈ Λが存在し てXµ∩ (A ∪ B) = ∅とできる．ΛA :={λ ∈ Λ | A ∩ Xλ=∅}と置く．x∈ Xµを一 つ取りC := A∪( ∪ λ∈ΛA (B∩ Xλ) ) ∪ {x}とすればC ∈ A, A ≤ C, B ≤ C である． λ, µ ∈ Λとする．x ∈ Xλ, y ∈ Xµ を取りA := {x, y}と置く．すると明らかに A∈ A, λ ≤ A, µ ≤ Aである． A ∈ A, λ ∈ Λ とする．λ ≤ A のときは明らかだから λ ≰ A とする．このと き A∩ Xλ = ∅ である．x ∈ Xλ を取り B := A∪ {x} と置く．すると明らかに B∈ A, A ≤ B, λ ≤ B である． 以上により(S,≤)は有向集合である． 故に仮定によりconstructive direction φ :P0 fin(S)−→ Sが存在する．λ, µ∈ Λ, λ ̸= µ とするとき明らかに|φ({λ, µ}) ∩ Xλ| = 1 である．そこでµ ∈ Λ とxµ ∈ Xµ を取り， λ̸= µに対してφ({λ, µ}) ∩ Xλ={xλ}と書けば(xλ)λ∈Λ ∈ ∏ λ∈Λ Xλである． 3

参考文献

[1] Marcel Ern´e, Constructive Order Theory，Mathematical Logic Quarterly 47 (2001), 211-222,

http://onlinelibrary.wiley.com/doi/10.1002/1521-3870(200105)47: 2<211::AID-MALQ211>3.0.CO;2-U/abstract