Lemma 3

Let E be a set, let $\mathfrak{S}$ be a subset of $\mathfrak{P}(\mathrm{E})$, and let $p$ be a mapping of $\mathfrak{S}$ into E such that $p(\mathrm{X}) \notin \mathrm{X}$ for all $\mathrm{X} \in \mathfrak{S}$. Then there exists a subset M of E and a well-ordering $\Gamma$ on M such that, if $x \leqslant y$ denotes the relation $y \in \Gamma\langle x \rangle$ and $\mathrm{S}_x$ denotes the segment $]\leftarrow, x]$,

(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.