§ 1. Set Theory
23
fi(x) = fJ(x) for every x E Xi n Xj.
Conversely, if this compatibility condition is satisfied then the function f
does exist: to define f(x) at an x E X one chooses an i E I such that
x E Xi arbitrarily, and then puts f(x) = fi(X); one has done the necessary
to eliminate any ambiguity in the definition of f(x). Further, the graph G of
f is the union of the graphs Gi C Xi X Y C X x Y of the IiThe situation is particularly simple if one has a partition of X, i.e. a
family of pairwise disjoint sets (Xi)iEI whose union is X. For every x E X,
there then exists one and only one i E I such that x E Xi, so that one may
choose the fi arbitrarily. If, on JR, for each integer n of arbitrary sign you
have a function f n defined for n ::; x < n + 1 (do not confuse the signs ::;
and <, see Chap. II, n° 2), then there exists a function f defined on JR which
agrees with fn for n ::; x < n + 1. If, on the other hand, the fn are given for
n::; x ::; n + 1, then f exists only if fn(n + 1) = fn+l(n + 1) for every n.
The concept of a family of sets is linked to the axiom of choice: given a
family of nonempty subsets (Xi)iEI of a set X there exists a map f : I -----4 X
such that f(i) E Xi for every i E I. Intuitively, one obtains f by "choosing
arbitrarily" an element Xi from each Xi. Cantor and others used it implicitly
until it was identified explicitly (Zermelo, Whitehead and Russell). As we said
at the beginning of this chapter, many mathematicians objected to "infinities
of random choices" with no precise mathematical sense that could never lead
to "explicit" formulae. No matter that it has survived by virtue of its use
in all sorts of branches of mathematics, where, most of the time, one uses it
without even a mention. Moreover, it was later proved (Paul Cohen, 1963)
that the axiom of choice is logically independent of the other axioms of set
theory: that if they are themselves not inconsistent, as one hopes (though this
has never been proved), then adjoining the axiom of choice will not lead to a
contradiction. You can adopt it or reject it. What is more, there are branches
of mathematics - arithmetic, for example - which can be constructed without
using it.
The axiom of choice comes in when one tries to extend the concept of
the cartesian product to an arbitrary family (Xi)iEI of sets. Their cartesian
product, properly, can only be the set of families (Xi)iEI such that Xi E Xi for
every i E I. The axiom of choice amounts to saying that a cartesian product
of nonempty sets is always nonempty.
6 - Injections, surjections, bijections
Let us return to maps in general. Given three sets X, Y, Z and maps
f : X -----4 Y and 9 : Y -----4 Z, one can construct the composed map
h : X -----4 Z by putting
h(x) = g[f(x)] for every x E X.
23
fi(x) = fJ(x) for every x E Xi n Xj.
Conversely, if this compatibility condition is satisfied then the function f
does exist: to define f(x) at an x E X one chooses an i E I such that
x E Xi arbitrarily, and then puts f(x) = fi(X); one has done the necessary
to eliminate any ambiguity in the definition of f(x). Further, the graph G of
f is the union of the graphs Gi C Xi X Y C X x Y of the IiThe situation is particularly simple if one has a partition of X, i.e. a
family of pairwise disjoint sets (Xi)iEI whose union is X. For every x E X,
there then exists one and only one i E I such that x E Xi, so that one may
choose the fi arbitrarily. If, on JR, for each integer n of arbitrary sign you
have a function f n defined for n ::; x < n + 1 (do not confuse the signs ::;
and <, see Chap. II, n° 2), then there exists a function f defined on JR which
agrees with fn for n ::; x < n + 1. If, on the other hand, the fn are given for
n::; x ::; n + 1, then f exists only if fn(n + 1) = fn+l(n + 1) for every n.
The concept of a family of sets is linked to the axiom of choice: given a
family of nonempty subsets (Xi)iEI of a set X there exists a map f : I -----4 X
such that f(i) E Xi for every i E I. Intuitively, one obtains f by "choosing
arbitrarily" an element Xi from each Xi. Cantor and others used it implicitly
until it was identified explicitly (Zermelo, Whitehead and Russell). As we said
at the beginning of this chapter, many mathematicians objected to "infinities
of random choices" with no precise mathematical sense that could never lead
to "explicit" formulae. No matter that it has survived by virtue of its use
in all sorts of branches of mathematics, where, most of the time, one uses it
without even a mention. Moreover, it was later proved (Paul Cohen, 1963)
that the axiom of choice is logically independent of the other axioms of set
theory: that if they are themselves not inconsistent, as one hopes (though this
has never been proved), then adjoining the axiom of choice will not lead to a
contradiction. You can adopt it or reject it. What is more, there are branches
of mathematics - arithmetic, for example - which can be constructed without
using it.
The axiom of choice comes in when one tries to extend the concept of
the cartesian product to an arbitrary family (Xi)iEI of sets. Their cartesian
product, properly, can only be the set of families (Xi)iEI such that Xi E Xi for
every i E I. The axiom of choice amounts to saying that a cartesian product
of nonempty sets is always nonempty.
6 - Injections, surjections, bijections
Let us return to maps in general. Given three sets X, Y, Z and maps
f : X -----4 Y and 9 : Y -----4 Z, one can construct the composed map
h : X -----4 Z by putting
h(x) = g[f(x)] for every x E X.