Mathematics for Computer Science

4.5. Finite Cardinality 107

5.Ris emptyŒD 0 outç

Below are some assertions about a relationR. For each assertion, write the
numbers of all the properties above that the relationRmust have; write “none” if
Rmight not have any of these properties. For example, you should write “(1), (4)”
next to the first assertion.
Variablesa;a 1 ;:::range overAandb;b 1 ;:::range overB.
(a) 8 a 8 b: a R b. (1), (4)

(b) NOT. 8 a 8 b: a R b/.

(c) 8 a 8 b: QNOT.a R b/.

(d) 8 a 9 b: a R b.

(e) 8 b 9 a: a R b.

(f)Ris a bijection.

(g) 8 a 9 b 1 a R b 1

V

8 b:a R bIMPLIESbDb 1.

(h) 8 a;b: a R bORa¤b.

(i) 8 b 1 ;b 2 ;a: .a R b 1 ANDa R b 2 /IMPLIESb 1 Db 2.

(j) 8 a 1 ;a 2 ;b: .a 1 R bANDa 2 R b/IMPLIESa 1 Da 2.

(k) 8 a 1 ;a 2 ;b 1 ;b 2 : .a 1 R b 1 ANDa 2 R b 2 ANDa 1 ¤a 2 /IMPLIESb 1 ¤b 2.

(l) 8 a 1 ;a 2 ;b 1 ;b 2 : .a 1 R b 1 ANDa 2 R b 2 ANDb 1 ¤b 2 /IMPLIESa 1 ¤a 2.

Homework Problems

Problem 4.24.
Letf WA!BandgWB!Cbe functions.

(a)Prove that if the compositiongıf is a bijection, thenf is a total injection
andgis a surjection.

(b)Show there is a total injection,f, and a bijection,g, such thatgıf is not a
bijection.

Problem 4.25.
LetA,B, andC be nonempty sets, and letf WB !C andg WA! Bbe