超限帰納法

同義語：transfinite induction

概要

前提知識: 順序数, 整列順序, 数学的帰納法

超限帰納法とは

超限帰納法（transfinite induction）は、順序数で番号を付けた主張を、各段階より前のすべての段階を仮定して証明する方法である。自然数についての数学的帰納法では $0,1,2,\ldots$ の段階を進むが、順序数には $0,1,2,\ldots$ の後の $\omega$ や、さらに $\omega+1$、$\omega\cdot2$ などの段階がある。$\omega$ には直前の順序数がないので、単に「一つ前から次へ」を繰り返す記述だけではその段階を扱えない。超限帰納法では、対象の順序が整列していることを使い、反例があれば最小の反例がある、という事実から結論を得る（Jec03 Chapter 2）。
この方法が保証するのは、既に定めた主張 $P(\alpha)$ がすべての段階で成り立つことである。各段階で新しい集合や関数を作る超限再帰とは役割が異なる。例えば順序数の和の定義では超限再帰で $\alpha+\beta$ を作り、その演算の性質を超限帰納法で証明する。この違いを押さえると、集合論の累積階層、基数論、強制法で使う名前の階数などを読む際に、何を定義し何を証明しているかが明確になる。

順序数上の原理

順序数 $\theta$ を固定し、各 $\beta<\theta$ について主張 $P(\beta)$ を考える。$\beta$ の段階では、それより小さいすべての $\gamma$ に対する $P(\gamma)$ を仮定してよい。この仮定は $\beta=0$ なら空である。帰納法の結論は $\theta$ 未満の全段階についてであり、$P(\theta)$ 自体は含まない。

順序数上の超限帰納法

順序数 $\theta$ と述語 $P$ に対し、各 $\beta<\theta$ で
$$ \bigl(\forall\gamma<\beta\;P(\gamma)\bigr)\Longrightarrow P(\beta) $$
が成り立つなら、すべての $\beta<\theta$ で $P(\beta)$ が成り立つ。この推論を $\theta$ 上の超限帰納法という。

これは条件として $P(\beta)$ を直接仮定しているのではない。$\beta$ より小さい段階だけを仮定し、そこから $P(\beta)$ を新たに導く。$\beta=0$ では前提が空なので、$P(0)$ を証明する必要がある。$\theta=0$ では対象段階がないため結論は空虚に真となる。これらの端の事例を曖昧にすると、基底のない循環論法が紛れやすい。

最小反例による原理の証明

$\theta$ を順序数とし、すべての $\beta<\theta$ について「$P(\gamma)$ が全ての $\gamma<\beta$ で成り立てば $P(\beta)$ が成り立つ」と仮定する。このとき $P(\beta)$ はすべての $\beta<\theta$ で成り立つ。

反例の集合の最小元を取る

結論が偽なら $C=\{\beta<\theta\mid \neg P(\beta)\}$ は空でない。$C$ は順序数 $\theta$ の部分集合であり、順序数の通常の順序は整列順序だから、$C$ には最小元 $\beta$ がある。最小性により $\gamma<\beta$ なら $\gamma\notin C$、すなわち $P(\gamma)$ が成り立つ。仮定をこの $\beta$ に適用すると $P(\beta)$ が得られ、$\beta\in C$ に矛盾する。従って反例はない。$\square$

この証明で必要なのは、反例が集合として $\theta$ の内部にあり、非空の部分集合が最小元を持つことである。順序数が整列していることが核心であり、反例を自然数のように一個ずつ数え上げたわけではない。$\theta$ 未満の主張については、選択公理を新たに仮定しなくてもこの論証が使える。任意の集合をまず整列可能にするという別問題とは区別する。
例えば $\theta=\omega+2$ の場合、対象は有限順序数、$\omega$、$\omega+1$ である。反例が $\omega+1$ にあると仮定したとき、より小さい段階には有限順序数だけでなく $\omega$ も含まれる。したがって $\omega+1$ の帰納仮定は「すべての自然数について真」にとどまらず、$P(\omega)$ が既に確立されたことも含む。どの段階まで仮定できるかは、添字の大小関係そのものから読み取る。
全順序数についての主張にも同じ発想を使う。反例があると仮定し、その一つを $\alpha$ とする。$\alpha+1$ の範囲内の反例を集めれば非空の集合になり、最小の反例を取れる。従って「反例の真のクラス全体から最小元を選ぶ」といったクラスに関する曖昧な操作をせずに済む。ただし全順序数について述べる $P$ は、集合論の言語で表せる性質など、各段階で意味が定まるものとする。

