4 I The Expanding Universe of NumbersreflexiveifaRafor everya∈A;
symmetricifbRawheneveraRb;
transitiveifaRcwheneveraRbandbRc.
It is said to be anequivalence relationif it is reflexive, symmetric and transitive.
IfRis an equivalence relation on a setAanda∈ A,theequivalence class Ra
ofais the set of allx∈Asuch thatxRa.SinceRis reflexive,a∈Ra.SinceRis
symmetric,b∈Raimpliesa∈Rb.SinceRis transitive,b∈RaimpliesRb⊆Ra.It
follows that, for alla,b∈A, eitherRa=RborRa∩Rb=∅.
ApartitionCof a setAis a collection of nonempty subsets ofAsuch that each
element ofAis an element of exactly one of the subsets inC.
Thus the distinct equivalence classes corresponding to a given equivalence relation
on a setAform a partition ofA. It is not difficult to see that, conversely, ifCis a
partition ofA, then an equivalence relationRis defined onAby takingRto be the
set of all(a,b)∈A×Afor whichaandbare elements of the same subset in the
collectionC.
LetAandBbe nonempty sets. Amapping fofAintoBis a subset ofA×Bwith
the property that, for eacha∈A, there is a uniqueb∈Bsuch that(a,b)∈ f.We
writef(a)=bif(a,b)∈f, and say thatbis theimageofaunderfor thatbis the
valueof fata. We express that fis a mapping ofAintoBby writingf:A→B
and we put
f(A)={f(a):a∈A}.The termfunctionis often used instead of ‘mapping’, especially whenAandBare
sets of real or complex numbers, and ‘mapping’ itself is often abbreviated tomap.
If f is a mapping ofAintoB,andifA′is a nonempty subset ofA, then the
restrictionofftoA′is the set of all(a,b)∈ fwitha∈A′.
Theidentity map iAof a nonempty setAinto itself is the set of all ordered pairs
(a,a) witha∈A.
Iffis a mapping ofAintoB,andga mapping ofBintoC, then thecomposite
mapping g◦fofAintoCis the set of all ordered pairs (a,c), wherec=g(b)and
b=f(a). Composition of mappings is associative, i.e. ifhis a mapping ofCintoD,
then
(h◦g)◦f=h◦(g◦f).The identity map has the obvious propertiesf◦iA=fandiB◦f=f.
LetA,Bbe nonempty sets andf:A→Ba mapping ofAintoB. The mapping
fis said to be ‘one-to-one’ orinjectiveif, for eachb∈B, there exists at most one
a∈Asuch that(a,b)∈ f. The mappingfis said to be ‘onto’ orsurjectiveif, for
eachb∈B, there exists at least onea∈Asuch that(a,b)∈f.Iffis both injective
and surjective, then it is said to bebijectiveor a ‘one-to-one correspondence’. The
nounsinjection, surjectionandbijectionare also used instead of the corresponding
adjectives.
It is not difficult to see that fis injective if and only if there exists a mapping
g:B→Asuch thatg◦f=iA, and surjective if and only if there exists a mapping
h:B →Asuch thatf◦h=iB.Furthermore,iff is bijective, thengandhare