2013年10月25日更新

従属選択公理について

PDF版

定義 次の命題を従属選択公理(axiom of dependent choice)という.

非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとき,Xのある点列 { xn }n∈ωが存在して任意の n に対して xnRxn+1 となる.

命題1 選択公理 ⇒ 従属選択公理

証明 X≠ ∅ とし,二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとする.Ax := { y∈X | xRy } と置く.Ax≠ ∅ だから { Ax }x∈X に選択公理を適用して選択関数 f: X→∪x∈X Ax⊂X を得る.あとは x0∈X を一つ取り xn+1 := f(xn) と定めればよい.

命題2 従属選択公理 ⇒ 可算選択公理

証明 { Xi }i∈ω を互いに素な非空集合の族とする.X := ∪i∈ω Xi として二項関係R := ∪i∈ω (Xi×Xi+1)⊂X×X を考える.このRは明らかに従属選択公理の仮定を満たす.よってある { xn }i∈ω が存在して任意の n に対して xnRxn+1 が成り立つ. x0∈Xm となる m を取ると明らかに xn∈Xm+n である. 故にΠi=mXi≠∅となる. 従ってΠi=0Xi = Πi=0m-1Xi×Πi = mXi≠ ∅ が分かる.

これにより,可算選択公理がZFで証明できないことを認めれば,従属選択公理がZFで証明できないことが分かる.

命題3 従属選択公理
⇒ 従属選択公理と同じ仮定の下で,任意の x0∈X に対してある点列 { xn }n∈ω が存在して,任意の非負整数 n に対して xnRxn+1 となる.

証明 ← は明らかなので ⇒ を示す.

非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとし,x0∈X を任意の元とする. A := { <x1, …, xm> | m≧1, x0Rx1, …, xm-1Rxm } と置く.二項関係 S⊂A×A を

<x1, …, xs>S< y1, …, y_t> ⇔ s<tかつx1=y1, …, xs=ys

で定義する.この S は従属選択公理の仮定を満たす.よってある { an }n∈ω が存在して 任意の n に対して anSan+1 が成り立つ. an∈A だから an = < an,1, …, an,sn> と書ける. S の定義より 0<s0<s1<… だから n+1≦sn である.よって xn+1 := an, n+1 と定義できて,このとき任意の n に対して xnRxn+1 である.

定義 順序数αに対して,次の命題をDC(α)で表す.

