■

[集合論] Well-Founded Relations (Jech本 p.25)

　
　例によって、テキストで引っかかったところをネタにするノート記事である．

＜well-founded relation＞

集合 P上の二項関係 Eが次の性質を持つとき、Eを well-foundedという．
Pの任意の部分集合 X \subset Pに対して、Pの元 aで
\forall x \in X : \neg x E a
なるものが存在する（これを E-minimal な元と呼ぶ）．

well-founded な二項関係Eと集合Pを合わせて、well-founded setと呼ぶ．


Eをあたかも大小関係'<'のように見たときに、任意の部分集合に最小元が存在するという well-orderd set の一般化になっているというわけである．もちろん一般的には Eは順序関係ですらない．とはいえ、このままではつまらない一般化に見えるが、次の定理がなんともすごい．Pを関係Eでの極小元から数え上げて階層づけできるというイメージである．

＜定理＞（Jech本 Theorem 2.27）

Eを集合 P上のwell-foundedな二項関係とする．このとき Pから順序数のクラスOrdへの関数で次の式を満たす\rho : P \to Ordが唯一存在する．
\forall x\in P:\rho(x)=sup_y\{\rho(y)+1:y E x\}
また、このとき値域 ran\ \rhoは一つの順序数となる（これをEのheightと呼ぶ）．

＜証明＞
対応を逆にして、順序数に対して Pの部分集合を超限再帰的に定義する．
P_0:=\emptyset, P_{\alpha+1}:=\{x\in P:\forall y(yEx \to y\in P_{\alpha}\},
P_{\alpha}:=\cup_{\xi < \alpha}P_{\xi}　　 \alphaが極限順序数のとき.

\alpha+1の定義の心は、xの下があるならそれは P_{\alpha}の元に限るというような意味合いである．ただし、x\in P_0のとき、yExなるyが存在しないので、条件式の前提が常にfalseとなるため P_0 \subset P_1であることを注意すれば、\alpha < \betaならば P_\alpha \subset P_\betaであることが超限帰納法で示せる（∵ \betaが極限順序数なら定義から自明．\beta=\beta'+1の時は、さらに

(i) \beta'が後続順序数の場合：
\beta'=\beta''+1とすれば、定義より x\in P_{\beta'}=\{x\in P:\forall y(yEx \to y\in P_{\beta''}\}であるが、超限帰納法の仮定から P_{\beta''} \subset P_{\beta'}であるため、後続順序数に対するPの定義から包含関係を＋１進めたP_{\beta''+1} \subset P_{\beta'+1} すなわち P_{\beta'} \subset P_{\beta}が成立する．
(ii)\beta'が後続順序数の場合：
定義より x\in P_{\beta'}\Rightarrow \exists \beta'' < \beta' (x \in P_{\beta''})で、超限帰納法の仮定から P_{\beta''} \subset P_{\beta'}なので P_{\beta''+1} \subset P_{\beta'+1}=P_{\beta}．\beta'' < \beta''+1 < \betaなので再び超限帰納法の仮定から P_{\beta'} \subset P_{\beta''+1}．これらより、x \in P_{\beta}．よって、P_{\beta'} \subset P_{\beta}．
より、超限帰納法が完成する．）


さて、ここでJech本では P_\theta = P_{\theta+1}なるような、\thetaが置換公理により存在するとさらっと主張している．StackExchangeでもこの点の質問があったが、その解答を紹介しよう．もしこのような\thetaが存在しないとすると \phi(\theta):= P_{\theta+1}\setminus P_\thetaの値は空集合でなく、順序数全体のクラスからPのベキ集合への単射になっている（∵ 単射であるのは \theta+1より小さい順序数\theta'に対する P_{\theta'}がすべて \phi(\theta)から除かれてしまっているため）．そして\phiの像に対しては、この\phiの逆写像を考え、\phiの像に入っていないPの部分集合に対しては 0を対応させれば、Pのベキ集合から、順序数全体のクラスへの全射が得られることになる（これらの対応はすべて関数クラスである．念のため）．しかし、これは置換公理により順序数全体のクラスが集合であることになるので、不合理である．
　さて， P_\theta = P_{\theta+1}となったとしよう．このとき，\theta < \theta'に対しても，P_{\theta'}=P_\thetaとなる．その証明は\theta' > \thetaをP_{\theta'}\neq P_\thetaなる最小の順序数とする：

