in Set Theory & Algebra retagged by
8,966 views
17 votes
17 votes

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

in Set Theory & Algebra retagged by
by
2261 2454 2576
9.0k views

1 comment

Same question was asked in 1987, see below :-

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

0
0

Subscribe to GO Classes for GATE CSE 2022

1 Answer

24 votes
24 votes
 
Best answer
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 by
by
191 292 382

3 Comments

@shaik could you pls explain more
2
2
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.
1
1
what if binary word is removed
0
0
Answer:

Related questions

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