edited by
8,520 views
32 votes
32 votes

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 by

4 Answers

Best answer
43 votes
43 votes

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 by
4 votes
4 votes

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).

 

0 votes
0 votes

A relation consists of set of ordered pairs (a,b).

possible number of reflexive relations on a set of n elements=

2^(n^2 - n)

here n=5 

so answer is , 2^(5^2 - 5) =20

Answer:

Related questions

12 votes
12 votes
5 answers
1
go_editor asked Sep 30, 2014
6,495 views
$25$ persons are in a room. $15$ of them play hockey, $17$ of them play football and $10$ of them play both hockey and football. Then the number of persons playing neithe...
26 votes
26 votes
4 answers
2
gatecse asked Sep 21, 2014
9,730 views
Consider the set $S = \{1, ω, ω^2\}$, where $ω$ and $ω^2$ are cube roots of unity. If $*$ denotes the multiplication operation, the structure $(S, *)$ formsA GroupA R...
7 votes
7 votes
1 answer
3
go_editor asked Sep 30, 2014
3,874 views
Choose the most appropriate word from the options given below to complete the following sentence:If we manage to __________ our natural resources, we would leave a better...