Chapter 4 Mathematical Data Types84
Problem 4.13.
Letf WA!BandgWB!Cbe functions.
(a)Prove that if the compositiongıf is a bijection, thenfis an injection andg
is a surjection.
(b)Iffis an injection andgis a surjection, then isgıfnecessarily a bijection?Problem 4.14.
LetA,B, andC be nonempty sets, and letf WB !C andg WA! Bbe
functions. LethWWDf ıgbe the composition function off andg, namely, the
function with domainAand rangeCsuch thath.x/Df.g.x//.
(a)Prove that ifhis surjective andfis total and injective, thengmust be surjec-
tive.
Hint:contradiction.
(b)Suppose thathis injective andf is total. Prove thatgmust be injective and
provide a counterexample showing how this claim could fail iff wasnottotal.
Problem 4.15.
LetA,B, andCbe finite sets, and letf WB!CandgWA!Bbe functions.
Lethbe the function with domainAand rangeCthat mapsx 2 Atof.g.x//.
Prove or disprove the following claims:
(a)Ifhis surjective, thenfmust be surjective.(b)Ifhis surjective, thengmust be surjective.(c)Ifhis injective, thenf must be injective.(d)Ifhis injective, thengmust be injective.Problem 4.16.
There is a simple and useful way to extend composition of functions to composition
of relations. Namely, letRWB! CandSWA!Bbe relations. Then the
composition ofRwithSis the binary relation.RıS/WA!Cdefined by the
rule
a .RıS/ cWWD 9b 2 B:.b R c/AND.a S b/: