連続体仮説の勉強その1：超限再帰のおさらい - ひかりちゃんの悲観的絵日記

　趣味の数学で次に何をやろうかなと思って，連続体仮説まわりの話と測度論ベースの複素解析が候補に挙がりました．これらは二者択一ではなく，気分によって好きな方をやるとかでもよいと思うのですが，とりあえず先に連続体仮説関連の勉強をしようと思います．

　連続体仮説（continuum hypothesis, CH）とは，「自然数よりサイズが真に大きくて，実数よりサイズが真に小さい集合は存在しない」という主張です．CHはZFCから独立であることが示されています．すなわち，ZFCではCHを証明も反証もできません．

　「連続体仮説の勉強」ということで私が意味するのは，この独立性の証明を追うことです．テキストとしては独立性証明に大きく貢献した（ZFCの公理からCHは証明できないことを示した）Paul J. CohenのSet Theory and the Continuum Hypothesis, Dover, 2008（オリジナルはW. A. Benjaminから1966年に出た）を使おうと思っています．これはCHの独立性証明がなされた数年後に書かれた解説書です．

　ただ，私も集合論の勉強を離れて久しいので，もう順序数の定義からして忘れています．よく分からないけれど，とにかく順序数の理解は必要なはずです．なので少し復習タイムを設けたいと思います．テキストとしてはH. B. Enderton, Elements of Set Theory, Academic Press, 1977を使います．

　順序数（ordinal number）というのは一般化された自然数みたいなやつです．自然数自体は「無限大」のような数を含みませんが，そうした「無限大」の数として $\omega$ というものを作り， $\omega$ よりも大きな無限の数があって，自然数みたいなノリでどんどん続いていくというイメージです．

　自然数自体は無限公理というやつを使って天下り式に作るのですが，順序数を作るにはもう少しステップが要ります．その際に超限再帰（transfinite recursion）という道具を使います．超限再帰は自然数上の再帰の一般化みたいなやつです．今回はこの超限再帰までおさらいします．

　自然数上の再帰といえば，たとえば $+3$ する関数 $+_{3}$ を $+_{3}(0)=3$ ， $+_{3}(suc(n))=suc(+_{3}(n))$ のように定義するやつです（自然数 $n$ に対して $suc(n)$ は $n$ の後続数）． $6+3=(5+1)+3=(5+3)+1=9$ みたいなノリですね．こういう「再帰的定義」がなぜ許されるのかというと，以下の再帰定理が成り立つからです． $\omega$ は自然数全体の集合を表すものとします．

自然数上の再帰定理

$A$ を何らかの集合， $a$ をその要素， $F$ は $A$ から $A$ への関数とする．このとき，関数 $h:\omega \to A$ で， $h(0)=a$ ， $h(suc(n))=F(h(n))$ を満たすものが唯一存在する．*1

ここで存在を主張されている関数 $h$ が，いわゆる再帰的に定義される関数です． $F$ には「 $h(n)$ が与えられたときに $h(suc(n))$ の値を決めてくれるやつ」が入ります．上に挙げた関数 $+_{3}:\omega \to \omega$ のケースだと， $suc: \omega \to \omega$ がちょうどこの $F$ にあたります．

　自然数上の再帰ができるのは $\omega$ がいい感じの順序構造をもっているからですが，実は再帰っぽいことは任意の整列集合上でできます（集合 $A$ 上の整列順序（well-ordering）とは，線型順序であって， $A$ の空でない任意の部分集合がその順序に関する最小元をもつようなものです）．これが超限再帰です．以下に記すのは超限再帰の強力なバージョンである，超限再帰定理図式（transfinite recursion theorem schema）です．

超限再帰定理図式

$>$ を集合 $A$ 上の整列順序とする．このとき， $\gamma$ が集合全体のクラス上で定義された関数クラスならば， $A$ を定義域とする関数 $h$ であって， $t \in A$ に対して $h(t)=\gamma(h\restriction{seg \ t})$ となるような関数 $h$ が唯一存在する．*2

　色々と分からない言葉が出てきたので，順に説明していきます．まず「関数クラス」ですね．世の中には関数っぽいけど定義域が大きすぎて関数になれないようなものがあります．たとえば，集合を食ってその値域（range）を返すようなものは関数っぽく見えますが，定義域が集合全体のクラスでは大きすぎて集合になれません（一般の集合に対して値域と言うのは異様な気がしますが，関係でないタイプの集合の値域としては空集合が振られます）．こういうものに言及する方法として，論理式にメタで言及するというものがあります．つまり，項 $x$ に対して $\gamma(x, y)$ なる項 $y$ が唯一存在するような穴あき論理式 $\gamma(x, y)$ を考えると（たとえば「 $y$ は $x$ の値域である」），これは関数っぽいものになり， $\gamma(x)=y$ という形で表して（記法の濫用）、これを関数クラスと呼んでいます．

　次に $h\restriction{seg \ t}$ です．まず， $\restriction$ は関数の制限です．関数 $h$ に対して $h\restriction{A}$ は $h$ の定義域を $A$ に制限して得られる関数です．順序づけられた集合 $A$ の元 $t$ に対して $seg \ t$ とは， $A$ の要素で $t$ より小さいようなものを集めた集合です（「始切片 initial segment」と呼ばれます）．つまり， $h\restriction{seg \ t}$ は $h$ の定義域を $t$ より小さいやつに制限して得られた関数ということですね．

　こうしてみると，超限再帰は $\omega$ 上の再帰の一般化という感じがしてきますね． $\omega$ 上の再帰における関数 $F$ が関数クラス $\gamma$ に替わって， $\omega$ が任意の整列集合に替わっています（相違点としては、 $\omega$ 上では「1個前」の自然数に関する値から次の自然数に関する関数の値を定められれば良かったのに対して、超限再帰では「今の元より小さいやつ全部」に関する関数の情報が必要になる、ということがあります）．超限再帰定理図式が言っていることは，「 $t$ より小さい要素に関する $h$ の情報が全部与えられたときに $h(t)$ の値を決められるような規則 $\gamma$ があれば，整列集合上でなら，その規則で定まりそうな関数 $h$ をちゃんと定義できるよ」ということです．

　超限再帰の応用の例として分かりやすいのは順序数の構成なのですが，今回は長くなってきたのでここらで終わりにします．次回は順序数を構成します．

*1:cf. H. B. Enderton, Elements of Set Theory, Academic Press, 1977, pp. 73-74.

*2:cf. 上掲書， p. 177.