全順序数への拡張

各順序数 $\beta$ で、それより小さい全順序数 $\gamma$ に $P(\gamma)$ が成り立つなら $P(\beta)$ も成り立つとする。このとき全順序数 $\beta$ に $P(\beta)$ が成り立つ。

反例一つから集合内の最小反例を取る

反例 $\alpha$ があると仮定する。順序数 $\alpha+1$ の範囲の反例集合 $C=\{\beta\leq\alpha\mid\neg P(\beta)\}$ は $\alpha\in C$ により非空である。$C$ の最小元 $\beta$ より小さい $\gamma$ はすべて $P(\gamma)$ を満たすから、段階 $\beta$ の仮定で $P(\beta)$ が得られる。これは矛盾である。どの反例も存在しない。$\square$

零・後続・極限の三段階

実際の証明では順序数を $0$、後続順序数 $\gamma+1$、$0$ でない極限順序数 $\lambda$ に分けることが多い。後続段階には直前 $\gamma$ があるが、極限段階にはない。そのため次の三条件を別々に確かめる形式が便利である（Jec03 Chapter 2）。

三段階形式

すべての順序数について $P$ を示したいとする。次の三条件が成り立てば、$P(\alpha)$ は全順序数 $\alpha$ で成り立つ。

$P(0)$ が成り立つ。
各 $\gamma$ について、$P(\gamma)$ なら $P(\gamma+1)$ が成り立つ。
各 $0$ でない極限順序数 $\lambda$ について、すべての $\gamma<\lambda$ で $P(\gamma)$ が成り立つなら $P(\lambda)$ が成り立つ。

最小反例の種類を分ける

反例があれば最小反例 $\beta$ を取る。$\beta=0$ は条件1に反する。$\beta=\gamma+1$ なら最小性から $P(\gamma)$ が成り立つので条件2に反する。残る $\beta$ は $0$ でない極限順序数であり、最小性からすべての $\gamma<\beta$ に $P(\gamma)$ が成り立つため条件3に反する。順序数はこの三種類のいずれかなので反例はない。$\square$

三段階形式は強い帰納仮定を各段階で必要な分だけ使う形である。後続段階では直前の主張だけで十分なことが多い一方、極限段階ではそれまでの全情報を使う。逆に、すべての前段階を仮定して $P(\beta)$ を導く元の形も三段階形式を含む。$P(\beta)$ の証明で $\beta$ の種類を調べ、該当する条件を使えばよいからである。ただし三段階形式の後続条件だけを書き、極限条件を省くことはできない。

$\omega$ で必要になる極限段階

$P(\alpha)$ を「$\alpha<\omega$」とする。$P(0)$ は真で、任意の順序数 $\alpha$ について $P(\alpha)\Rightarrow P(\alpha+1)$ が成り立つ。$\alpha$ が有限なら $\alpha+1$ も有限であり、$\alpha\geq\omega$ なら前件が偽だからである。しかし $P(\omega)$ は偽である。自然数の段階をいくら進んでも、$\omega$ を含む範囲の結論は得られない。$\omega$ での極限条件を別に検証しなければならない。

