Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
21 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}$
in Set Theory & Algebra
edited by

This might help ...

3 Answers

34 votes
Best answer

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
7 votes
The number of reflexive relations =2^(n^2 - n) so option c is correct
0 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).



Related questions

18 votes
3 answers
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
asked Sep 21, 2014 in Set Theory & Algebra gatecse 4.8k views
47 votes
4 answers
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
asked Sep 21, 2014 in Mathematical Logic gatecse 8.2k views
16 votes
3 answers
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$
asked Sep 21, 2014 in Linear Algebra gatecse 3.3k views
19 votes
4 answers
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$
asked Sep 21, 2014 in Probability gatecse 4.3k views