Mathematics for Computer Science

Chapter 4 Mathematical Data Types106

Problem 4.20.
Give an example of a relationRthat is a total injective function from a setAto
itself but is not a bijection.

Problem 4.21.
LetRWA!Bbe a binary relation. Each of the following formulas expresses
the fact thatRhas a familiar relational “arrow” property such as being surjective
or being a function.
Identify the relational property expressed by each of the following relational
expressions. Explain your reasoning.

(a)RıR^1 IdB

(b)R^1 ıRIdA

(c)R^1 ıRIdA

(d)RıR^1 IdB

Class Problems

Problem 4.22. (a)Prove that ifAsurjBandBsurjC, thenAsurjC.

(b)Explain whyAsurjBiffBinjA.

(c)Conclude from (a) and (b) that ifAinjBandBinjC, thenAinjC.

(d)Explain whyAinjBiff there is a total injectivefunction(ŒD 1 out; 1 inç)
fromAtoB.^11

Problem 4.23.
Five basic properties of binary relationsRWA!Bare:

1.Ris a surjectionŒ 1 inç

2.Ris an injectionŒ 1 inç

3.Ris a functionŒ 1 outç

4.Ris totalŒ 1 outç

(^11) The official definition of inj is with a total injectiverelation(Œ 1 out; 1 inç)