We have seen that ordinals are either zero, a successor, or a limit, and are based on $\in $ which is well-founded and has induction and recursion principles. Therefore there are induction and recursion principles on ordinals, which are essentially just special cases of $\in $-induction and recursion. This web page states these principles: the proofs are the same as for $\in $-induction and recursion. Examples will be given later.

As elsewhere, $\alpha ,\beta ,\gamma ,\delta ,\dots $ etc. and $\lambda ,\mu ,\dots $ range over ordinals with $\lambda ,\mu ,\dots $ being reserved for limit ordinals.

Theorem.

Suppose $\varphi \left(x\right)$ is a first order formula and

- $\varphi \left(0\right)$
- $\forall \alpha \u200a\left(\varphi \right(\alpha )\to \varphi (\alpha +1\left)\right)$
- $\forall \lambda \u200a\left(\right(\forall \alpha \in \lambda \u200a\varphi \left(\alpha \right))\to \varphi \left(\lambda \right))$

Then for all ordinals $\alpha $ we have $\varphi \left(\alpha \right)$.

Remark: in the above, and everywhere in these notes, $\lambda $ is thought of as a limit ordinal. However the third case includes the first for $\lambda =0$ and the second for $\lambda =\alpha +1$ so strictly speaking the first two cases are redundant.

Theorem.

Suppose $G(x,y),H(x,y)$ are class functions defined on ordinals alpha and $G$ is defined by

- $F\left(0\right)={F}_{0}$
- $\forall \alpha \u200aF(\alpha +1)=G(\alpha ,F(\alpha \left)\right)$
- $\forall \lambda \u200aF\left(\lambda \right)=H(\lambda ,\{F\left(\alpha \right):\alpha \in \lambda \})$

Then there is a class function $F$ defined as above, uniform in any parameters in $G,H$.

There are similar induction and recursion theorems on any well-founded relation. A well-order is a particular kind of well-founded relation closely related to ordinals.

Note: some of the following will be moved to somewhere more appropriate in the future.

Definition.

A binary relation, $R$, is *well-founded*
if $\forall z\u200a(z\ne \varnothing \to \exists y\in z\u200a\forall x\u200a(x\in z\to \neg R(x,y\left)\right))$.
A set $r\subseteq x\times x$ is well-founded if the relation
$(u,v)\in r$ is well-founded. The relation
$R$ is *local* if $\forall y\u200a\exists z\u200a\forall x\u200a(x\in z\leftrightarrow R(x,y\left)\right)$.

A set $x$ is called a *well-founded set* if the set membership relation is
well-founded on the transitive closure of $x$.

Definition.

A well-order $<$ on a set $X$ is a linear order such that for all nonempty $Y\subseteq X$ there is a $<$-least element of $Y$.

Theorem.

If $(X,<)$ is a well-ordered set there is a unique ordinal $\alpha $ such that $(X,<)$ is order-isomorphic to $(\alpha ,\in )$.

**Proof.**

Consider the class of set-functions
$F=\{f:Y\to \beta :Y{\subseteq}_{e}X\wedge f:(Y,<)(\beta ,\in )\}$.
where ${\subseteq}_{e}$ denoted Initial part of

and $\beta $ ranges over ordinals.
$F$ is a class i.e. defined by a first order formula. (We shall show eventually it is a set.)
It is nonempty because it contains the empty cunction $\varnothing \to 0$.

Given $f:Y\to \beta $ in $F$, if the domain $Y$ of $f$ is not the whole of $X$ we can take $y\in X\setminus Y$ to be $\in $-least and define $f\prime \left(y\right)=\beta $ and $f\prime \left(x\right)=f\left(x\right)$ for $x\in Y$ hence extend $f$. Furthermore we can prove that for any $f,g\in F$ either $domf\subseteq domg$ or $domg\subseteq domf$ (since both are initial parts of $X$) and that $f,g$ agree on their common doman. (Else take $x\in X$ to be least such that $f,g$ disagree at $x$.) It follows that the union of a set of fucntions in $F$ is a function in $F$.

Now for each $x\in X$ let ${F}_{x}$ be the unique element of $F$ with domain $\{y\in X:y<x\}$ proving (by considering the least such $x$ such that ${F}_{x}$ doesn't exis) that such ${F}_{x}$ always exists. Then $\{{F}_{x}:x\in X\}$ is a set by replacement and $f=\bigcup \{{F}_{x}:x\in X\}$ is a set function mapping $X$ to some ordinal, as may be checked.