Mathematics for Computer Science

Chapter 4 Mathematical Data Types108

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.26.
LetA,B, andCbe sets, and letf WB!C andgWA!Bbe functions. Let
hWA!Cbe the composition,fıg, that is,h.x/WWDf.g.x//forx 2 A. 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 andf is total, thengmust be injective.

Problem 4.27.
LetRbe a binary relation on a setD. Letx;ybe variables ranging overD. Circle
the expressions below whose meaning is thatRis aninjectionŒ 1 inç. Remember
Ris a not necessarily total or a function.

1.R.x/DR.y/IMPLIESxDy

2.R.x/\R.y/D;IMPLIESx¤y

3.R.x/\R.y/¤;IMPLIESx¤y

4.R.x/\R.y/¤;IMPLIESxDy

5.R^1 .R.x//Dfxg

6.R^1 .R.x//fxg

7.R^1 .R.x//fxg

8.R.R^1 .x//Dx