§ 1. Set Theory
33
(3) 0 E X for every nonempty ordinal X. By the axiom of regularity,
there exists an a E X such that a n X = 0. But a C X by (0 1). Thus
o = a n X = a, qed.
(4) For a, b EX, the relation a E b implies a C b. If indeed x E a, one
has either b E x, or b = x, or x E b by (0 2). In the first case, one would
have x E a E b E x, impossible (axiom of regularity). In the second case, one
would have a E band b E a, impossible. In consequence, x E a implies x E b,
whence a C b, qed.
(5) Let A be a nonempty subset of X; let us show that there exists an
a E A such that a C x for all x E A. In other words: as a set of subsets of
X, every nonempty subset A of X possesses a least element. By the axiom of
regularity, there exists an a E A such that a n A = 0. For x E A, the relation
x E a would imply x E A n a = 0, absurd; since x E a is impossible, one thus
has either x = a or a E x, whence a C x in both cases, by (4), qed.
(6) Every element Y of an ordinal X is itself an ordinal. By (4), x E Y
implies x C Y, whence (0 1). If on the other hand x, y E Y, one has also
x, y E X since Y C X by (0 1); since X satisfies (02), a fortiori so does Y,
qed.
(7) Let X and Y be two ordinals such that Y C X and X -=I Y; then
Y E X and conversely. The converse is clear since it implies Y C X by (4)
and Y -=I X since otherwise one would have X EX.
So suppose that Y C X and X - Y is nonempty; X - Y possesses a least
element b by (5); we shall see that b = Y, which will prove that Y E X (and
even that Y E X - Y, in accordance with the axiom of regularity).
First we shall show that beY. For all x E b, one has either x E X - Y or
x E Y. Since b is the smallest element of X - Y, the first eventuality would
imply b c x; but since b is an ordinal, by (6), and since x E b by hypothesis,
one also has xC b; the relation x E X - Y would thus imply x = b, impossible
since x E b. So we see that x E b implies x E Y, whence beY.
Conversely, for all y E Y, one has either bEy, or b = y, or y E b. Y
being an ordinal by (6), one has y C Y. If bEy, one has bEY, absurd since
bE X - Y. If b = y, one again has bEY since y E Y implies y C Y. The
only possible case is thus the third, which shows that Y C b, qed.
(8) Let X and Y two ordinals; then either X C Y or Y eX. Let Z =
X n Y, which is an ordinal by (1). If the theorem were false, one would have
Z C X and Z -=I X, so Z E X by (7), and similarly Z E Y, whence Z E XnY,
Le. Z E Z, qed.
(9) Let X and Y two ordinals; one has either Y E X, or Y = X, or
X E Y. If in fact Y C X one has either Y = X, or Y -=I X and so Y E X by
(7); one finishes the proof with the help of (8).
(10) Let a be an element of an ordinal X; then either s(a) E X or s(a) =
X. Since s(a) = Y is an ordinal by (2), it is enough, by (9), to exclude the
possibility that X E s(a) = a U {a}. But if such were the case, one would
33
(3) 0 E X for every nonempty ordinal X. By the axiom of regularity,
there exists an a E X such that a n X = 0. But a C X by (0 1). Thus
o = a n X = a, qed.
(4) For a, b EX, the relation a E b implies a C b. If indeed x E a, one
has either b E x, or b = x, or x E b by (0 2). In the first case, one would
have x E a E b E x, impossible (axiom of regularity). In the second case, one
would have a E band b E a, impossible. In consequence, x E a implies x E b,
whence a C b, qed.
(5) Let A be a nonempty subset of X; let us show that there exists an
a E A such that a C x for all x E A. In other words: as a set of subsets of
X, every nonempty subset A of X possesses a least element. By the axiom of
regularity, there exists an a E A such that a n A = 0. For x E A, the relation
x E a would imply x E A n a = 0, absurd; since x E a is impossible, one thus
has either x = a or a E x, whence a C x in both cases, by (4), qed.
(6) Every element Y of an ordinal X is itself an ordinal. By (4), x E Y
implies x C Y, whence (0 1). If on the other hand x, y E Y, one has also
x, y E X since Y C X by (0 1); since X satisfies (02), a fortiori so does Y,
qed.
(7) Let X and Y be two ordinals such that Y C X and X -=I Y; then
Y E X and conversely. The converse is clear since it implies Y C X by (4)
and Y -=I X since otherwise one would have X EX.
So suppose that Y C X and X - Y is nonempty; X - Y possesses a least
element b by (5); we shall see that b = Y, which will prove that Y E X (and
even that Y E X - Y, in accordance with the axiom of regularity).
First we shall show that beY. For all x E b, one has either x E X - Y or
x E Y. Since b is the smallest element of X - Y, the first eventuality would
imply b c x; but since b is an ordinal, by (6), and since x E b by hypothesis,
one also has xC b; the relation x E X - Y would thus imply x = b, impossible
since x E b. So we see that x E b implies x E Y, whence beY.
Conversely, for all y E Y, one has either bEy, or b = y, or y E b. Y
being an ordinal by (6), one has y C Y. If bEy, one has bEY, absurd since
bE X - Y. If b = y, one again has bEY since y E Y implies y C Y. The
only possible case is thus the third, which shows that Y C b, qed.
(8) Let X and Y two ordinals; then either X C Y or Y eX. Let Z =
X n Y, which is an ordinal by (1). If the theorem were false, one would have
Z C X and Z -=I X, so Z E X by (7), and similarly Z E Y, whence Z E XnY,
Le. Z E Z, qed.
(9) Let X and Y two ordinals; one has either Y E X, or Y = X, or
X E Y. If in fact Y C X one has either Y = X, or Y -=I X and so Y E X by
(7); one finishes the proof with the help of (8).
(10) Let a be an element of an ordinal X; then either s(a) E X or s(a) =
X. Since s(a) = Y is an ordinal by (2), it is enough, by (9), to exclude the
possibility that X E s(a) = a U {a}. But if such were the case, one would