16
I - Sets and Functions
presents another advantage, because of which it has been adopted almost
universally for the construction of the "infinite ordinals" of Cantor, as we
shall show in nO 9.
The question of how to know whether the sets used to define the integers
are themselves elements of some set, in other words, that of the existence of
the set N of whole numbers, is not logically evident; it would be, by the axiom
of separation, if one already knew of the existence of a set of which at least
all the integers are elements, but where to find one? All the sets we have
actually constructed up to now, starting from the one set whose existence
is guaranteed a priori, namely 0, have a finite number of elements, while,
according to all the evidence, N must possess infinitely many, whatever the
precise definition of this tenn. To justify its existence one thus introduces the
axiom of infinity: one possible formulation of this is to posit the existence of
a set X such that
(3.3)
(0 E X) and (x E X implies sex) EX),
as would clearly be true of N if one already knew that N existed; this is
not the case of the sets 0, 1, 2 etc. defined above: we have 2 E 3 but the
relation s(2) E 3 is false. A set satisfying the conditions (3) is sometimes
called inductive. Let us show how to construct N starting from here.
First, it is clear that every union or intersection of inductive sets is inductive. If, in any inductive set X, one considers the intersection Xo of all
the inductive sets X' C X one thus obtains the "smallest" inductive set contained in X. If Y is another inductive set then X n Y is an inductive subset
of both X and of Y, so contains Xo and Yo; Yo is thus an inductive subset
of X, whence Yo ::J Xo and vice versa; in other words Xo = Yo. The set Xo
defined in each inductive set X is thus the same independently of X; it is, by
definition, the set N of whole numbers, and, similarly, the smallest of "all"
inductive sets (which are too numerous to be the elements of a set).
Since N is inductive and contains 0 it contains all the whole numbers d la
von Neumann. This proves that they belong to a common set, and therefore
we may speak of the set E of these integers. It is clear that it is inductive
and is contained in N. Hence E = N, so the elements of N are precisely the
integers d la von Neumann.
From this follows the principle of proof by induction: to show that a property P{ n}, in which the letter n symbolises an indeterminate ''variable'', is
true for every n E N one shows that
(i) it is true for n = 0, i.e., in ordinary language, for n = 0,
(ii) the relation P{n} implies P{s(n)} i.e., in ordinary language, that P{n}
implies P{n + I}.
If this is so, then the set of n E N satisfying P { n} is inductive and contained
in N, so equal to N.
I - Sets and Functions
presents another advantage, because of which it has been adopted almost
universally for the construction of the "infinite ordinals" of Cantor, as we
shall show in nO 9.
The question of how to know whether the sets used to define the integers
are themselves elements of some set, in other words, that of the existence of
the set N of whole numbers, is not logically evident; it would be, by the axiom
of separation, if one already knew of the existence of a set of which at least
all the integers are elements, but where to find one? All the sets we have
actually constructed up to now, starting from the one set whose existence
is guaranteed a priori, namely 0, have a finite number of elements, while,
according to all the evidence, N must possess infinitely many, whatever the
precise definition of this tenn. To justify its existence one thus introduces the
axiom of infinity: one possible formulation of this is to posit the existence of
a set X such that
(3.3)
(0 E X) and (x E X implies sex) EX),
as would clearly be true of N if one already knew that N existed; this is
not the case of the sets 0, 1, 2 etc. defined above: we have 2 E 3 but the
relation s(2) E 3 is false. A set satisfying the conditions (3) is sometimes
called inductive. Let us show how to construct N starting from here.
First, it is clear that every union or intersection of inductive sets is inductive. If, in any inductive set X, one considers the intersection Xo of all
the inductive sets X' C X one thus obtains the "smallest" inductive set contained in X. If Y is another inductive set then X n Y is an inductive subset
of both X and of Y, so contains Xo and Yo; Yo is thus an inductive subset
of X, whence Yo ::J Xo and vice versa; in other words Xo = Yo. The set Xo
defined in each inductive set X is thus the same independently of X; it is, by
definition, the set N of whole numbers, and, similarly, the smallest of "all"
inductive sets (which are too numerous to be the elements of a set).
Since N is inductive and contains 0 it contains all the whole numbers d la
von Neumann. This proves that they belong to a common set, and therefore
we may speak of the set E of these integers. It is clear that it is inductive
and is contained in N. Hence E = N, so the elements of N are precisely the
integers d la von Neumann.
From this follows the principle of proof by induction: to show that a property P{ n}, in which the letter n symbolises an indeterminate ''variable'', is
true for every n E N one shows that
(i) it is true for n = 0, i.e., in ordinary language, for n = 0,
(ii) the relation P{n} implies P{s(n)} i.e., in ordinary language, that P{n}
implies P{n + I}.
If this is so, then the set of n E N satisfying P { n} is inductive and contained
in N, so equal to N.