GATE CS 2020 Q17 — Sets, Relations and Functions

Let $A = \{1, 2, 3\}$ be a set with $n = 3$ elements.

A binary relation on $A$ is any subset of the Cartesian product $A \times A$. Since $|A \times A| = n^2 = 3^2 = 9$, the total number of possible binary relations on $A$ is:

$$\text{Total Relations} = 2^{n^2} = 2^9 = 512$$

For a relation $R$ to be reflexive, it must contain all diagonal pairs $(a, a)$ for every $a \in A$. That is, the elements $(1,1)$, $(2,2)$, and $(3,3)$ must be present in $R$.

The remaining $n^2 - n = 9 - 3 = 6$ non-diagonal elements can either be included or excluded from $R$. Therefore, the number of reflexive relations is:

$$\text{Reflexive Relations} = 2^{n^2 - n} = 2^6 = 64$$

The probability $P$ that a randomly chosen relation is reflexive is:

$$P = \frac{\text{Number of reflexive relations}}{\text{Total number of relations}} = \frac{2^{n^2 - n}}{2^{n^2}} = \frac{1}{2^n}$$

$$P = \frac{1}{2^3} = \frac{1}{8} = 0.125$$

Rounding off to three decimal places, the probability is 0.125.