この例では後続条件は全段階で成り立つが、極限条件が $\omega$ で失敗する。従って後続条件が完全に確認されていても、それだけでは全順序数への結論を導けない。示したい範囲を固定し、その範囲の後続段階と極限段階を過不足なく調べることが重要である。自然数の強い帰納法と超限帰納法は、最小反例を使う論理の形が共通するが、対象となる整列順序に極限段階がある点で用途が広がる。
極限条件は「無限個の事実を一度に仮定する」ための条件であり、有限回の後続操作を極限まで実際に実行する手続きではない。例えば $\lambda=\omega$ で $P(n)$ を全て確認しても、$P(\omega)$ に関する推論が空白なら三段階形式の仮定は満たされない。極限で対象を合併として定義している場合には、各要素がある前段階から来ることを示すのが典型的な橋渡しになる。後の累積階層の証明では、$x\in V_\lambda$ から $x\in V_\beta$ となる $\beta<\lambda$ を取り、この橋渡しを具体的に行う。

整列集合への一般化

順序数だけでなく、整列集合 $(W,<)$ 上でも同じ証明が使える。ここで整列とは、$W$ の空でない任意の部分集合に最小元があることをいう。各 $x\in W$ より前のすべての $y< x$ に $P(y)$ が成り立つなら $P(x)$ が成り立つ、という仮定を置く。順序数の場合の $\gamma<\beta$ を $y< x$ に読み替えるだけである。

整列集合上の帰納法

整列集合 $(W,<)$ の各 $x$ について、$P(y)$ がすべての $y< x$ で成り立てば $P(x)$ が成り立つとする。このときすべての $x\in W$ に $P(x)$ が成り立つ。

最小反例は仮定と両立しない

反例集合 $C=\{x\in W\mid\neg P(x)\}$ が非空なら、整列性から最小元 $x$ がある。$y< x$ なら $y\notin C$ なので $P(y)$ が成り立つ。段階 $x$ の仮定から $P(x)$ が従い、矛盾する。従って $C$ は空である。$\square$

整列集合はある順序数と順序同型であるため、この一般化は順序数上の原理の別表現ともいえる。ただし任意の全順序集合にそのまま適用できるわけではない。例えば整数の通常の順序には最小元がない非空部分集合 $\mathbb Z$ 自身がある。「$P(y)$ がすべての $y< x$ で成り立つなら $P(x)$」という条件だけでは、最初に情報を供給する段階が存在せず、$P(x)$ をすべて偽にしても各含意が真になってしまう。整列性を外すと結論が破れる具体的な理由である。

超限再帰との違い

超限再帰（transfinite recursion）は、既に与えられた関数の前半 $f\upharpoonright\beta$ から次の値 $f(\beta)$ を決める規則を使い、列や関数を構成する定理である。帰納法が既存の主張の真偽を伝えるのに対し、再帰は各段階の値を生み出す。両者はしばしば連続して使われる。超限再帰で対象を定義し、超限帰納法で定義が一意であることや対象の性質を示す（Jec03 Chapter 2）。
例えば固定した順序数 $\alpha$ に対し、和 $\alpha+\beta$ は $\beta$ について、初期値、後続で一つ進める規則、極限でそれまでの上限を取る規則によって定まる。
$$ \alpha+0=\alpha,\qquad \alpha+(\beta+1)=(\alpha+\beta)+1,\qquad \alpha+\lambda=\sup_{\beta<\lambda}(\alpha+\beta) $$
最後の式は $\lambda$ が $0$ でない極限順序数のときのものである。この三式は $\alpha+\beta$ を定義する式であって、それだけで任意の性質を証明するわけではない。証明したい性質に対して帰納仮定を別途立てる。

順序数加法の右変数に関する単調性

順序数 $\alpha$ を固定し、$\beta<\gamma$ なら $\alpha+\beta<\alpha+\gamma$ である。

後続で増え極限では上限を取る

$\gamma$ に関する超限帰納法で示す。$\gamma=0$ では $\beta<\gamma$ がなく空虚である。$\gamma=\delta+1$ なら、$\beta<\gamma$ は $\beta\leq\delta$ を意味する。$\beta=\delta$ では $\alpha+\beta< (\alpha+\delta)+1=\alpha+\gamma$ である。$\beta<\delta$ なら帰納仮定で $\alpha+\beta<\alpha+\delta<\alpha+\gamma$ となる。$\gamma$ が非零極限なら $\beta<\gamma$ に対して $\beta+1<\gamma$ である。従って $\alpha+\beta<(\alpha+\beta)+1=\alpha+(\beta+1)\leq\sup_{\xi<\gamma}(\alpha+\xi)=\alpha+\gamma$。三場合で示せた。$\square$

