Mathematics for Computer Science

Chapter 4 Mathematical Data Types82

Class Problems

Problem 4.10.
Define asurjection relation, surj, on sets by the rule

Definition.AsurjBiff there is a surjectivefunctionfromAtoB.

Define theinjection relation, inj, on sets by the rule

Definition.AinjBiff there is a total injectiverelationfromAtoB.

(a)Prove that ifAsurjBandBsurjC, thenAsurjC.

(b)Explain whyAsurjBiffBinjA.

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

Problem 4.11.
LetAbe the following set of five propositional formulas shown below on the left,
and letC be the set of three propositional formulas on the right. The “implies”
binary relation,I, fromAtoCis defined by the rule

F I G iff Œthe formula.FIMPLIESG/is validç:

For example,.PANDQ/ I P, because the formula.PANDQ/does implyP.
Also, it is not true that.PORQ/ I Psince.PORQ/IMPLIESPis not valid.

(a)Fill in the arrows so the following figure describes the graph of the relation,I: