Question

1. (9pts) Suppose A is a set with m elements and B is a set with n elements. a. How many relations are there from A to B? Explain b. How many functions are there from A to B? Explain C. How many relations from A to itself are reflexive? Explain

Answer 1

Ans: Given that A is a set with m elements and B is a set with n elements.
 a. If A ={a1, a2, a3......am} and B ={b1, b2, b3.....bn} 
     then Cartesian product of A and B is:
      A X B = {(a1, b1), (a1, b2), (a1, b3)........., (a1, bn), 
               (a2, b1), (a2, b2), (a2, b3).........., (a2, bn),
                ................. 
               (am, b1),(am, b2), (am, b3),........., (am, bn)}
This set of ordered pairs contains mn pairs. 
Now these pairs can be present in A X B or can be absent. 
So total number of possible relation = 2mn

b.

Suppose there are two sets ‘A’ and ‘B’ containing ‘m’ and ‘n’ number of elements respectively, i.e., Sets,

'A' = {1, 2, 3, 4, ............, m},
'B' = {1, 2, 3, 4, ............, n} 

Each element of set ‘A’ makes ‘n’ number of functions with each element of the set ‘B’ and hence total number of functions possible is |B|^|A|  i.e  n^m .

c.  A relation has ordered pairs (a,b). Now 'a' can be chosen in m ways and also 'b' can be choosen in m ways. So set of ordered pairs contains m² pairs. Now for a reflexive relation, (a,a) must be present in these ordered pairs. And there will be total m pairs of (a,a), so number of ordered pairs will be m²-m pairs. So total number of relations from A to itself are reflexive relations is equal to 2^m(m-1).