特に $1+\omega=\sup_{n<\omega}(1+n)=\omega$ だが、$\omega+1$ は $\omega$ より大きい。この非可換性は、極限段階の上限を経由する演算と、後続を一つ加える演算とが同じでないことを示す。$1+n=n+1$ は有限の $n$ について通常の帰納法で証明でき、そこから有限後続順序数の上限が $\omega$ であることを使った。

累積階層における帰納法

集合論の累積階層では $V_0=\emptyset$、$V_{\alpha+1}=\mathcal P(V_\alpha)$ とし、極限 $\lambda$ では $V_\lambda=\bigcup_{\beta<\lambda}V_\beta$ とする。これは再帰による構成である。構成後に各 $V_\alpha$ が推移的集合であることを示すのが帰納法の役割になる。集合 $T$ が推移的とは、$x\in T$ なら $x\subseteq T$ であることをいう。

累積階層の各段階は推移的

すべての順序数 $\alpha$ について $V_\alpha$ は推移的である。

零・後続・極限を分ける

$V_0=\emptyset$ は推移的である。$V_\alpha$ が推移的なら、$x\in V_{\alpha+1}=\mathcal P(V_\alpha)$ は $x\subseteq V_\alpha$ を意味する。さらに $V_\alpha\subseteq\mathcal P(V_\alpha)$ が成り立つ。実際、$y\in V_\alpha$ なら推移性から $y\subseteq V_\alpha$ なので $y\in\mathcal P(V_\alpha)$ である。従って $x\subseteq V_\alpha\subseteq V_{\alpha+1}$ となり、$V_{\alpha+1}$ は推移的である。非零極限 $\lambda$ で $x\in V_\lambda$ なら、ある $\beta<\lambda$ で $x\in V_\beta$ である。帰納仮定から $x\subseteq V_\beta\subseteq V_\lambda$。よって $V_\lambda$ も推移的である。三段階形式により結論を得る。$\square$

この証明では後続段階において $V_\alpha$ 自体の推移性を用い、極限段階では各前段階の推移性を用いる。もし極限の定義が単なる一つ前からの更新だけなら、この論証は書けない。累積階層は、再帰で構成した対象に対して帰納法を適用する標準的な型を示す。

集合論での用途と注意点

順序数を添字とする構成では、上の二つの例以外にも、集合の階数に関する性質や、順序数演算の恒等式を帰納法で検証する。ある対象に「階数」を割り当て、定義や証明をより低い階数の対象に還元できれば、最小反例の議論が働く。強制法では強制概念の条件とともに名前の階数を用い、名前の解釈や強制関係の基本性質を段階的に扱う。ただし「階数が小さいものに戻る」と示さないまま帰納法と称してはいけない。何が整列されたパラメータで、どの前段階に還元したかを明示する必要がある。
到達不能基数や可測基数のような巨大基数を扱う議論でも、順序数や基数上の再帰・帰納法は基本的な道具になる。一方、超限帰納法の原理そのものが巨大基数の存在を与えるわけではない。大きな基数の存在は別の仮定を要し、帰納法は与えられた順序数の範囲で主張を伝播させる。大きな添字を扱うからといって、強い存在公理を密かに使っていると解釈してはならない。
よくある混同を三つ区別しておく。第一に、$P(n)$ が全自然数で真でも $P(\omega)$ は別に示す必要がある。第二に、極限段階で $P(\lambda)$ を示す際には $P(\gamma)$ の全 $\gamma<\lambda$ が使えるが、それだけで $P(\lambda)$ が自動的に真になるわけではない。第三に、超限再帰の規則が各段階で値を与えることと、そこから得た値が期待する性質を満たすことは別の証明課題である。この区別は順序数の和や累積階層の例で具体的に確かめられる。