2012年4月15日更新

Constructive Order Theory

PDF版

定義 Xを集合とする.

  1. P0(X) := P(X)\{ ∅ }
  2. E(X) := { {x} | x∈X }
  3. F(X) := { Y⊂X | Yは有限集合 }
  4. F0(X) := F(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)→F(X) が存在する.

証明 (1 ⇒ 2) Xを任意の集合とする.P0(X) に選択公理を適用して 選択関数 f: P0(X)→X を得る. このとき明らかに Y に { f(Y) } を対応させる写像はcontractionである.

(2 ⇒ 1) {X_λ}_{λ∈Λ}を非空集合の族とする. X:=∪_{λ∈Λ}X_λに仮定を適用してcontraction φ: P0(X)→E(X) を得る.任意のλ∈Λに対してφ(Xλ)⊂Xλである.φ(Xλ)∈E(X)だからφ(Xλ) = { xλ } と書ける.{ xλ } = φ(Xλ)⊂Xλ だからxλ∈Xλとなる.よって(xλ)λ∈ΛΠ_{λ∈Λ}X_λである.

(1 ⇔ 3) 同様にして AMC⇔3 であることが分かる.

定義 (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に対して

s≦xのとき Ax := Y
¬s≦xのとき Ax := { y∈Y | ¬y≦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\Y)⊂X\Y である.故にψ(X\Y)∩Y≠∅となる.ψ(X\Y)∈E(X) だからψ(X\Y)∩Y∈E(X) である.よってφは P0(X) から E(X) への写像であるが,定義から明らかにcontractionである.

定義 順序集合(X, ≦)がconstructively directedである
⇔ある写像φ: F0(X)→X が存在して,任意の Y∈F0(X) に対してφ(Y)はYの上界である.(この写像φをconstructtive directionと呼ぶ)

定理3 選択公理 ⇔ 任意の有向集合はconstructively directedである.

証明 (⇒) (X, ≦)を有向集合とする.Y∈F0(X) に対して AY := { x∈X | xはYの上界 } と置き { AY }Y∈F0(X) に選択公理を適用すればよい.

(←) {X_λ}_{λ∈Λ}を互いに素な非空集合の族とする.Λは無限集合であるとしてよい.X:=∪_{λ∈Λ}X_λとして G := { A∈F0(X) | 任意のλ∈Λに対して |A∩Xλ|≦1 } と置く.G∩Λ = ∅ としてよい.このとき S := G∪Λ の順序≦を,s, t∈Sに対して

s < t
⇔ 「s, t∈Gかつ{λ∈Λ| s∩Xλ≠∅ } ⊊ {λ∈Λ| t∩Xλ≠∅ }」または「s∈Λ, t∈G かつ |t∩Xs| = 1」

で定義する.このとき(S, ≦)は有向集合である.

任意のs, t∈Sに対して,あるu∈Sが存在して s≦u かつ t≦u とできることを示せばよい.

A, B∈Gとする.A, Bは有限集合でΛは無限集合だから,あるμ∈Λが存在して Xμ∩(A∪B) = ∅ とできる.ΛA := {λ∈Λ| A∩Xλ = ∅ } と置く.x∈Xμを一つ取り C := A∪( ∪λ∈ΛA (B∩Xλ) )∪{x} とすれば C∈G, A≦C, B≦C である.

λ, μ∈Λとする.x∈Xλ, y∈Xμを取り A := {x, y} と置く.すると明らかに A∈G, λ≦A, μ≦A である.

A∈G, λ∈Λとする.λ≦Aのときは明らかだから¬λ≦Aとする.このとき A∩Xλ = ∅ である.x∈Xλを取り B := A∪{x} と置く.すると明らかに B∈G, A≦B, λ≦B である.

以上により(S, ≦)は有向集合である.

故に仮定によりconstructive direction φ: F0(S)→S が存在する.λ, μ∈Λ, λ≠μとするとき明らかに |φ( {λ, μ} )∩Xλ| = 1 である.そこでμ∈Λとxμ∈Xμを取り,λ≠μに対して φ( {λ, μ} )∩Xλ = { xλ } と書けば ( xλ )λ∈ΛΠ_{λ∈Λ}X_λである.

参考文献

コメント

コメントはまだありません。

コメントする

感想、意見、質問など何でもどうぞ。
※書き込んだのに表示されない場合は、ページをリロードしてみてください。