search
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
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}$
in Set Theory & Algebra
edited by
4k views
6

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

 

Answer:

Related questions

18 votes
3 answers
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
asked Sep 21, 2014 in Set Theory & Algebra gatecse 4.8k views
47 votes
4 answers
2
8.2k views
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
3
3.3k views
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
4
4.3k views
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
...