Let S be a segment of E such that $\mathrm{S} \neq \mathrm{E}$. Since $\mathrm{E} - \mathrm{S}$ is not empty, it has a least element $a$. By virtue of Definition 2, the relation $x \geqslant a$ implies $x \notin \mathrm{S}$; otherwise we would have $a \in \mathrm{S}$, which is absurd. Hence $\mathrm{E} - \mathrm{S}$ is the interval $[a, \rightarrow[$, and S is the interval $]\leftarrow, a[$.

¶ For every element $x$ in a totally ordered set E the segment $]\leftarrow, x[$ is called the segment with endpoint x, and is denoted by $\mathrm{S}_x$.

Note that if E is well-ordered and not empty, $\mathrm{S}_x$ has a least element $\alpha$ and consequently is also the interval $[\alpha, x[$.

Let E be a totally ordered set. The union A of the $\mathrm{S}_x$, as $x$ runs through E, is E if E has no greatest element; and if E has a greatest element $b$, we have $\mathrm{A} = \mathrm{E} - \{b\}$.

It is clear that if $x \in \mathrm{E}$ and $y \in \mathrm{E}$, the relation $x \leqslant y$ implies $\mathrm{S}_x \subset \mathrm{S}_y$, and that $x < y$ implies $\mathrm{S}_x \neq \mathrm{S}_y$; the mapping $x \rightarrow \mathrm{S}_x$ is therefore an isomorphism of E onto the set S(E) of segments of E distinct from E itself (§ 1, no. 12, Proposition 11), and consequently S(E) is well-ordered. Moreover, E\* is isomorphic to the well-ordered set obtained from S(E) by adjoining a greatest element.

The first assertion is a consequence of the following general lemma :

Let $\mathrm{G}_\alpha$ be the graph of the given ordering on $\mathrm{X}_\alpha$. If G is the graph of an ordering on E which induces on each $\mathrm{X}_\alpha$ the ordering whose graph is $\mathrm{G}_\alpha$, then we must have $\mathrm{G}_\alpha \subset \mathrm{G}$ for each $\alpha \in \mathrm{A}$; hence G contains $\bigcup_{\alpha \in \mathrm{A}} \mathrm{G}_\alpha$. On the other hand, for each pair $(x, y)$ of elements of E there exists by hypothesis an index $\alpha \in \mathrm{A}$ such that $x \in \mathrm{X}_\alpha$ and $y \in \mathrm{X}_\alpha$; if $(x, y) \in \mathrm{G}$, we have $(x, y) \in \mathrm{G}_\alpha$, so that $\mathrm{G} \subset \bigcup_{\alpha \in \mathrm{A}} \mathrm{G}_\alpha$. Hence if the required ordering on E exists, its graph is necessarily $\mathrm{G} = \bigcup_{\alpha \in \mathrm{A}} \mathrm{G}_\alpha$. It remains to be shown that this set satisfies the conditions of the lemma. Since $\mathrm{G}_\beta \cap (\mathrm{X}_\alpha \times \mathrm{X}_\alpha) = \mathrm{G}_\alpha$ if $\mathrm{X}_\alpha \subset \mathrm{X}_\beta$, we have $\mathrm{G} \cap (\mathrm{X}_\alpha \times \mathrm{X}_\alpha) = \mathrm{G}_\alpha$ for all $\alpha \in \mathrm{A}$; on the other hand, it follows from the hypothesis that any three elements $x$, $y$, $z$ of E belong to the same $\mathrm{X}_\alpha$. Hence $(x, y) \in \mathrm{G}$ is an order relation on E, and the lemma is proved.

¶ We now take up the proof of Proposition 3. Let us begin by showing that each $\mathrm{X}_\iota$ is a segment of E. Indeed, if $x \in \mathrm{X}_\iota$, $y \in \mathrm{E}$, and $y \leqslant x$, there exists an index $\varkappa$ such that $\mathrm{X}_\iota \subset \mathrm{X}_\varkappa$ and $y \in \mathrm{X}_\varkappa$; since by hypothesis $\mathrm{X}_\iota$ is a segment of $\mathrm{X}_\varkappa$, we have $y \in \mathrm{X}_\iota$, which proves the assertion. The same reasoning proves that for each $x \in \mathrm{X}_\iota$ the segment with endpoint $x$ in $\mathrm{X}_\iota$ is identical with the interval $]\leftarrow, x[$ in E. Next let us show that E is well-ordered. If H is a non-empty subset of E, there is an index $\iota \in \mathrm{I}$ such that $\mathrm{H} \cap \mathrm{X}_\iota \neq \emptyset$; if $a$ is the least element of $\mathrm{H} \cap \mathrm{X}_\iota$ in $\mathrm{X}_\iota$, then $a$ is also the least element of H in E. That is, if $x \in \mathrm{H}$, there exists an index $\varkappa \in \mathrm{I}$ such that $\mathrm{X}_\iota \subset \mathrm{X}_\varkappa$ and $x \in \mathrm{X}_\varkappa$; we cannot have $x < a$, because the interval $]\leftarrow, a[$ is contained in $\mathrm{X}_\iota$, and therefore we have $x \geqslant a$ since $\mathrm{X}_\varkappa$ is totally ordered.

¶ Finally, we must show that a segment of E, other than E itself, is a segment of one of the $\mathrm{X}_\iota$; this is an immediate consequence of the preceding arguments, since such a segment is of the form $]\leftarrow, x[$ (Proposition 1) and since $x$ belongs to some $\mathrm{X}_\iota$.

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.

(1) for all $x \in \mathrm{M}$ we have $\mathrm{S}_x \in \mathfrak{S}$ and $p(\mathrm{S}_x) = x$;

(2) $\mathrm{M} \notin \mathfrak{S}$.

Let $\mathfrak{M}$ be the set of subsets G of $\mathrm{E} \times \mathrm{E}$ satisfying the following conditions :

(a) G is the graph of a well-ordering on $\mathrm{pr}_1 \mathrm{G} = \mathrm{U}$;

(b) if $x \leqslant y$ denotes the relation $(x, y) \in \mathrm{G}$ on U, then for each $x \in \mathrm{U}$ the segment $\mathrm{S}_x$ is such that $\mathrm{S}_x \in \mathfrak{S}$ and $p(\mathrm{S}_x) = x$.

¶ We shall show that if G and G' are two elements of M and if U, U' denote their first projections, then one of the two sets U, U' is contained in the other and that if, for example, $\mathrm{U} \subset \mathrm{U}'$, then $\mathrm{G} = \mathrm{G}' \cap (\mathrm{U} \times \mathrm{U})$ (in other words, that the order relation on U is induced by the order relation on U') and U is a segment of U'.

¶ Consider the set V of elements $x \in \mathrm{U} \cap \mathrm{U}'$ such that the segments with endpoint $x$ are the same in U and U', and such that the orderings induced on this segment by the orderings on U and U' are identical. It is clear that V is a segment in both U and U' and that the orderings induced on V are the same; our assertion will therefore be proved if we show that either $\mathrm{V} = \mathrm{U}$ or $\mathrm{V} = \mathrm{U}'$. Let us argue by contradiction and suppose that $\mathrm{V} \neq \mathrm{U}$ and $\mathrm{V} \neq \mathrm{U}'$. Let $x$ be the least element of $\mathrm{U} - \mathrm{V}$ in U and let $x'$ be the least element of $\mathrm{U}' - \mathrm{V}$ in U'; we have $\mathrm{V} = \mathrm{S}_x$ in U, and $\mathrm{V} = \mathrm{S}_{x'}$ in U'. But by hypothesis, $\mathrm{V} \in \mathfrak{S}$ and

so that $x = x'$. Hence by definition $x \in \mathrm{V}$, which is absurd.

¶ We may therefore apply Proposition 3 of no. 1 to the set of first projections $\mathrm{U} = \mathrm{pr}_1 \mathrm{G}$ (where $\mathrm{G} \in \mathfrak{M}$) and thus obtain a well-ordered set

It is easily seen that the graph of the ordering on M belongs to $\mathfrak{M}$. If we had $\mathrm{M} \in \mathrm{S}$, then, putting $a = p(\mathrm{M})$, we should have $a \notin \mathrm{M}$. We could therefore adjoin to M the element $a$ as greatest element, and the set $\mathrm{M}' = \mathrm{M} \cup \{a\}$ would be well-ordered. Since $\mathrm{M} = \mathrm{S}_a$ in M', we should have $\mathrm{S}_a \in \mathfrak{S}$ and $p(\mathrm{S}_a) = a$; the graph of the ordering on M' would therefore belong to $\mathfrak{M}$, which is absurd.

Note that if $\emptyset \notin \mathfrak{S}$ (and in particular if $\mathfrak{S}$ is empty), the set M whose existence is asserted by Lemma 3 is the empty set; this follows from condition 1 of Lemma 3.

Let $\mathfrak{S} = \mathfrak{P}(\mathrm{E}) - \{\mathrm{E}\}$ be the set of all subsets of E other than E itself. For each $\mathrm{X} \in \mathfrak{S}$ let $p(\mathrm{X}) = \tau_x \ (x \in \mathrm{E} - \mathrm{X})$; since the relation $\mathrm{X} \in \mathfrak{S}$ implies $(\exists x)(x \in \mathrm{E} - \mathrm{X})$, we have $p(\mathrm{X}) \in \mathrm{E} - \mathrm{X}$ (Chapter I, § 4, no. 1) and therefore $p(\mathrm{X}) \notin \mathrm{X}$. We may therefore apply Lemma 3, and consequently there exists a well-ordering on a subset M of E such that $\mathrm{M} \notin \mathfrak{S}$; but the only subset of E which does not belong to $\mathfrak{S}$ is E itself, and the theorem is proved.

This theorem is a particular case of the following result :

We shall say that an element $v \in \mathrm{E}$ is a strict upper bound of a subset X of E if $v$ is an upper bound of X and $v \notin \mathrm{X}$. Let $\mathfrak{S}$ be the set of subsets of E which have a strict upper bound in E, and for each $\mathrm{S} \in \mathfrak{S}$ put $p(\mathrm{S}) = \tau_v(v$ is a strict upper bound of S$)$; then $p(\mathrm{S})$ is a strict upper bound of S. Applying Lemma 3 of no. 3 to $\mathfrak{S}$ and $p$, we see that there exists a subset M of E and a well-ordering $\Gamma$ on M which satisfies the conditions of Lemma 3; in particular, M has no strict upper bound in E. Furthermore, the ordering $\Gamma$ is identical with that induced on M by the ordering on E. For in M the relation “$y\in\Gamma\langle x\rangle$ and $x\ne y$” is equivalent to $x\in S_y$; and since $p(S_y)=y$ is an upper bound of $S_y$ (with respect to the ordering on E), it implies $x<y$ in E. But this means that the injection of M into E is a strictly increasing mapping (M being endowed with the ordering $\Gamma$); and since M is totally ordered, it follows that the relations $y\in\Gamma\langle x\rangle$ and $x\leq y$ are equivalent in M (§ 1, no. 12, Proposition 11). This being so, there exists by hypothesis an upper bound $m$ of M in E; but since M has no strict upper bound, it follows that $m$ is a maximal element of E.

For it follows from Definition 3 that the set F of elements $x\geq a$ in E is inductive, and a maximal element of F is also maximal in E.

(1) there exists a unique isomorphism of E onto a segment of F;

(2) there exists a unique isomorphism of F onto a segment of E.

Let $\mathfrak{F}$ be the set of mappings of subsets of E into F such that each mapping is defined on a segment of E and is an isomorphism of this segment onto a segment of F. Then the set $\mathfrak{F}$, ordered by the relation “$v$ extends $u$” between $u$ and $v$, is inductive. For if $\mathfrak{G}$ is a totally ordered subset of $\mathfrak{F}$, the union S of the domains of the mappings $u\in\mathfrak{G}$ is a union of segments of E and is therefore itself a segment of E. If $v$ is the least upper bound of $\mathfrak{G}$ in $\Phi(E,F)$ (no. 4, Example 2), then $v(S)$ is the union of the ranges of the mappings $u\in\mathfrak{G}$ and is therefore a segment of F. Finally, for each pair of elements $x$, $y$ of S such that $x<y$ there exists $u\in\mathfrak{G}$ whose domain contains both $x$ and $y$ (because $\mathfrak{G}$ is totally ordered); and since $v(x)=u(x)<u(y)=v(y)$, $v$ is an isomorphism of S onto $v(S)$, and our assertion is proved.

¶ Now let $u_0$ be a maximal element of $\mathfrak{F}$ (no. 4, Theorem 2) and let $S_0$ be the segment of E which is the domain of $u_0$. If we show that either $S_0=E$ or $u_0(S_0)=F$, the theorem will be proved. Let us argue by contradiction and suppose that $S_0\ne E$ and $u_0(S_0)\ne F$. There will then be an element $a\in E$ and an element $b\in F$ such that $S_0=]-\leftarrow,a[$ and $u_0(S_0)]=]-\leftarrow,b[$ (no. 1, Proposition 1). Extend $u_0$ to a mapping $u_1$ of the segment $]-\leftarrow,a]$ into F by putting $u_1(a)=b$; since $u_1$ is an isomorphism of $]-\leftarrow,a]$ onto the segment $]-\leftarrow,b]$, this contradicts the maximality of $u_0$ in $\mathfrak{F}$.

¶ The uniqueness asserted in Theorem 3 is a consequence of the following Lemma :

Suppose, on the contrary, that the set of elements $y\in E$ such that $f(y)>g(y)$ is not empty; then this set will have a least element $a$. If $x<a$, we have then $f(x)\leq g(x)<g(a)<f(a)$ since $g$ is strictly increasing. Since $f(E)$ is a segment of F, there exists $z\in E$ such that $g(a)=f(z)$; $f$ is increasing, so that $f(z)<f(a)$ implies $z<a$. Hence

which is absurd.

Put $F=E$ in Theorem 3.

For $g\circ f$ is an isomorphism of E onto the segment $g(T)\subset S$ of E; by Corollary 1 we have $g(T)=S=E$, and $g\circ f$ is the identity mapping of E. Similarly, $f\circ g$ is the identity mapping of F, whence the result.

By virtue of Theorem 3 it is enough to prove that there exists no isomorphism $g$ of E onto a segment of A of the form $S_a$. If there were, $g$ would then be a strictly increasing mapping of E into E such that $g(a)\in S_a$, in other words such that $g(a)<a$; but this inequality contradicts Lemma 4 (with $f$ as the identity mapping).