# GATE1999-1.2

3.1k views

The number of binary relations on a set with $n$ elements is:

1. $n^2$

2. $2^n$

3. $2^{n^2}$

4. None of the above

retagged
0

Same question was asked in 1987, see below :-

https://gateoverflow.in/82436/gate1987-9a

Answer: $C$

In a binary relation two elements are chosen from the set. So, with $n$ elements $n^2$ pairings are possible. Now, a relation can be any subset of these $n^2$ pairings and thus we get $2^{n^2}$ binary relations.

edited
2
@shaik could you pls explain more
0
Think of the boolean matrix of the relation, where an element is related to another element if the matrix entry for that pair is 1. If unrelated, 0.

There are $n^2$ entries in this matrix. Each entry can be $1$ or $0$. Therefore there are $2^{n^{2}}$ possible choices and that many relations.
0
what if binary word is removed

## Related questions

1
1.6k views
Let $L$ be a set with a relation $R$ which is transitive, anti-symmetric and reflexive and for any two elements $a, b \in L$, let the least upper bound $lub (a, b)$ and the greatest lower bound $glb (a, b)$ exist. Which of the following is/are true? $L$ is a poset $L$ is a Boolean algebra $L$ is a lattice None of the above
2
1.1k views
Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof: &ldquo;From xRy, using symmetry we get yRx. Now because R is transitive xRy and yRx together imply xRx. Therefore, R is reflexive&rdquo;. Give an example of a relation R which is symmetric and transitive but not reflexive.
3
754 views
Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$. Show that $|aH| = |bH|.$ Show that for every pair of elements $a, b \in G$, either $aH = bH$ or $aH$ and $bH$ are disjoint. Use the above to argue that the order of $H$ must divide the order of $G.$