関係 R⊂P(X)×X が「|Y| < |α| となる任意の部分集合 Y⊂X に対してある x∈X が存在して R(Y, x)」を満たすとき,ある f: α→X が存在して任意のβ<αに対して R(f"β, f(β)) となる.

f"β := { f(γ) | γ<β } である.

命題4 従属選択公理 ⇔ DC(ω)

証明 (⇒)関係 R⊂P(X)×X が「|Y| < |ω| となる任意の部分集合 Y⊂X に対してある x∈X が存在して R(Y, x)」を満たすとする.Pfin(X) := { Y⊂X | |Y|<|ω| }, A := Pfin(X)×X と置く.二項関係 S⊂A×A を

<Y, y>S<Z, z> ⇔ Y∪{z}=Z かつ R(Y, z)

で定める.このSは従属選択公理の仮定を満たす.よってAの点列 { < Yn, yn> }n∈ω で任意の n に対して <Yn, yn>S<Yn+1, yn+1> を満たすものが存在する.命題3により Y0 = ∅ とできる. このとき f: ω→X を f(n) := yn+1 で定める.Yn = f"n である.

n=0 のときは明らか.

n>0 のときは

Yn = Yn-1∪{yn} = f"(n-1)∪{f(n-1)} = f"n

である.

R(Yn, yn+1) だったから R(f"n, f(n)) となる.

(←) 非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとする.A := X×ωと置く.関係 S⊂P(A)×A を B∈P(A), <x, n>∈A に対して次のように定める.

(i) B=∅のとき.

S(∅, <x, n>) ⇔ n=0.

(ii) B≠∅が有限集合で,ある<y, m>∈B に対してm=|B| となるとき.

S(B, <x, n>) ⇔ n=|B|+1 かつある <y, |B|>∈B が存在して yRx.

(iii) それ以外のとき.常に S(B, < x, n>).

この S はDC(ω)の仮定を満たす.よってある写像 f: ω→A が存在して任意の n<ω に対して S(f"n, f(n)) である.Sの定義から f(n) = <xn, |f"n|+1> と書ける.|f"n| = n である.

n=0 のときは明らか.

n>0のとき.f"n = f"(n-1)∪{f(n-1)} であり,S の定義から明らかに f(n-1) ∉ f"(n-1) であるから

|f"n| = |f"(n-1)|+|{f(n-1)}| = (n-1)+1 = 1.

故に f"(n+1) = {f(0), …, f(n)} = {<x0, 0>, …, <xn, n>} である.従って S の定義から xnRxn+1 である.よって { xn }n∈ωを取ればよい.

この命題により,DC(α)は従属選択公理の一般化と考えることができる.

定理 選択公理 ⇔ 任意の順序数αに対してDC(α)が成り立つ.

証明 (⇒)明らか.

(←)整列可能定理を示す.X を任意の集合とする.X に含まれない元∞を一つ取り Z := X∪{∞} と置く. 関係 R⊂P(Z)×Z を

R(Y, x) ⇔ x ∉ Y かつ Y⊂X (x∈Xのとき)
R(Y, ∞) ⇔ Y=Z または Y=X

で定義する.この R は「任意の部分集合 Y⊂Z に対してある x∈Z が存在して R(Y, x)」を満たす. αを ¬|α|≦|Z| なる順序数とする.(このような順序数は選択公理を使わずに取れる.) R にDC(α)を適用して写像 f: α→Z を得る.β, γ<αについて,f(β)=f(γ)≠∞ならばβ=γである.

β≠γと仮定する.β<γとしてよい.f の取り方から R(f"γ, f(γ)) である.f(γ)≠∞だから R の定義により f(γ) ∉ f"γ となる.f(β)∈f"γ だから f(β)≠f(γ) となり矛盾する.

¬|α|≦|Z| だったから,f は単射ではない.故に f(β)=∞ となるβ<αが存在する.そこでγ := min{ β<α | f(β)=∞ } と置く.このとき R(f"γ, ∞) だからf"γ=X または f"γ=Z となるが,γの最小性から f"γ=X が分かる.故に fγ: γ→X が全単射になる.

選択公理に対してAMCがあるように,従属選択公理に対してDMCがある.

定義 次の命題をDMC(Axiom of Dependent Multiple Choice)という.

非空集合 X 上の二項関係 R⊂X×X が「任意のx∈Xに対してあるy∈Xが存在してxRy」を満たすとき, X のある有限部分集合列 { Fn }n=0 が存在して,任意の n∈N と x∈Fn に対してある y∈Fn+1 が存在して xRy となる.

定理 従属選択公理 ⇒ DMC

定理 次の命題は( ZF 上)同値.

  1. DMC
  2. { Xn }n=0 を互いに素な非空集合の族で, |X0|=1 とする. X := ∪n=0Xn として,全射 f: X→X は「x∈Xn+1 に対して f(x)∈Xn」を満たすとする.このときある { Fn }n=0 が存在して Fn⊂Xn, 0 < |Fn| < ∞, f(Fn+1)=Fn となる.
  3. y∈X とするとき,DMCにおいて F0={ y } とできる.即ち非空集合 X 上の二項関係 R⊂X×X が「任意のx∈Xに対してあるy∈Xが存在してxRy」を満たすとき,任意の y∈X に対して X のある有限部分集合列 { Fn }n=0 が存在して, F0={ y } かつ任意の n∈N と x∈Fn に対してある y∈Fn+1 が存在して xRy となる.

証明 (1 ⇒ 2)2の条件を満たす { Xn }n=0 と f を取る. X := ∪n=0Xn 上の二項関係 R を

xRy ⇔ x=f(y)

で定めるとこれは「任意の x∈X に対してある y∈X が存在して xRy」を満たす.故にある { Gn }n=0 が存在して Gn⊂X, 0 < |Gn| < ∞ かつ「任意の n∈N と x∈Gn に対してある y∈Gn+1 が存在して xRy 」となる. a∈G0 を一つ取り, a∈Xm となる番号 m を取る.このとき xm := a, xm-1 := f(xm), …, x0 := f(x1) として

Fn := { xn } (0≦n≦mのとき)
Fn := Gn-m∩Xn (n > mのとき).

と定める.このとき Fn⊂Xn, 0 < |Fn| < ∞, f(Fn+1)=Fn である.

(2 ⇒ 3)非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとする. y∈X をとる. n≧0 に対して Xn := { <y, x1, …, xn> | yRx1, …, xn-1Rxn } と置く. X := ∪n=0Xn として, f: X→X を

f(x) := y (x=y のとき)
f(x) := <y, x1, …, xn> (x=<y, x1, …, xn, xn+1>∈Xn+1のとき).

で定義する.この f は仮定2の条件を満たす.よってある { Gn }n=0 が存在して Gn⊂Xn, 0 < |Gn| < ∞, f(Gn+1)=Gn となる. πn: Xn→X を第 n+1 成分への射影として Fn := πn(Xn) とすれば F0={ y } で { Fn }n=0 はDMCの条件を満たす.

(3 ⇒ 1)明らか.

コメント

匿名 | 2013年10月29日 04:14

命題4の中の「従属選択公理 (←) DC(ω)」の証明におけるSの定義(ii)は不適であると思われます。

z∈X を適当にとって、B={<z,1000000>}とすれば
B⊂Aではありますが、|B|=1ですので、yをどんな風にとろうとも<y,|B|>∈Bは成立しません。すると<x,n>∈Aをどんな風にとろうとも、それに無関係にS(B,<x,n>)は成立しないはずです。

これはSがDC(ω)の仮定をみたさないことを意味しているので、そこからの証明が破綻してしまいます。

管理人 | 2013年10月30日 00:19

あっホントですね…
そういうBのときは常にS(B, a)となるようにすれば大丈夫そうですが…。

ちゃんと考えて後日直します。ありがとうございました。

管理人 | 2013年11月 4日 22:57

直しました。

コメントする

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