日記 (2020 年 6 月 5 日)

5 月 31 日6 月 1 日の続き。 今回は、 再帰定理を証明し、 その応用として整列可能定理を示す。

順序数 α を固定し、 順序数 ξ<α に関して定められた命題 Φ(ξ) を考える。 超限帰納法の原理により、 順序数 ξ<α に関して命題 Φ(ξ) が成り立つことを示すためには、 任意の順序数 η<ξ に対して Φ(η) が成り立つことを仮定した上で Φ(ξ) が示されれば良いのであった。 これから証明する再帰定理はこれに似ていて、 順序数 ξ<α に関して何らかの集合 f(ξ) を構成するためには、 任意の順序数 η<ξ に対して f(η) が構成されている状態で f(ξ) を構成すれば良いということを保証するものである。

定理 4.1 [再帰定理 (recursion threorem)].

順序数 α と集合 R に対し、 写像 r:ξ<αRξR が定まっているとする。 このとき、 写像 fRα が一意に存在して、 任意の順序数 ξ<α に対して f(ξ)=r(f|ξ) が成り立つ。

証明の前に、 この定理の気持ちを述べておこう。 順序数 α と集合 R に対して、 R の元からなる列 (f(ξ))ξ<α を作りたいとする。 定理によると、 これを作るためには、 写像 r:ξ<αRξR を用意すれば良いことになる。 この r の定義域である ξ<αRξ は非交和になっているので、 r を用意することは、 各順序数 ξ<α に対する写像 rξ:RξR たちの族を用意するのと同じである。 この rξ は、 最終的に作りたい列の途中までができている列 (f(η))η<ξ から f(ξ) を構成する役割を担っている。 言い方を変えれば、 rξ は、 作りたい列が ξ 番目の手前までできていると仮定した上で ξ 番目の値を作る操作を表している。 定理の主張は、 このような操作の族が揃っていれば最終的に完全な列 f が構成できるということである。 すなわち、 再帰的な定義を正当化している。

証明.

以下、 集合 R は常に固定する。 順序数 α と写像 r:ξ<αRξR をとる。 写像 fRα に対して、

という条件のことを、 条件 α(r) と呼ぶことにする。 定理の主張は、 条件 α(r) を満たす写像 fRα が一意に存在することである。

まず、 各順序数 α と写像 r:ξ<αRξR に対して、 条件 α(r) を満たす f の一意性を示す。 そのため、 条件 α(r) を満たす f,gRα をとる。 ここで、 Z:={ξαf(ξ)=g(ξ)}α とおき、 超限帰納法によって Z=α を示す。 これが示されれば、 f=g となって一意性が得られる。

任意に ξα をとり、 O(ξ)Z であるとする。 Z の定義により、 これは任意の η<ξ について f(η)=g(η) であるということだが、 それはすなわち f|ξ=g|ξ が成り立つということである。 fg は条件 α を満たすから、 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β) (ξ=β) とおくと、 この写像 fRα は条件 α(r) を満たすことが容易に分かる。 これは矛盾である。

α が極限順序数のとき。 任意の順序数 ξ<α に対して、 α の最小性によって、 条件 ξ(r) を満たす写像 fξRξ は存在する。 α が極限順序数であることから、 ξ+1<α であることに注意して、 fα: α R ξ fξ+1(ξ) とおく。

ここでまず、 任意の順序数 ξ<α に対して fξ+1|ξ=fα|ξ が成り立つことを示す。 任意に元 ηξ をとると、 fξ+1|η+1fη+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 が存在し、 yY であることが、 ある xX が存在して Φ(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 { Γ(XImh) (XImh) (XImh=) と定める。 すると、 再帰定理により、 写像 f(X{})α が存在し、 任意の順序数 ξ<α に対して、 f(ξ)=r(f|ξ)={ Γ(Xf[ξ]) (Xf[ξ]) (Xf[ξ]=) が成り立つ。

ここで、 順序数 βα に対して、 f[β] ならば f|β:βX は単射であることを示す。 任意に相異なる元 ξ,ξ󰎘β をとる。 ξ<ξ󰎘 と仮定して良い。 すると、 f[β] であることから f(ξ󰎘) なので、 式 によって、 f(ξ󰎘)=Γ(Xf[ξ󰎘])Xf[ξ󰎘] が成り立つ。 一方、 ξ<ξ󰎘 より ξξ󰎘 であるから、 f(ξ)f[ξ󰎘] が成り立つ。 これより、 f(ξ)f(ξ󰎘) でなければならない。 以上により、 f|β が単射であることが示された。

次に、 f[α] であることを示す。 仮に f[α] であるとすると、 上の議論によって f|α:αX は単射である。 したがって、 󰒝 の定義によって α󰒝 であるが、 そもそも αα󰒝 が成り立つようにとったのだからこれは矛盾である。 以上により、 f[α] が示された。

このことから、 S:={βαf(β)=}α とおくと S が成り立つので、 β:=minS がとれる。 β の最小性によって f[β] であるから、 前の議論によって f|β:βX は単射である。 また、 f(β)= であるから、 式 により Xf[β]= でなければならないので、 f|β:βX は全射でもある。 以上をまとめると、 f|β:βX は全単射であるから、 X 上の関係 を、 xx󰎘:⟺f1(x)f1(x󰎘) で定めれば、 β が整列集合であることからこれは整列順序になる。 これが示したかったことであった。

参考文献

  1. K. Ciesielski (1997) 『Set Theory for the Working Mathematician』 Cambridge University Press