§ 1. Set Theory
25
in the first case one has to consider the x E X such that f (x) E B' U BIf, i.e.
such that f(x) E B' or f(x) E BIf; in the second, those x such that f(x) E B'
and f(x) E BIf, whence the formulae, which you can extend to the case of
unions and intersections of arbitrary families of sets.
It can happen that a map f : X --+ Y is simultaneously injective and
surjective; one then says that f is bijective or is a bijection; this means that
for every bEY the equation f(x) = b has one and only one solution x E X.
The map x 1---+ x 3 of IR into IR is bijective. The map x 1---+ x + 1 of N into N
is injective but not surjective; it is a bijection of
N = {O, 1,2,3, ... } onto {I, 2,3,4, ... } = N - {OJ.
The map x 1---+ x 2 of IR into IR is neither injective nor surjective; it becomes
bijective if one replaces IR by 1R+, the set of real numbers 2: o.
When a map f : X --+ Y is bijective one can define the inverse map
1-1 : Y --+ X as follows: its graph G c Y x X is the set of ordered pairs
(y,x) such that (x,y) E F, the graph of f. Since one and only one x E X
corresponds to each y E Y, G really is a graph and one sees that
(6.4)
x = r 1 (y) {=} y = f(x).
It comes to the same to say that
1- 10 f(x) = x for every x E X and f 0 f-l(y) = Y for every y E Y.
If one writes idx for the identity map x 1---+ x of X into X then
1- 10 1=idx ,
fol-1 =idy .
For example, the inverse map of x 1---+ x 3 on IR is x 1---+ x 1 / 3 , the cube root
of x.
It is clear that if one composes maps which are all injective, or all surjective, or all bijective, one obtains a map of the same kind: to solve g(J(x» = c,
one has to find a b such that c = g(b), then an x such that b = f(x), whence
the results.
1 - Equipotent; sets. Countable sets
It is "obvious" that if X is a finite set - a concept which we have not yet
defined strictly - and I is an injective map of X into a set Y then the image
I(X) has as many elements as X. If, in particular, Y = X, then f cannot be
injective unless it is surjective too; this is the property which Dedekind used
to define a finite set; the others being said to be infinite. (There are other
ways of proceeding, as we shall see.) The example of the map n 1---+ n + 1 of
N into N shows that N is infinite in Dedekind's sense.
When there is a bijection of a set X onto a set Y one says that X and Y
are equipotent (or have the same power, which assumes that we have defined
25
in the first case one has to consider the x E X such that f (x) E B' U BIf, i.e.
such that f(x) E B' or f(x) E BIf; in the second, those x such that f(x) E B'
and f(x) E BIf, whence the formulae, which you can extend to the case of
unions and intersections of arbitrary families of sets.
It can happen that a map f : X --+ Y is simultaneously injective and
surjective; one then says that f is bijective or is a bijection; this means that
for every bEY the equation f(x) = b has one and only one solution x E X.
The map x 1---+ x 3 of IR into IR is bijective. The map x 1---+ x + 1 of N into N
is injective but not surjective; it is a bijection of
N = {O, 1,2,3, ... } onto {I, 2,3,4, ... } = N - {OJ.
The map x 1---+ x 2 of IR into IR is neither injective nor surjective; it becomes
bijective if one replaces IR by 1R+, the set of real numbers 2: o.
When a map f : X --+ Y is bijective one can define the inverse map
1-1 : Y --+ X as follows: its graph G c Y x X is the set of ordered pairs
(y,x) such that (x,y) E F, the graph of f. Since one and only one x E X
corresponds to each y E Y, G really is a graph and one sees that
(6.4)
x = r 1 (y) {=} y = f(x).
It comes to the same to say that
1- 10 f(x) = x for every x E X and f 0 f-l(y) = Y for every y E Y.
If one writes idx for the identity map x 1---+ x of X into X then
1- 10 1=idx ,
fol-1 =idy .
For example, the inverse map of x 1---+ x 3 on IR is x 1---+ x 1 / 3 , the cube root
of x.
It is clear that if one composes maps which are all injective, or all surjective, or all bijective, one obtains a map of the same kind: to solve g(J(x» = c,
one has to find a b such that c = g(b), then an x such that b = f(x), whence
the results.
1 - Equipotent; sets. Countable sets
It is "obvious" that if X is a finite set - a concept which we have not yet
defined strictly - and I is an injective map of X into a set Y then the image
I(X) has as many elements as X. If, in particular, Y = X, then f cannot be
injective unless it is surjective too; this is the property which Dedekind used
to define a finite set; the others being said to be infinite. (There are other
ways of proceeding, as we shall see.) The example of the map n 1---+ n + 1 of
N into N shows that N is infinite in Dedekind's sense.
When there is a bijection of a set X onto a set Y one says that X and Y
are equipotent (or have the same power, which assumes that we have defined