34
I - Sets and Functions
have either X E a and thus a E X E a, impossible, or X = a and then a E a,
impossible, qed.
The two possibilities s(a) E X and s(a) = X can very well arise. The
second is trivially satisfied if one puts X = s(a) for an ordinal a, for example
a von Neumann integer, or for a = N. For X = N, the first happens for any
aEX.
One can finally prove, but it is much more difficult, that
(11) Every set is equipotent to an ordinal. It can be shown that this statement is equivalent to the axiom of choice.
These properties explain the word "ordinal". For consider an ordinal X
and, for x, y E X, let us write x < y if x E y. Then we have the following
statements, which everyone knows in the case of N:
(i) x < y and y < z imply x < Z;
(ii) for any x, y, one and only one of the following relations is true:
x < y, x = y, y < x;
(iii) in every nonempty subset A of X, there exists an a such that a < x for
all x E A other than a.
(i) follows from (7) since x < y, i.e. x E y, is equivalent to x C y and
x f. y; (ii) and (iii) are the properties (9) and (4).
That said, let us consider an arbitrary set E and, thanks to (11), let us
choose an ordinal X and a bijection f of E onto X. Given two elements x
and y of E, let us agree to write that
x < y <===} f(x) < f(y)·
One thus obtains an order relation 3l on E, possessing the properties (i),
(ii) and (iii): we describe this by saying that E is a well ordered set. There
does indeed exist such an order relation on the set lR of real numbers; but
it clearly cannot be the one that everyone knows - this does not satisfy
(iii): the set of numbers> 0 does not possess a least element, this is the
31 On a set E, an order relation is a relation xRy between the elements of E such
that (a) one has xRx for all x E E, (b) xRy and yRz imply xRz, (c) xRy and yRx
imply x = y; it is convenient to write x:::; y, and to write x < y when also x =I y.
Examples: the (nonstrict) inequalities between whole numbers, or between real
numbers, the inclusion relation between subsets of a set. When the conditions (i)
and (ii) above are satisfied, one speaks of a total order- clearly not so in the case
of inclusion - and of a well ordering when (iii) is also satisfied. This last concept
was invented by Cantor whose two fundamental articles are available, with a
long and interesting historical introduction in somewhat outdated language by
its British translator: Georg Cantor, Contributions to the Founding of the Theory
of Transfinite Numbers (Open Court Publishing Cy, 1915, reprinted Dover, 1955)
I - Sets and Functions
have either X E a and thus a E X E a, impossible, or X = a and then a E a,
impossible, qed.
The two possibilities s(a) E X and s(a) = X can very well arise. The
second is trivially satisfied if one puts X = s(a) for an ordinal a, for example
a von Neumann integer, or for a = N. For X = N, the first happens for any
aEX.
One can finally prove, but it is much more difficult, that
(11) Every set is equipotent to an ordinal. It can be shown that this statement is equivalent to the axiom of choice.
These properties explain the word "ordinal". For consider an ordinal X
and, for x, y E X, let us write x < y if x E y. Then we have the following
statements, which everyone knows in the case of N:
(i) x < y and y < z imply x < Z;
(ii) for any x, y, one and only one of the following relations is true:
x < y, x = y, y < x;
(iii) in every nonempty subset A of X, there exists an a such that a < x for
all x E A other than a.
(i) follows from (7) since x < y, i.e. x E y, is equivalent to x C y and
x f. y; (ii) and (iii) are the properties (9) and (4).
That said, let us consider an arbitrary set E and, thanks to (11), let us
choose an ordinal X and a bijection f of E onto X. Given two elements x
and y of E, let us agree to write that
x < y <===} f(x) < f(y)·
One thus obtains an order relation 3l on E, possessing the properties (i),
(ii) and (iii): we describe this by saying that E is a well ordered set. There
does indeed exist such an order relation on the set lR of real numbers; but
it clearly cannot be the one that everyone knows - this does not satisfy
(iii): the set of numbers> 0 does not possess a least element, this is the
31 On a set E, an order relation is a relation xRy between the elements of E such
that (a) one has xRx for all x E E, (b) xRy and yRz imply xRz, (c) xRy and yRx
imply x = y; it is convenient to write x:::; y, and to write x < y when also x =I y.
Examples: the (nonstrict) inequalities between whole numbers, or between real
numbers, the inclusion relation between subsets of a set. When the conditions (i)
and (ii) above are satisfied, one speaks of a total order- clearly not so in the case
of inclusion - and of a well ordering when (iii) is also satisfied. This last concept
was invented by Cantor whose two fundamental articles are available, with a
long and interesting historical introduction in somewhat outdated language by
its British translator: Georg Cantor, Contributions to the Founding of the Theory
of Transfinite Numbers (Open Court Publishing Cy, 1915, reprinted Dover, 1955)