# GATE CSE 2010 | Question: 3

4k views

What is the possible number of reflexive relations on a set of 5 elements?

1. $2^{10}$
2. $2^{15}$
3. $2^{20}$
4. $2^{25}$

edited
6

This might help ...

A relation consists of set of ordered pairs $(a,b)$. Here, $a$ can be chosen in $n$ ways and similarly, $b$ can be chosen in $n$ ways. So, totally $n^2$ possible ordered pairs are possible for a relation. Now each of these ordered pair can either be present in the relation or not- 2 possibilities for each of the $n^2$ pair. So, total number of possible relations =  $$2^{\left(n^2\right)}$$

Now, for a relation $R$ to be reflexive, ordered pairs $\left\{(a,a) \mid a \in S \right\}$, must be present in $R$. i.e.; the relation set $R$ must have $n$ ordered pairs fixed. So, number of ordered pairs possible is $n^2 - n$ and hence total number of reflexive relations is equal to $$2^{\left(n^2-n\right)}$$

for $n=5$, answer will be, $2^{5^2-5}=2^{20}$

Therefore, option C is correct

edited
The number of reflexive relations =2^(n^2 - n) so option c is correct

The number of reflexive relations is given by $2^{n^{2}-n}$. The reasoning is not always very clear so here is the explanation:

• If the relation must be reflexive means we need to have all the self-pairs, e.g. (1,1) for all elements in the set. So choice for these is one as they have to be included, no matter what.
• Now come the other pairs left. These may or may not be included and it will not affect the overall reflexivity of the relation, as all self-pairs are already selected.

So, total self-pairs = $n$, and remaining pairs = ${n^2}-n$ , which is total minus the self-pairs and the left pairs still have a choice.

Hence total number of reflexive pairs =  $2^{n^{2}-n}$

Substituting $n$=5 for this question we get $2^{20}$, which is option (C).

## Related questions

1
4.8k views
Consider the set $S = \{1, ω, ω^2\}$, where $ω$ and $ω^2$ are cube roots of unity. If $*$ denotes the multiplication operation, the structure $(S, *)$ forms A Group A Ring An integral domain A field
Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$. Which one of the statements below expresses best the meaning of the formula, $\qquad∀x∃y∃t(¬F(x,y,t))$ Everyone can fool some person at some time No one can fool everyone all the time Everyone cannot fool some person all the time No one can fool some person at some time
Consider the following matrix $A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$ If the eigenvalues of A are $4$ and $8$, then $x = 4$, $y = 10$ $x = 5$, $y = 8$ $x = 3$, $y = 9$ $x = -4$, $y =10$
Consider a company that assembles computers. The probability of a faulty assembly of any computer is $p$. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of $q$. What is the probability of a computer being declared faulty? $pq + (1 - p)(1 - q)$ $(1 - q)p$ $(1 - p)q$ $pq$