2012年08月05日更新

整列可能定理について

PDF版

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

  1. 選択公理
  2. 任意の集合は整列可能 (整列可能定理).
  3. 任意の集合Xに対して,ある順序数αと全単射 X→αが存在する.
  4. 任意の集合Xに対して,ある順序数αと全射α→X が存在する.
  5. 任意の集合Xに対して,ある順序数αと単射 X→αが存在する.

証明 (1 ⇔ 2) 整列可能定理とZornの補題で示した.

(2 ⇒ 3) 整列可能定理によりXの整列順序≦が存在する.順序数の性質により,ある順序数αと順序同型 f: (X, ≦)→αが存在する.f: X→αは勿論全単射である.

(3 ⇒ 4) 明らか.

(4 ⇒ 5) 全射 f: α→X に対して g: X→α を g(x) := min f-1(x) で定めればgは明らかに単射である.

(5 ⇒ 2) 単射 X→α により X⊂α とみなすことによりXは整列集合である.

定理2 整列可能定理 ⇔ 選択関数を持つ集合は整列可能

証明 ⇒は明らか. ←を示す.任意の集合Xに対し,Y := { {x} | x∈X } と置けば,Yは明らかに選択関数を持つ.故にYは整列可能.よって明らかにXも整列可能.

定理3 選択公理
⇔「Xが有限集合⇔(X, ≦)が整列順序ならば(X, ≧)も整列順序」

証明 (⇒) 「Xが有限集合⇒(X, ≦)が整列順序ならば(X, ≧)も整列順序」は明らか.逆を示すため,Xが「(X, ≦)が整列順序ならば(X, ≧)も整列順序」を満たすとする.整列可能定理より整列順序(X, ≦)が存在する.(X, ≦)≅αとなる順序数(α, ≦)が存在する.(X, ≧)の整列性より(α, ≧)も整列順序.故にα∩ω⊂αは(≧に関する)最小元,即ち(≦に関する)最大元を持つ.ω≦αのときα∩ω=ωは最大元を持たないから,α<ω でなければならない.即ちXは有限集合.

(←) 整列できない無限集合Xが存在すると仮定する.このXは明らかに「(X, ≦)が整列順序ならば(X, ≧)も整列順序」を満たす.よって仮定に矛盾. 故に任意の集合は整列可能である.

定理4 次の命題は同値

  1. 任意の集合は整列可能.
  2. 任意の全順序集合は整列可能.
  3. 集合 X が整列可能ならば冪集合 P(X) も整列可能.
  4. 順序数αに対して P(α) も整列可能.

証明 (1⇒2) 自明

(2⇒3) (X, ≦)を整列順序集合とする. P(X) に二項関係 < を

A<B ⇔ ある a∈A\B が存在して任意の b∈B\A に対して a<b

で定める.これによって P(α) が全順序集合になることを確かめる.

(i) ¬A<A について.
A\A= ∅ なので明らか

(ii) A<B ⇒ ¬B<A について.
A<Bとすると < の定義より,あるa0∈A\Bが存在して「任意の b∈B\A に対して a0<b 」となる.よって明らかに ¬B<A である.

(iii) A<B または A=B または B<A について.
A≠B とすると,X は整列順序集合だから a := min( (A\B)∪(B\A) ) が存在する.勿論 a∈A または a∈B であるが,明らかに a∈A ならば A < Bで,a∈B ならば B < A である.

(iv) (A<B かつ B<C) ⇒ A<C について.
¬A<C と仮定する.A=C だとすると A<BかつB<A となり(ii)に反するので A≠B である.故に(iii)から C<A である.A<B, B<C, C<A より

(1) 任意の b∈B\A に対して a0 < b
(2) 任意の c∈C\B に対して b0 < c
(3) 任意の a∈A\C に対して c0 < a

を満たすa0∈A\B, b0∈B\C, c0∈C\Aが存在する.a0∈A\Cである.

a0 ∉ A\C と仮定する.即ちa0∈Ac∪Cである.a0∈A\Bだったから a0 ∈ (Ac∪C)∪(A\B) = A∪C\B ⊂ C\B である.よって(2)により b0 < a0.従って(1)から b0 ∉ B\A でなければならない.すると同様の議論を繰り返して a0 < c0 < b0 < a0 が導かれ,矛盾.

同様にしてb0∈B\A, c0∈C\Bである.従って(1)(2)(3)から a0 < b0 < c0 < a0 となり,矛盾する.

以上より(P(X), <)は全順序集合である.よって,仮定より整列可能である.

(3⇒4) 明らか.

(4⇒1) Xを任意の集合とすると(基礎の公理により)順序数αが存在してX⊂R(α)となる.

