GATE CSE 1999 | Question: 1.2

Question

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

• A. $n^2$

• B. $2^n$

• C. $2^{n^2}$

• D. None of the above

Comments

Same question was asked in 1987, see below :-

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

Answer 1

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.

Comments

@shaik could you pls explain more

---

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.

---

what if binary word is removed

Answer 2

number of elements in binary relation are nxn = n^2.

Now , wvery pair in it has 2 choices , you either consider it in a relation or don't. so , 2x2x2x2........n^2 times = 2^(n^2)

Comments

right

Answer 3

max number of elements in a binary relation on a set of n elements = n x n = n^2

therefore number of binary relations= $2^{n^2}$

Comments

thanks initially i am confused

Answer 4

Let set A have n elements.

Since, relation is a subset of A x A

Therefore, A x A will have n² elements

Therefore, total no. of relations = 2ⁿ²

Correct Option :- C) 2ⁿ²

Answer 5

Set A,

|A|= n

Relation is subset of |A|*|A| = n*n;

R = 2^n*n