超限帰納法
注意
定理であることに注意
整列集合$ \lang A,\leq \rangとする．$ P(x)は$ A上の述語とする． 次が成り立てば，任意の$ a \in Aについて$ P(a)．
任意の$ a \in Aとして，$ a' < aである全ての$ a'で$ P(a') \implies P(a)．
証明
1. $ A(a) \coloneqq \{x \in A \mid x < a\} \sube Aとする．$ A(a) \sube A．
2. $ A_P \coloneqq \{ x \in A \mid P(x)\}とする．$ A_P \sube A．
任意の$ a \in Aで$ A(a) \sube A_P \implies a \in A_P
任意の$ a \in Aで$ A(a) \cap \overline{A_P} = \emptyset \implies a \in A_P
$ \overline{A_P}は$ A_Pの補集合．
5. $ A = A_P，すなわち$ \overline{A_P} = \emptysetを示す．
6. $ \overline{A_P} \ne \emptysetを背理法の仮定とする．
7. $ Aは整列集合であるので，$ \overline{A_P}も整列集合であり，最小元$ \min \overline{A_P}が存在する．
8. $ A\left( \min \overline{A_P} \right) \cap \overline{A_P} = \emptysetである．（$ <の定義．）
9. 4より，$ \min \overline{A_P} \in A_P．しかしこれは明らかに矛盾している．
10. したがって$ \overline{A_P} = \emptyset，すなわち$ A = A_P．❏