基礎の公理とはZFに含まれる公理の1つで x≠∅ ⇒ ∃y∈x( x∩y = ∅ ) を表す.また,順序数αに対しR(α)は

R(α)の定義

と定義される.このとき「ZFから基礎の公理を除いた公理系」の元で「基礎の公理 ⇔ 任意の集合xに対してある順序数αが存在してx∈R(α)」となる. また集合xに対してρ(x) := min{ α | x∈R(α+1) } と定義する.

故にR(α)が整列可能であることを示せばよい.¬|λ|≦|R(α)|となるような順序数λが存在するので,そのようなλを一つとっておく.仮定4によりP(λ)は整列可能である.そこで(P(λ), ≦)が整列順序となるような≦を一つ取っておく.

超限帰納法により,α上の関数Fで 「任意のβ<αに対して Fβ := F(β) は z(β) := { a∈R(α) |ρ(a)=β } を整列する」 を満たすものを構成する.

(i) β=0のとき.
R(0) = ∅ だから F0 := ∅ とすればよい.

(ii) 0<β<αのとき.
帰納法の仮定により,任意のγ<βに対して(z(γ), Fγ)は整列順序である.そこで R(β) = ∪γ<β z(γ) の二項関係 ≦β を次のように定義する.

u≦βv ⇔ ρ(u)<ρ(v)または「ρ(u)=ρ(v), uFρ(u)v」

すると (R(β), ≦β) は整列順序である.

(反射律) Fρ(u) の反射律から明らか.

(反対称律) u≦βv かつ v≦βu とする.ρ(u)=ρ(v)である.即ちuFρ(u)v かつ vFρ(v)u である.今 Fρ(u) が反対称律を満たすから u=v である.

(推移律) u≦βv かつ v≦βw とする.ρ(u)<ρ(v)またはρ(v)<ρ(w)の時は明らかなので ρ(u)=ρ(v)=ρ(w) とする.この時 uFρ(u)v かつ vFρ(u)w であり,Fρ(u) の推移律により uFρ(u)w である.

以上より (R(β), ≦β) は順序集合である.次に任意の部分集合 A⊂R(β) をとる.ξ := min{ρ(u) | u∈A } とする.ξ<βである.B := { u∈A |ρ(u)=ξ } を考える.B⊂z(ξ) であり,Fξ は z(ξ) を整列するからBは最小元u0を持つ.u0の選び方から,これはAの最小元である.即ち (R(α), ≦β) は整列順序集合である.

今 ¬|λ|≦|R(α)| であったから,勿論 ¬|λ|≦|R(β)| であり,よって |R(β)| < |λ| となる. 故にあるμ<λが一意に存在して (R(β), ≦β) ≅ (δ, ≦) である(この同型も一意に定まることに注意する).ここから全単射 f: P(R(β))→P(δ) が自然に定まる.δ⊂λであるから P(δ)⊂P(λ) である.よって(P(δ), ≦)は整列順序である.ここから f により R(β+1) = P(R(β)) の整列順序が定まる.それにより定まる z(β)⊂R(β+1) の整列順序を Fβ と置く.

(i)(ii)により F が定まった.このとき,先と同様にして R(α) の整列順序 ≦α

u ≦α v ⇔ ρ(u)<ρ(v)または「ρ(u)=ρ(v), uFρ(u)v」}

で定めればよい.

定理5 λは基数を表すとし,WO(X, λ)で命題

ある順序数αとα上の関数fが存在して∀β<α( |f(β)| <λ ) かつ X=∪β<α f(β)

を表すことにする.mは2以上の整数を表すとするとき,次の命題は(ZF上)同値.

1. 整列可能定理
2(m). 任意の集合 X に対し WO(X, m)
3. ある m≧2 が存在して任意の集合 X に対し WO(X, m)
4. 任意の集合 X に対しある m≧2 が存在して WO(X, m)
5. 任意の集合 X に対し WO(X, aleph<sub>0</sub>)

証明 1⇔2(2) と 2(m)⇒3 と 3⇒4 と 4⇒5 は明らか.m≦n に対し 2(m)⇒2(n) も明らか.なので 5⇒1 を示せばよい.その為には選択公理と同値なAMCを示せばよい.

AMC(=the Axiom of Multiple Choice)とは次の命題のこと.

集合Xが ¬ ∅ ∈X を満たす時, X上の写像fが存在して,任意のx∈Xに対し f(x)⊂x, 0 < |f(x)| <∞ を満たす

同値性の証明はthe Axiom of Multiple Choiceを参照.

