制限された選択公理
alg-d
http://alg-d.com/math/ac/
2012
年
1
月
1
日
選択公理とは，非空集合の族{Xλ}λ∈Λ は選択関数f : Λ −→ ∪ λ∈ΛXλを持つという 命題だった．このとき，Λや各Xλに制限を加えたものを考えることもできる． 定義. κ, µを基数とする．次の二条件を満たす族{Xλ}λ∈Λ は選択関数を持つ，という命 題をAC(κ)µで表すことにする． 1. 任意のλ∈ Λに対し|Xλ| = κ 2. |Λ| = µ ※ 添え字集合への制限を添え字に書くことにした． また，次の二条件を満たす族 {Xλ}λ∈Λ は選択関数を持つ，という命題をAC(≤ κ)≤µ で表すことにする． 1. 任意のλ∈ Λに対し0 <|Xλ| ≤ κ 2. |Λ| ≤ µ同様にしてAC(< κ)<µ，AC(≤ κ)<µ，AC(κ)≤µなどを定義する．また，濃度の制限が
無い場合はκ, µのところに何も書かない．例えばΛの濃度に制限が無い場合はAC(κ)と なる．
ACℵ0 を可算選択公理(the Axiom of Countable Choice)と呼ぶ．
これらは，AC<ℵ0 などのような簡単な場合を除けばZFでは証明できないようだ．例
えばAC(2)ℵ はZFで証明できない([1]p71参照)など．
証明. (=⇒) {Xλ}λ∈Λを4元集合の族とする．λ∈ Λに対しAλ :={Z ⊂ Xλ| |Z| = 2} と置く．A := ∪ λ∈Λ Aλ と置けば，A の各元は二元集合だから AC(2) により選択関数 f : A −→ ∪ Z∈A Z = ∪ λ∈Λ Xλ を持つ．λ ∈ Λ として，x ∈ Xλ に対し nλ,x := {Z ∈ Aλ | f(Z) = x} と置く．これは ∑ x∈Xλ nλ,x = 6を満たす．mλ := max{nλ,x | x ∈ Xλ} と置いて Yλ := {x ∈ Xλ | nλ,x = mλ} とする．|Xλ| = 4 と ∑ x∈Xλ nλ,x = 6により 1≤ |Yλ| ≤ 3が成り立つ．g : Λ−→ ∪ λ∈ΛXλを g(λ) := x ∈ Yλとなるx (|Yλ| = 1のとき) f (Yλ) (|Yλ| = 2のとき) x ∈ Xλ\ Yλとなるx (|Yλ| = 3のとき) で定めればgが選択関数である． (⇐=) {Xλ}λ∈Λ を2元集合の族とする．λ ∈ Λ に対しAλ := Xλ× {0, 1} と置けば |Aλ| = 4 だからAC(4)により選択関数 f : Λ −→ ∪ λ∈Λ Aλ が存在する．そこで π を第 一成分への射影としてg := π◦ f : Λ −→ ∪ λ∈Λ Xλ とすれば明らかにgが選択関数であ る． 命題1の⇐=は明らかに次のように一般化できる． 命題 2. 正整数k, nに対しAC(kn) =⇒ AC(n)． ※ 一般に AC(m) =⇒ AC(n)は成立するとは限らない．例えば m = 2 のとき， AC(2) =⇒ AC(n)が成立するn > 1はn = 2, 4だけであることが知られている．こ れによりAC(4) =⇒ AC(3)が成立しないことも分かる．何故ならば，成立すると仮 定するとAC(2) ⇐⇒ AC(4)によりAC(2) =⇒ AC(3)が成立してしまい，矛盾する からである． 命題1の=⇒は以下のように一般化され，命題5を得ることができる． 補題 3. pを素数，n > p をp の倍数としてAC(p)を仮定する．このとき n元集合の 族{Xλ}λ∈Λ に対し集合族{Yλ}λ∈Λ で各λ ∈ Λに対し ∅ ̸= Yλ ⊊ Xλ となるものが存在 する． 証明. Aλ :={Z ⊂ Xλ| |Z| = p}と置きA := ∪ λ∈ΛAλとする．Aの各元はp元集合だ からAC(p)により選択関数f を持つ．
λ ∈ Λ とする．x ∈ Xλ に対し nλ,x := |{Z ∈ Aλ | f(Z) = x}| とする．mλ := max{nλ,x | x ∈ Xλ}と置く．Yλ :={x ∈ Xλ | nλ,x = mλ}と置けば∅ ̸= Yλ ⊂ Xλであ る．このときYλ ⊊ Xλが成立する . ..) |Aλ| = nCp であるから ∑ x∈Xλ nλ,x = nCp = n(n− 1) · · · (n − p + 1) p! となる． n− 1, · · · , n − p + 1はpで割れないから ∑ x∈Xλ nλ,xはnで割り切れない．よって「任 意のx∈ Xλに対しnλ,x = mλ」はありえない．故にYλ̸= Xλである． 補題 4. nを正整数とする．「任意の素数p≤ nに対しAC(p)が成り立つ」ならば「任意 の正整数k ≤ nに対しAC(k)が成り立つ」． 証明. nについての帰納法．n = 1のときは明らか．n > 1とする．任意の素数p≤ nに 対しAC(p)が成り立つとする．帰納法の仮定により任意の1≤ k ≤ n − 1に対しAC(k) が成り立つ．故にAC(n)を示せば証明が終わる． (i) nが素数のとき．仮定によりAC(n)が成り立つから示すべきことは何も無い． (ii) nが合成数のとき．AC(n)を示すため，{Xλ}λ∈Λをn元集合の族とする．1≤ k ≤ n− 1に対しA(k)λ :={Z ⊂ Xλ | |Z| = k}と置きA(k) := ∪ λ∈ΛA (k) λ とする．AC(k)を A(k) に適用して選択関数f(k) を得る． n を割る最小の素数を p とすると，補題 3 により集合族 {Yλ}λ∈Λ で各 λ ∈ Λ に 対し ∅ ̸= Yλ ⊊ Xλ となるものが取れる．勿論 1 ≤ |Yλ| ≤ n − 1 である．そこで f (λ) := f(|Yλ|)(Y λ) と置けばf が{Xλ}λ∈Λ の選択関数である．故に AC(n)が成り立 つ． 命題 5. nを正整数とする．「任意の素数p≤ nに対しAC(p)が成り立つ」ならば「任意 の合成数k ≤ 2n + 1に対しAC(k)が成り立つ」． 証明. 補題4により任意の1≤ m ≤ nに対しAC(m)が成り立つ． k ≤ 2n + 1 を合成数とする．AC(k)を示すため，{Xλ}λ∈Λ をk 元集合の族とする． 1 ≤ m ≤ nに対しA(m)λ := {Z ⊂ Xλ | |Z| = m}と置きA(m) := ∪ λ∈ΛA(m)λ とする． AC(m)をA(m) に適用して選択関数f(m)を得る． k を割る最小の素数をpとすると，明らかにp ≤ nだからAC(p)が成り立つ．よって 補題3により集合族{Yλ}λ∈Λ で各λ ∈ Λに対し∅ ̸= Yλ ⊊ Xλとなるものが取れる．勿
論1≤ |Yλ| ≤ k − 1 ≤ 2nである．そこで f (λ) := { f(|Yλ|)(Y λ) (1≤ |Yλ| ≤ nのとき) f(|Xλ\Yλ|)(X λ\ Yλ) (n + 1≤ |Yλ| ≤ k − 1のとき) と置けばf が{Xλ}λ∈Λの選択関数である．故にAC(k)が成り立つ． 命題 5でn = 2 とすれば先の AC(2) =⇒ AC(4) が得られる．また n = 4 とすれば
AC(2)かつAC(3)からAC(6)，AC(8)，AC(9)が得られることが分かる．
命題 6. AC(2)かつAC(5) =⇒ AC(8)
証明. AC(2)とAC(5)を仮定する．命題 1によりAC(4)が成り立つ．{Xλ}λ∈Λ を8元
集合の族とする．p = 2として補題3を適用すると集合族 {Yλ}λ∈Λ で各λ ∈ Λに対し ∅ ̸= Yλ⊊ Xλとなるものが存在する．勿論1≤ |Yλ| ≤ 7である． 次に自然数nに対しA(n)λ :={Z ⊂ Xλ | |Z| = n}と置きA(n) := ∪ λ∈ΛA (n) λ とする．
AC(2)，AC(4)，AC(5)をそれぞれA(2), A(4), A(5) に適用して選択関数f(2), f(4), f(5) を 得る． あとは，{Xλ}λ∈Λ の選択関数f : Λ−→ ∪ λ∈Λ Xλを f (λ) := x∈ Yλとなるx (|Yλ| = 1のとき) f(2)(Y λ) (|Yλ| = 2のとき) f(5)(Xλ\ Yλ) (|Yλ| = 3のとき) f(4)(Yλ) (|Yλ| = 4のとき) f(5)(Yλ) (|Yλ| = 5のとき) f(2)(Xλ\ Yλ) (|Yλ| = 6のとき) x∈ Xλ\ Yλとなるx (|Yλ| = 7のとき) と定義すればよい． 命題 7. AC(10) =⇒ AC(8)
証明. AC(10) =⇒ AC(2)とAC(10) =⇒ AC(5)により明らか． 命題 8. AC(3)かつAC(7) =⇒ AC(9)
証明. AC(3)とAC(7)を仮定する．{Xλ}λ∈Λ を9元集合の族とする． 自然数 nに対し A(n)λ := {Z ⊂ Xλ | |Z| = n} と置き A(n) := ∪ λ∈ΛA (n) λ とする． AC(3)，AC(7)をそれぞれA(3), A(7) に適用して選択関数f(3), f(7) を得る．
p = 3として補題3を適用すると集合族{Yλ}λ∈Λ で各λ ∈ Λに対し∅ ̸= Yλ ⊊ Xλ と なるものが存在する．勿論1≤ |Yλ| ≤ 8である． |Yλ| = 4となるλ ∈ Λを取る．Bλ := {Z ⊂ Yλ | |Z| = 2}と置く．Z ∈ Bλとする とXλ\ Z ∈ A(7) だから g(Z) := f(7)(Xλ\ Z) ∈ Xλを考えることができる．そこで Wλ:={g(Z) | Z ∈ Bλ} ⊂ Xλと置く．|Bλ| = 6だから1≤ |Wλ| ≤ 6である． (i) |Wλ| = 4とする．このとき Vλ :={g(Z) |あるZ′ ∈ Bλが存在してZ ̸= Z′, g(Z) = g(Z′)} ⊂ Xλ と置けば|Bλ| = 6だから1≤ |Vλ| ≤ 2となる．そこでyλ∈ Xλを yλ := { x∈ Vλとなるx (|Vλ| = 1のとき) f(7)(Xλ\ Vλ) (|Vλ| = 2のとき) と定める． (ii) |Wλ| = 5とする．このとき Vλ :={g(Z) |あるZ′ ∈ Bλが存在してZ ̸= Z′, g(Z) = g(Z′)} ⊂ Xλ と置けば|Bλ| = 6だから|Vλ| = 1となる．そこでyλ∈ Xλをx∈ Vλとなるxにより定 める． (i)(ii)に注意して，xλ ∈ Xλを xλ := x ∈ Wλとなるx (|Wλ| = 1のとき) f(7)(Xλ\ Wλ) (|Wλ| = 2のとき) f(3)(W λ) (|Wλ| = 3のとき) yλ (|Wλ| = 4のとき) yλ (|Wλ| = 5のとき) f(3)(Xλ\ Wλ) (|Wλ| = 6のとき) で定義する． |Yλ| = 5となるλ∈ Λの場合もXλ\ Yλに対して同様の議論をしてxλ∈ Xλを定めて おく． あとは，{Xλ}λ∈Λ の選択関数f : Λ−→ ∪ λ∈ΛXλを f (λ) := x∈ Yλとなるx (|Yλ| = 1のとき) f(7)(Xλ\ Yλ) (|Yλ| = 2のとき) f(3)(Yλ) (|Yλ| = 3のとき) xλ (|Yλ| = 4のとき) xλ (|Yλ| = 5のとき) f(3)(Xλ\ Yλ) (|Yλ| = 6のとき) f(7)(Yλ) (|Yλ| = 7のとき) x∈ Xλ\ Yλとなるx (|Yλ| = 8のとき)
と定義すればよい． 命題 9. ACℵ0 ⇐⇒非空集合の族{Xn}n∈Nに対し，ある無限集合M ⊂ Nが存在して ∏ n∈MXn ̸= ∅ 証明. (=⇒)明らか (⇐=) Ym:= ∏m n=0Xnと置く．各Ymは空でない．{Ym}m∈Nに仮定を適用すると，あ る無限集合M ⊂ Nが存在して∏m∈M Ym ̸= ∅となる．即ち元(ym)m∈M ∈ ∏ m∈M Ym が取れる．ym ∈ Ym = ∏m n=0Xn だから ym = ⟨x m 0 , xm1 ,· · · , xmm⟩ と書ける．そこで m(n) := min{m ∈ M | n ≤ m}と置けば(xm(n)n )n∈N ∈ ∏ n∈NXnである．
参考文献
[1] Thomas J. Jech, The Axiom of Choice, North Holland, Amsterdam, 1973
[2] W. Sierpi´nski, Cardinal and Ordinal Numbers, Polska Akad. Nauk Monogr. Matem. 34, Warszawa, 1958
