4.5. Finite Cardinality 113
Problem 4.32.
LetRWA!Bbe a binary relation.
(a)Prove thatRis a function iffRıR ^1 IdB.
Write similar containment formulas involvingR ^1 ıR,RıR ^1 , Ida, IdBequivalent
to the assertion thatRhas each of the following properties. No proof is required.
(b)total.(c)a surjection.(d)a injection.Problem 4.33.
LetRWA!BandSWB!Cbe binary relations such thatSıRis a bijection
andjAjD 2.
Give an example of suchR;Swhere neitherRnorSis a function.
Hint:LetjBjD 4.
Problems for Section 4.5
Practice Problems
Problem 4.34.
Assumef WA!Bis total function, andAis finite. Replace the?with one of
;D;to produce thestrongestcorrect version of the following statements:
(a)jf.A/j?jBj.(b)Iff is a surjection, thenjAj?jBj.(c)Iff is a surjection, thenjf.A/j?jBj.(d)Iff is an injection, thenjf.A/j?jAj.(e)Iff is a bijection, thenjAj?jBj.Class Problems
Problem 4.35.
LetAD fa 0 ;a 1 ;:::;an 1 gbe a set of sizen, andBD fb 0 ;b 1 ;:::;bm 1 ga set
of sizem. Prove thatjABjDmnby defining a simple bijection fromABto
the nonnegative integers from 0 tomn 1.