Question ID: #642
The number of relations, defined on the set {a, b, c, d}, which are both reflexive and symmetric, is equal to:
- (1) 256
- (2) 16
- (3) 1024
- (4) 64
Solution:
Let $A = \{a, b, c, d\}$. Total elements $n = 4$.
A relation is **Reflexive** if $(x, x) \in R$ for all $x \in A$.
This means the 4 diagonal pairs $\{(a,a), (b,b), (c,c), (d,d)\}$ **must** be included.
A relation is **Symmetric** if $(x, y) \in R \Rightarrow (y, x) \in R$.
This means the non-diagonal elements must be chosen in pairs. We cannot choose $(a,b)$ without $(b,a)$.
We can count the distinct symmetric pairs available for selection (Upper Triangular part):
1. $(a,b)$ and $(b,a)$ $\rightarrow$ 1 pair
2. $(a,c)$ and $(c,a)$ $\rightarrow$ 1 pair
3. $(a,d)$ and $(d,a)$ $\rightarrow$ 1 pair
4. $(b,c)$ and $(c,b)$ $\rightarrow$ 1 pair
5. $(b,d)$ and $(d,b)$ $\rightarrow$ 1 pair
6. $(c,d)$ and $(d,c)$ $\rightarrow$ 1 pair
Total distinct choice units (pairs) = 6.
For each of these 6 pairs, we have exactly 2 choices:
1. Include both in the relation.
2. Exclude both from the relation.
Total number of relations = $2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^6$.
$$2^6 = 64$$
Ans. (4)
Was this solution helpful?
YesNo