Home ] Up ]


I. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry,  and transitivity. Check whether the binary relations are equivalence, and/or partial/total ordering relations or neither, describe the equivalence classes if applicable. 

  a) S = {0,1,2,3,4},   R1={(0,0),(1,1),(2,2),(3,3),(4,4),(2,4),(0,1),(1,2),(4,3)} 

b) S = P({a,b,c,d,e,f,g,h,i}) [ P: Power set], (A,B) belongs to R2 if and only if |A| = |B| 

c) S = N [N: set of positive integers]. (x,y) belongs to R3 if and only if x^2 - y^2 is even.

[x^2 : stands for x squared]. 



II. Let S = { 0,2,4,6}, and T = {1,3,5,7}. Determine whether each of the following sets of ordered  pairs is a function from S to T. If so, is it injective, surjective, and bijective. 

a. {(0,2),(2,4),(4,6),(6,0)}

b. {(6,3),(2,1),(0,3),(4,5)}

c. {(2,3),(4,7),(0,1),(6,5)} 



III. Let S = {1,2,3,4,5,6,7,8}, and let |T| = n.

a. How many different function can we define from S to S?

b. If n=10, how many injective functions can we define from S to T?

c. How many bijections can we define from S to S?




IV. You have a group of 10 men and 6 women.

a) In how many ways can you seat them in a row?

b) In how many ways can you choose a committee of 5 with at least 2 women?




V. A florist has roses, carnations, lilies, and snapdragons in stock. How many different bouquets of one dozen flowers can be made? Explain briefly.