GATE CS 2010 Q3 — Sets, Relations and Functions

A relation $R$ on a set $A$ with $n$ elements is a subset of the Cartesian product $A \times A$. The total number of ordered pairs in $A \times A$ is $n^2$.

For a relation $R$ to be reflexive, it must contain all diagonal elements of the form $(a, a)$ for every $a \in A$.

• Diagonal elements: There are exactly $n$ such elements, and all of them must be included in the relation (only $1$ choice for each).
• Non-diagonal elements: There are $n^2 - n$ remaining elements. Each of these elements can either be included or excluded from the relation (exactly $2$ choices for each).

Therefore, the total number of reflexive relations on a set of $n$ elements is given by:

Given $n = 5$:

Hence, the correct option is C.