日記 (2020 年 6 月 5 日)
5 月 31 日と 6 月 1 日の続き。
今回は、 再帰定理を証明し、 その応用として整列可能定理を示す。
順序数 α を固定し、 順序数 ξ<α に関して定められた命題 Φ(ξ) を考える。
超限帰納法の原理により、 順序数 ξ<α に関して命題 Φ(ξ) が成り立つことを示すためには、 任意の順序数 η<ξ に対して Φ(η) が成り立つことを仮定した上で Φ(ξ) が示されれば良いのであった。
これから証明する再帰定理はこれに似ていて、 順序数 ξ<α に関して何らかの集合 f(ξ) を構成するためには、 任意の順序数 η<ξ に対して f(η) が構成されている状態で f(ξ) を構成すれば良いということを保証するものである。
定理 4.1 [再帰定理 (recursion threorem)].
順序数 α と集合 R に対し、 写像 r:⋃ξ<αRξ→R が定まっているとする。
このとき、 写像 f∈Rα が一意に存在して、 任意の順序数 ξ<α に対して f(ξ)=r(f|ξ) が成り立つ。
証明の前に、 この定理の気持ちを述べておこう。
順序数 α と集合 R に対して、 R の元からなる列 (f(ξ))ξ<α を作りたいとする。
定理によると、 これを作るためには、 写像 r:⋃ξ<αRξ→R を用意すれば良いことになる。
この r の定義域である ⋃ξ<αRξ は非交和になっているので、 r を用意することは、 各順序数 ξ<α に対する写像 rξ:Rξ→R たちの族を用意するのと同じである。
この rξ は、 最終的に作りたい列の途中までができている列 (f(η))η<ξ から f(ξ) を構成する役割を担っている。
言い方を変えれば、 rξ は、 作りたい列が ξ 番目の手前までできていると仮定した上で ξ 番目の値を作る操作を表している。
定理の主張は、 このような操作の族が揃っていれば最終的に完全な列 f が構成できるということである。
すなわち、 再帰的な定義を正当化している。
証明.
以下、 集合 R は常に固定する。
順序数 α と写像 r:⋃ξ<αRξ→R をとる。
写像 f∈Rα に対して、
- 任意の順序数 ξ<α に対して f(ξ)=r(f|ξ) が成り立つ。
という条件のことを、 条件 ♤α(r) と呼ぶことにする。
定理の主張は、 条件 ♤α(r) を満たす写像 f∈Rα が一意に存在することである。
まず、 各順序数 α と写像 r:⋃ξ<αRξ→R に対して、 条件 ♤α(r) を満たす f の一意性を示す。
そのため、 条件 ♤α(r) を満たす f,g∈Rα をとる。
ここで、
Z:={ξ∈α∣f(ξ)=g(ξ)}⊆α
とおき、 超限帰納法によって Z=α を示す。
これが示されれば、 f=g となって一意性が得られる。
任意に ξ∈α をとり、 O(ξ)⊆Z であるとする。
Z の定義により、 これは任意の η<ξ について f(η)=g(η) であるということだが、 それはすなわち f|ξ=g|ξ が成り立つということである。
f と g は条件 ♤α を満たすから、
f(ξ)=r(f|ξ)=r(g|ξ)=g(ξ)
となり、 ξ∈Z が示された。
次に、 任意の順序数 α と写像 r:⋃ξ<αRξ→R に対して、 条件 ♤α(r) を満たす f の存在を示す。
これは背理法による。
そこで、 ある順序数 α と写像 r:⋃ξ<αRξ→R が存在して、 条件 ♤α(r) を満たす f が存在しないと仮定する。
さらに、 α はそのような順序数のうち最小のものとする。
α が後続順序数か極限順序数かに応じて場合分けする。
α が後続順序数のとき。
このとき、 ある順序数 β によって α=β+1 と書ける。
β<α であるから、 α の最小性によって、 条件 ♤β(r) を満たす写像 fβ∈Rβ は存在する。
そこで、
fα: β+1 ⟶ R ξ ⟼ { fβ(ξ) (ξ<β) r(fβ) (ξ=β)
とおくと、 この写像 f∈Rα は条件 ♤α(r) を満たすことが容易に分かる。
これは矛盾である。
α が極限順序数のとき。
任意の順序数 ξ<α に対して、 α の最小性によって、 条件 ♤ξ(r) を満たす写像 fξ∈Rξ は存在する。
α が極限順序数であることから、 ξ+1<α であることに注意して、
fα: α ⟶ R ξ ⟼ fξ+1(ξ)
とおく。
ここでまず、 任意の順序数 ξ<α に対して fξ+1|ξ=fα|ξ が成り立つことを示す。
任意に元 η∈ξ をとると、 fξ+1|η+1 と fη+1 はともに条件 ♤η+1(r) を満たす。
すでに示したようにそのような写像は一意だから、 fξ+1|η+1=fη+1 が成り立つ。
したがって、 特に
fξ+1(η)=fξ+1|η+1(η)=fη+1(η)=fα(η)
が成り立つ。
η は任意にとったので、 fξ+1|ξ=fα|ξ が示された。
この事実を用いると、 任意の順序数 ξ<α に対して、
fα(ξ)=fξ+1(ξ)=h(fξ+1|ξ)=h(fα|ξ)
が成り立つので、 fα は条件 ♤α(r) を満たす。
これは矛盾である。
どちらの場合でも矛盾が導かれたので、 これで証明が完了した。
再帰定理の応用として、 整列可能定理を示す。
その証明で用いるので、 ここで置換公理図式と選択公理について復習しておく。
特に、 選択公理は整列可能定理と (他の公理を仮定した上で) 同値であることが知られている。
公理 4.2 [置換公理図式 (axiom schema of replacement)].
2 変数の論理式 Φ があり、 任意の集合 x に対して集合 y が一意に存在して Φ(x,y) が成立するとする。
このとき、 任意の集合 X に対してある集合 Y が存在し、 y∈Y であることが、 ある x∈X が存在して Φ(x,y) が成り立つことと同値になる。
この公理図式から、 ある集合 X の元 x に対して、 (ある一定の集合に属しているとは限らない) 何らかの集合 F(x) を構成する操作があるとき、 そのようにして作られる F(x) たちの集まり全体も集合になるということが分かる。
公理 4.3 [選択公理 (axiom of choice)].
空でない集合から成る集合 に対し、 関数 Γ:→⋃ が存在し、 任意の S∈ に対して Γ(S)∈S が成り立つ。
なお、 Γ は 上の 「選択関数 (choice function)」 と呼ばれる。
さて、 再帰定理の応用として次の整列可能定理を示す。
定理 4.4 [整列可能定理 (well-ordering theorem)].
任意の集合 X に対し、 X 上の整列順序が存在する。
厳密な証明に入る前に、 証明の方針を軽く述べておく。
証明の最終的な目標は、 ある順序数から X への全単射を作ることである。
これを作ることができれば、 順序数に定まっている整列順序をそのまま使って X に整列順序を定めることができる。
そのために、 十分大きな順序数 α をとって、 X の元もしくは後述する特殊な元 ⊥ のどちらかから成る列 (f(ξ))ξ<α を、 再帰的に次のように構成することを考える。
ξ 番目の手前まで列が構成できていたとして、 そこまででまだ現れていない X の元を新しくとって f(ξ) とする。
もし、 ξ 番目の手前までで X の元をとり尽くしてしまっていたら、 そのことを明示するために ⊥ という特殊な元を用意してそれを f(ξ) とする。
このようにすると、 列 (f(ξ))ξ<α は、 下から順に X の元が相異なるように入っていて、 X の元を全てとり尽くしたらそれ以降はずっと ⊥ が入っているものになっている。
したがって、 初めて ⊥ が現れる地点のすぐ手前でこの列を切れば、 順序数から X への全単射が得られたことになる。
証明.
まず、
:={ord(Y,⪯)| Y∈(X),⪯∈(X×X) ⪯ は Y 上の整列順序{
とおくと、 置換公理図式によってこれは集合である。
これは、
={ξ| ξ は順序数 単射 f:ξ→X が存在する{
とも書ける。
ここで、 順序数 α であって α∉ なるものをとって固定する。
そのためには、 例えば α:=⋃+1 とすれば良い。
ある集合 ⊥ であって ⊥∉X なるものをとる。
例えば ⊥:=X とすれば良い。
さらに、 (X)∖{∅} 上の選択関数を Γ:(X)∖{∅}→X とする。
このとき、
r: ξ<α(X∪{⊥})ξ ⟶ X∪{⊥} h ⟼ { Γ(X∖Imh) (X∖Imh≠∅) ⊥ (X∖Imh=∅)
と定める。
すると、 再帰定理により、 写像 f∈(X∪{⊥})α が存在し、 任意の順序数 ξ<α に対して、
f(ξ)=r(f|ξ)={ Γ(X∖f[ξ]) (X∖f[ξ]≠∅) ⊥ (X∖f[ξ]=∅)♡
が成り立つ。
ここで、 順序数 β≤α に対して、 ⊥∉f[β] ならば f|β:β→X は単射であることを示す。
任意に相異なる元 ξ,ξ∈β をとる。
ξ<ξ と仮定して良い。
すると、 ⊥∉f[β] であることから f(ξ)≠⊥ なので、 式 ♡ によって、
f(ξ)=Γ(X∖f[ξ])∈X∖f[ξ]
が成り立つ。
一方、 ξ<ξ より ξ∈ξ であるから、 f(ξ)∈f[ξ] が成り立つ。
これより、 f(ξ)≠f(ξ) でなければならない。
以上により、 f|β が単射であることが示された。
次に、 ⊥∈f[α] であることを示す。
仮に ⊥∉f[α] であるとすると、 上の議論によって f|α:α→X は単射である。
したがって、 の定義によって α∈ であるが、 そもそも α は α∉ が成り立つようにとったのだからこれは矛盾である。
以上により、 ⊥∈f[α] が示された。
このことから、
S:={β∈α∣f(β)=⊥}⊆α
とおくと S≠∅ が成り立つので、 β:=minS がとれる。
β の最小性によって ⊥∉f[β] であるから、 前の議論によって f|β:β→X は単射である。
また、 f(β)=⊥ であるから、 式 ♡ により X∖f[β]=∅ でなければならないので、 f|β:β→X は全射でもある。
以上をまとめると、 f|β:β→X は全単射であるから、 X 上の関係 ⪯ を、
x⪯x:⟺f−1(x)≤f−1(x)
で定めれば、 β が整列集合であることからこれは整列順序になる。
これが示したかったことであった。
参考文献
- K. Ciesielski (1997) 『Set Theory for the Working Mathematician』 Cambridge University Press