Xを集合とし, ¬ ∅ ∈X とする. 仮定5により WO(∪X, aleph<sub>0</sub>) の条件を満たす順序数αと写像 g が存在する.x∈X に対し β(x) := min{ γ< α | x∩g(γ) ≠ ∅ } と定めて f(x) := x∩g(β(x)) と置けば,この f がAMCを満たす.

基礎の公理を仮定しないと AMC⇒選択公理 は証明できない.つまりこの 5⇒1 の証明は基礎の公理を使っていることになる.実は 5⇒1 は基礎の公理を仮定しないと証明できないことが知られている.( 5⇔AMC は基礎の公理を使わずに証明できる.)一方,4⇒1 は基礎の公理を使わなくても証明できるので,その証明を書いておく.

証明 まず Y×Y⊂Y を満たす集合 Y が整列可能であることを示す.m>1 で WO(Y, m) が成立しているとする. (この時 WO(Y, m-1) であることをこれから示す.) WO(Y, m) の条件を満たす順序数αと関数 f を取り

u(β, γ, δ) := (f(β)×f(γ))∩f(δ) (β, γ, δ<α)

を考える.定義より u(β, γ, δ) は二項関係とみなせる. (即ち定義域 dom,値域 ran を考えることができる.) fの性質から

| dom(u(β, γ, δ)) |≦| f(β) |≦m
| ran(u(β, γ, δ)) |≦| f(γ) |≦m
| u(β, γ, δ) |≦| f(δ) |≦m

である.

(i)全てのβ<αに対し「f(β)≠∅⇒∃γ, δ<α(0< |dom(u(β, γ, δ))| <m)」の時.
f(β)≠ ∅ なるβ<αに対し,0<| dom(u(β, γ, δ)) |<mとなる組<γ, δ>のうち辞書式順序で最小のものを<λβ, μβ>で表す.

f(β)≠ ∅ の時 vβ := dom(u(β, λβ, μβ))
f(β)= ∅ の時 vβ := ∅
wβ := f(β)\vβ

と置き,α+α上の関数gを

β<αの時 g(β) := vβ
α≦β, β\α≅γ<αの時 g(β) := wγ

で定義する.すると∪β<α+α g(β) = y である.次に,定義から明らかに | vβ|<m, | wβ|<m だから | g(β) |≦m-1 (β<α+α)である.即ち,α+αとgが WO(Y, m-1) の条件を満たす.

(ii)あるβ≦αについて「f(β)≠∅かつ∀γ, δ<α(| dom(u(β, γ, δ)) |=0 or m)」の時.
このようなβのうち最小のものを取り,s∈f(β)とする.γ, δ<αがdom(u(β, γ, δ))≠∅を満たすとする.この時 | dom(u(β, γ, δ)) |=m である.| u(β, γ, δ) |≦m だったから,| u(β, γ, δ) |=m で,u(β, γ, δ)は関数でなければならない.さて,f(γ)≠ ∅ であるとすると Y×Y⊂Y より u(β, γ, δ)≠ ∅ となるδが存在するので,そのようなδのうち最小のものをδγと書く.

f(γ)≠ ∅ の時 vγ := { u(β, γ, δγ)(s) }
f(γ)= ∅ の時 vγ:= ∅
wγ := f(γ)\vγ

と置き,α+α上の関数gを

γ<αの時 g(γ) := vγ
α≦γ, γ\α≅λ<αの時 g(γ) := wλ

で定義する.すると(i)の場合と同様,α+αとgが WO(Y, m-1) の条件を満たす.

(i)(ii)より WO(Y, m-1) が成立する.仮定4. より WO(Y, m) が成立するmは存在するから,WO(Y, 1)が成立することが分かる.即ち,Y は整列可能である.

さて,X を任意の集合とする.この時

Z0 := X, Zn+1 := Zn ∪(Zn×Zn), Y := ∪n=0∞ Zn

と置く.すると m<n の時 Zm ⊂ Zn, Zm×Zm ⊂ Zn だから

Y×Y=∪_{m, n=0}^{∞}Z_m×Z_n⊂∪_{m, n=0}^{∞}Z_{max(m, n)}×Z_{max(m, n)}⊂∪_{m, n=0}^{∞}Z_{max(m, n)+1}⊂Y

よって先に述べた通り Y は整列可能であり,明らかに X⊂Y だから X も整列可能である.

参考文献

コメント

匿名 | 2017年12月 9日 03:24

瑣末なtypoですが、定理1の証明の最後の行
(5 ⇒ 2) であるべきと思われる箇所が (5 ⇒ 6) になっています

管理人 | 2017年12月 9日 04:46

ありがとうございます。直しました。

コメントする

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