Lemma 2

Let $E$ be a well-ordered set and let $\mathfrak{S}$ be a set of segments of $E$ with the following properties : (1) every union of segments belonging to $\mathfrak{S}$ belongs to $\mathfrak{S}$; (2) if $S_x\in\mathfrak{S}$, then $S_x\cup\{x\}\in\mathfrak{S}$. Then every segment of $E$ belongs to $\mathfrak{S}$.

Suppose that there are segments of $E$ which do not belong to $\mathfrak{S}$, and let $S$ be the smallest of them (no. 1, Proposition 2). If $S$ has no greatest element, then $S$ is the union of the segments of $S$ distinct from $S$ itself, and these segments belong to $\mathfrak{S}$ by virtue of the definition of $S$; hence $S\in\mathfrak{S}$, which is absurd. If, on the other hand, $S$ has a greatest element $a$, then $S=S_a\cup\{a\}$, and since $S_a$ is a segment of $S$ distinct from $S$, we have $S_a\in\mathfrak{S}$; but then also $S\in\mathfrak{S}$, which again is absurd.

¶ For greater convenience we shall place ourselves in a theory $\mathscr{T}$ in which $E$ is a set well-ordered by a relation written $x\leq y$. We have then the following criteria :

C59. (Principle of transfinite induction). *Let $R\{x\}$ be a relation in $\mathscr{T}$ ($x$ not being a constant of $\mathscr{T}$) such that the relation

is a theorem in $\mathscr{T}$. Under these conditions the relation $(x\in E)\Rightarrow R\{x\}$ is a theorem in $\mathscr{T}$.*

Let $\mathfrak{S}$ be the set of segments $S$ of $E$ such that $(y\in S)\Rightarrow R\{y\}$. It is clear that every union of segments belonging to $\mathfrak{S}$ also belongs to $\mathfrak{S}$. On the other hand, if $S_x\in\mathfrak{S}$, we have $R\{x\}$ by hypothesis; hence $(y\in S_x\cup\{y\})\Rightarrow R\{y\}$ by the method of disjunction of cases. Hence (Lemma 2) $E\in\mathfrak{S}$, which proves the criterion.

¶ In the applications of C59, the relation

is usually called the “inductive hypothesis”.

¶ In what follows, for every mapping $g$ of a segment $S$ of $E$ into a set $F$, and for each $x\in S$ we shall denote by $g^{(x)}$ the mapping of the segment $S_x=]\leftarrow,x[$ of $E$ onto $g(S_x)$ which coincides with $g$ on $S_x$. With this notation we have

C60. (Definition of a mapping by transfinite induction.) Let $u$ be a letter, $\mathrm{T}\{u\}$ a term in the theory $\mathscr{T}$. There exists a set $U$ and a mapping $f$ of $E$ onto $U$ such that for all $x\in E$ we have $f(x)=\mathrm{T}\{f^{(x)}\}$. Furthermore, the set $U$ and the mapping $f$ are uniquely determined by these conditions.

Let us first prove the uniqueness. Suppose that $f'$ and $\mathrm{U}'$ also satisfy the conditions of the criterion. Let $\mathfrak{S}$ be the set of segments S of E such that $f$ and $f'$ coincide on S. It is clear that every union of segments belonging to $\mathfrak{S}$ also belongs to $\mathfrak{S}$. On the other hand, if $\mathrm{S}_x \in \mathfrak{S}$, then $f$ and $f'$ agree on $\mathrm{S}_x$ and therefore $f^{(x)} = {f'}^{(x)}$; consequently

which shows that $\mathrm{S}_x \cup \{x\} \in \mathfrak{S}$. It follows that $\mathrm{E} \in \mathfrak{S}$ (Lemma 2), hence $f' = f$ and $\mathrm{U}' = f'(\mathrm{E}) = f(\mathrm{E}) = \mathrm{U}$.

¶ Now let $\mathfrak{S}_1$ denote the set of segments S of E for which there exists a set $\mathrm{U_S}$ and a mapping $f_\mathrm{S}$ of S onto $\mathrm{U_S}$ such that for all $x \in \mathrm{S}$ we have $f_\mathrm{S}(x) = \mathrm{T}\{f^{(x)}\}$. For each $\mathrm{S} \in \mathrm{S}_1$, $f_\mathrm{S}$ and $\mathrm{U_S}$ are uniquely determined, by the first part of the proof; in particular, if $\mathrm{S}'$ and $\mathrm{S}''$ are two segments belonging to $\mathfrak{S}_1$ such that $\mathrm{S}' \subset \mathrm{S}''$, then $f_{\mathrm{S}'}$ is the mapping of $\mathrm{S}'$ onto $f_{\mathrm{S}''}(\mathrm{S}')$ which agrees with $f_{\mathrm{S}''}$ on $\mathrm{S}'$. From this remark it follows that every union of segments belonging to $\mathfrak{S}_1$ also belongs to $\mathfrak{S}_1$ (Chapter II, § 4, no. 6, Proposition 7). On the other hand, if $\mathrm{S}_x \in \mathfrak{S}_1$, we define on $\mathrm{S} = \mathrm{S}_x \cup \{x\}$ a function $f_\mathrm{S}$ extending $f_{\mathrm{S}_x}$ by putting

(Chapter II, § 4, no. 7, Proposition 8); since $f_\mathrm{S}^{(x)} = f_{\mathrm{S}_x}$, it is obvious that $\mathrm{S}_x \cup \{x\} \in \mathfrak{S}_1$. Hence (Lemma 2) $\mathrm{E} \in \mathfrak{S}_1$, and the proof is complete.

¶ Usually this criterion is applied in situations where there exists a set F such that for every mapping h of a segment of E onto a subset of F we have $\mathrm{T}\{h\} \in \mathrm{F}$. Then the set U obtained by applying C60 is a subset of F. For, with the notation used above, let $\mathfrak{S}_2$ be the subset of $\mathfrak{S}_1$ consisting of segments S of E such that $\mathrm{U_S} \subset \mathrm{F}$. It is evident that every union of segments belonging to $\mathfrak{S}_2$ also belongs to $\mathfrak{S}_2$; on the other hand, the hypothesis on F implies that if $\mathrm{S}_x \in \mathfrak{S}_2$, we have $\mathrm{S}_x \cup \{x\} \in \mathfrak{S}_2$. The assertion now follows from Lemma 2.