Question

The number of reflexive relations of a set with four elements is equal to
(a) ${{2}^{16}}$
(b) ${{2}^{12}}$
(c) ${{2}^{8}}$
(d) ${{2}^{4}}$

Answer 1

By going through the definition of reflexive relations, we will first try to find the number of reflexive relations in a set of two elements. With the help of that, we will try to get the number of reflexive relations in a four-element set.

Complete step-by-step solution:
If there are $n$ elements in a set $X$ and a relation $R$ is defined from the set $X$ to $X$, then the relation $R$ is called a reflexive relation if every element of $X$ is related to itself. In other words, a relation R is reflexive if $\forall x\in X,\left( x,x \right)\in R$.
For an example, let us consider a set X=\left\\{ a,b,c \right\\} and let us define two relations ${{R}_{1}}$ and ${{R}_{2}}$, then the relation {{R}_{1}}=\left\\{ \left( a,a \right),\left( b,b \right),\left( c,c \right),\left( a,c \right),\left( b,c \right) \right\\} is reflexive, as $\forall x\in X,\left( x,x \right)\in {{R}_{1}}$. But the relation {{R}_{2}}=\left\\{ \left( a,a \right),\left( b,b \right),\left( a,c \right),\left( b,c \right) \right\\} is not reflexive, as $\left( c,c \right)\notin {{R}_{2}}$ which violates the condition $\forall x\in X,\left( x,x \right)\in {{R}_{2}}$.
Let us consider a set X=\left\\{ 1,2 \right\\} of two elements. Then the total number of relations on the set $X$ can be defined as:
\begin{aligned} & \varnothing ,\left\\{ \left( 1,1 \right) \right\\},\left\\{ \left( 2,2 \right) \right\\},\left\\{ \left( 1,2 \right) \right\\},\left\\{ \left( 2,1 \right) \right\\},\left\\{ \left( 1,1 \right),\left( 1,2 \right) \right\\},\left\\{ \left( 1,1 \right),\left( 2,1 \right) \right\\},\left\\{ \left( 2,2 \right),\left( 1,2 \right) \right\\}, \\\ & \left\\{ \left( 2,2 \right),\left( 2,1 \right) \right\\},\left\\{ \left( 2,1 \right),\left( 1,2 \right) \right\\},\left\\{ \left( 1,1 \right),\left( 2,2 \right) \right\\},\left\\{ \left( 1,1 \right),\left( 1,2 \right),\left( 2,1 \right) \right\\},\left\\{ \left( 2,2 \right),\left( 1,2 \right),\left( 2,1 \right) \right\\}, \\\ & \left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 1,2 \right) \right\\},\left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 2,1 \right) \right\\},\left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 1,2 \right),\left( 2,1 \right) \right\\} \\\ \end{aligned}
Out of these, the reflexive relations are:
\begin{aligned} & \left\\{ \left( 1,1 \right),\left( 2,2 \right) \right\\} \\\ & \left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 1,2 \right) \right\\} \\\ & \left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 2,1 \right) \right\\} \\\ & \left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 1,2 \right),\left( 2,1 \right) \right\\} \\\ \end{aligned}
Thus, out of the total $16={{2}^{{{2}^{2}}}}$ relations, only $4={{2}^{\left( {{2}^{2}}-2 \right)}}$ are reflexive.
Similarly, we can find that for a four-element set, the total number of relations is ${{2}^{{{4}^{2}}}}$ and out of these ${{2}^{{{4}^{2}}-4}}={{2}^{12}}$ relations are reflexive.
Hence, option (b) is correct.

Note: For a set of $n$ elements, we can generalize the formula as
Total number of relations $={{2}^{{{n}^{2}}}}$
Total number of reflexive relations $={{2}^{{{n}^{2}}-n}}={{2}^{n\left( n-1 \right)}}$
Thus, this can be used as a short-cut trick for solving these types of questions.