((i) \theta'=\theta''+1 のとき：
　仮定より，\theta \le \theta''でP_{\theta''} = P_{\theta}. これよりP_{\theta''+1} = P_{\theta+1}=P_{\theta}であるから，\theta'の定義に反する．
(ii) \theta'が極限順序数のとき：
　定義より P_{\theta'}=\cup_{\xi < \theta'}P_{\xi}=\cup_{\theta \le \xi < \theta'}P_{\xi}=\cup_{\theta \le \xi < \theta'}P_{\theta}=P_{\theta}は\theta'の定義に反する．

続いて，P=P_{\theta}を証明する．もしそうでないとすると P\setminus P_{\theta}にE-minimalな元 aが存在する．E-minimal の定義より \forall y( yEa \to y\in P_{\theta})となるが，これは a\in P_{\theta+1}そのもので，P_{\theta+1}=P_{\theta}なのでaの決め方に矛盾する．

P_\alphaの準備ができたので，\rhoを次のように定義する．

x \in Pに対して，\rho(x):= min\{\xi:x\in P_{\xi+1}\}

このとき xEyならば，\rho(x) < \rho(y)である（∵ y\in P_{\rho(y)+1}なので，定義から x\in P_{\rho(y)}でなければならない．\rho(y)が後続順序数なら \xi+1=\rho(y)で x\in P_{\xi+1}だから \rho(x) \le \xi < \rho(y). \rho(y)が極限順序数なら \exists \xi < \rho(y)(x\in P_{\xi})．x\in P_{\xi} \subset P_{\xi+1}なので \rho(x) \le \xi < \rho(y) □）

定理の等式を証明しよう．yExより\rho(y) < \rho(x)なので\rho(y)+1 \le \rho(x)．よって、\rho(x) \ge sup_y\{\rho(y)+1:yEx\}は直ちに出る．ここでさらに > が成立しないことを見る．
まず，x\in P_{\rho(x)+1} \wedge x \notin P_{\rho(x)}である（∵もしx\in P_{\rho(x)}なら，\rho(x)が後続順序数なら直ちに矛盾だし，極限順序数なら \exists \xi < \rho(x) (x \in P_{\xi})だが，\xi+1 < \rho(x) かつ x \in P_{\xi}\subset P_{\xi+1}なのでこれも\rho(x)の定義に矛盾する）．さて，\exists \xi < \rho(x)で，\forall y (yEx \to y\in P_{\xi})となってしまうと，x \in P_{\xi+1}より，\rho(x) \le \xiで矛盾する．よって yExなるyの中に y \notin P{\xi} \wedge y\in P_{\rho(x)}なるものがあるが，もし\rho(y) < \xi ならば \rho(y)+1 \le \xi より y\in P_{\rho(y)+1} \subset P_{\xi}は矛盾なので， \xi \le \rho(y). よって，\xi < \rho(y)+1 \le \rho(x)かつ yExなるyが存在する．さて，もし\rho(x) > sup_y\{\rho(y)+1:yEx\}ならば \xi=sup_y\{\rho(y)+1:yEx\}に対して，\xi < \rho(y)+1 かつ yExなるyが存在するが，\rho(y)+1 \in sup_y\{\rho(y)+1:yEx\}=\xiより \rho(y)+1 < \xiは矛盾である□

　最後に heightが \thetaに等しいことを証明する．ここでひとつ重要な注意を．私も一時ハマって『気づいてしまったシリーズ』のネタに入りかけたのだが，定理のステートメント ran\ \rho=\theta は集合としての一致であり，左辺はそもそも順序数であるかどうかは自明ではない．この左辺はsup\{ran\ \rho\} の意味では決してない．なぜなら\thetaが極限順序数でないときは，sup\{ran\ \rho\} \neq \thetaである．例えば１点 xしかない集合で，E=\emptysetとするとトリビアルに well-founded だが，P_0=\emptyset,\ P_1={x}であり，\theta=1．一方 \rho(x)=0となっている．sup\{lo(x)\}=0 \neq 1=\thetaである．しかし，集合としては \{0\}=1で確かに成立している．
　さて， ran\ \rho=\thetaを示そう．

\thetaが後続順序数のとき：
\theta=\theta'+1として，P=P_{\theta}=P_{\theta'+1}なので \forall x \in P \Rightarrow \rho(x) \le \theta'． よって，ran \rho \subset \theta．逆向きは \forall \xi \le \theta'に対して，\xi+1 \le \theta'+1=\thetaだから P_{\xi} \subsetneq P_{\xi+1}なので x \in P_{\xi+1} \wedge x \notin P_{\xi}なるxが存在するが，このとき\rho(x)=\xiである（∵ \rho(x) < \xiだとすると \rho(x)+1 \le \xiより x\in P_{\rho(x)+1} \subset P_{\xi}は xの取り方に矛盾）□
\thetaが極限順序数のとき：
x\in P=P_{\theta}=\cup_{\xi < \theta}P_{\xi}より \exists \xi(x \in P_{\xi})．\xi+1 < \thetaなので \rho(x) < \theta. よって，ran\ \rho \subset \theta．逆向きは \forall \xi < \thetaに対して，\xi < \xi+1 < \thetaなので P_{\xi} \subsetneq P_{\xi+1}．x \in P_{\xi+1} \wedge x \notin P_{\xi}なるxが存在するが，このとき\rho(x)=\xiであるのは先と同じ理由である □

というわけで，特に\rho(x) < \thetaなのであり，等号は成立していない．