備忘録：超限帰納法
記事を書くのに慣れる意味も込めて備忘録を書く．
全順序集合 $(A,\le)$ のどんな空でない部分集合も最小元をもつとき，$(A,\le)$ を整列集合と呼ぶ．
実はこの定義において $(A,\le)$ は全順序集合である必要はなく，半順序集合であるだけで十分である．なぜなら後半の条件から二元集合 $\{ a,b \}$ にも最小元が存在するから，任意の $A$ の二元は比較可能だからだ．
$A$ を整列集合とし，各 $a \in A$ に対し命題 $P(a)$ が定義されているとする．もし
- $P(\min A)$ が真であること
- $b < a$ を満たす任意の $b \in A$ に対し $P(b)$ が真であるとき，$P(a)$ もまた真であること
の二つが成り立てば，すべての $a \in A$ に対し $P(a)$ は真である．
（仮定2.において $a = \min A$ とすれば仮定1.と等価な主張となるから，仮定2.のみを書く場合もしばしばある）
$A_1 = \{ a \in A \mid P(a) \textrm{ が偽} \}$ と定義し，これが空であることを背理法で示す．
$A_1$ が空でないとすると，$A$ が整列集合であることから $A_1$ の最小元 $\min A_1$ が存在するはずだ．最小性より $b < \min A_1$ を満たす任意の $b \in A$ に対して $P(b)$ は真である．これを仮定2.と照らし合わせると $P(\min A_1)$ もまた真となり矛盾する．したがって $A_1$ は空であり，任意の $a \in A$ に対し $P(a)$ は成立する．
一般に，順序数に対しても超限帰納法は利用することができる．
任意の順序数 $\alpha$ に対し，命題 $P(a)$ が定義されているものとする．このとき，任意の順序数 $\alpha$ が条件
「すべての $\beta < \alpha$ なる順序数 $\beta$ について $P(\beta)$ が真なら $P(\alpha)$ もまた真である」
を満たすのなら，すべての順序数 $\alpha$ に対して $P(\alpha)$ が成り立つ．
気持ちとしては定理1の整列集合 $A$ に「すべての順序数の集合」を当てはめたいのだが，これは叶わない．なぜならすべての順序数の集まりは集合とはならず真のクラスとなるからだ（ブラリ-フォルティの定理）．その点だけ注意が必要となる．
この記事を高評価した人
この記事に送られたバッジ
投稿者
