Answer to Question #148107 in Discrete Mathematics for Promise Omiponle

Question

(a) If A={1,2,3,4}, calculate the number of reflexive relations on A.
(b) If B={1,2,3,4,5}, calculate the number of symmetric relations on B.

Answer 1

(a) Reflexive relations are those where (a,a) belongs to the relation set. Now number of such elements is 4 namely, (1,1),(2,2),(3,3),(4,4). But number of elements of $A\times A$ is $4^2=16.$ Hence number of reflexive relations = number of relations containing those four elements. So fixing those 4 elements we have to take subsets of 16-4=12 elements. Hence number of reflexive relations are $2^{12}.$

(b) For symmetric, we need if (a,b) is there then (b,a) is also there. If a=b, then (a,b)=(b,a). Total number of elements of the form (a,b) is $5\times 5=25.$ So number of elements (a,b) with $a\neq b$ is 25-5=20. We take only one element out of (a,b) and (b,a). Then there are 20/2=10 such elements. So total we get 10+5=15 elements. So number of subsets we get is $2^{15}.$ Now in each of these sets, we add the elements (b,a) corresponding to (a,b) and thus get all symmetric relations. Hence number of symmetric relations is $2^{15}.$