2012年1月 1日更新

制限された選択公理

PDF版

選択公理とは,非空集合の族{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)アレフ0はZFで証明できない(Jech『The Axiom of Choice』p71参照)など.

命題1AC(2)⇔AC(4)

証明(⇒) {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_λ}_{λ∈Λ}を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を得ることができる.

補題3pを素数,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λである.

補題4nを正整数とする. 「任意の素数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)が成り立つ.

命題5nを正整数とする. 「任意の素数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 が{X_λ}_{λ∈Λ}の選択関数である.故にAC(k)が成り立つ.

命題5でn=2とすれば先の AC(2)⇒AC(4) が得られる.またn=4とすれば AC(2)かつAC(3) からAC(6),AC(8),AC(9)が得られることが分かる.よって AC(2)かつAC(3) ⇔ AC(6) も分かる.

命題6AC(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_λ

と定義すればよい.

命題7AC(10)⇒AC(8)

証明AC(10)⇒AC(2) と AC(10)⇒AC(5) により明らか.

命題8AC(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λ

と定める.

(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λ

で定義する.

|Yλ|=5となるλ∈Λの場合も Xλ\Yλに対して同様の議論をして xλ∈Xλを定めておく.

あとは,{X_λ}_{λ∈Λ}の選択関数f: Λ→∪_{λ∈Λ}X_λ

と定義すればよい.

命題9ACアレフ0
⇔非空集合の族{ Xn }n∈Nに対し,ある無限集合M⊂Nが存在してΠn∈M Xn≠∅

証明(⇒)明らか

(←) Ym := Πn=0m Xnと置く.各Ymは空でない.{ Ym }m∈N に仮定を適用すると, ある無限集合 M⊂N が存在してΠm∈M Ym≠∅となる. 即ち元( ym )m∈M∈Πm∈M Ymが取れる. ym∈Ymn=0m Xnだから ym = < x0m, x1m, …, xmm> と書ける. そこで m(n) := min{ m∈M | n≦m } と置けば (xnm(n))n∈N∈Πn∈N Xnである.

参考文献

コメント

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

コメントする

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