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

Hint: 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{align}
  & \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{align}$
Out of these, the reflexive relations are:
$\begin{align}
  & \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{align}$
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.