GATE CSE 1987 | Question: 9a

Question

How many binary relations are there on a set $A$ with $n$ elements?

Comments

Binary relation on a set A is a subset of (AxA).

Ternary relation on a set A is a subset of (AxAxA).

---

@raja11sep 

@Udhay Brahmi

number of ternary relations in the set will be 2^(n^3) right??

Answer 1

The total number of binary relation from n element set to itself is $2^{n^{2}}$ i.e. $n^2$ entries with two choices take it or not.

Comments

Also, we can view it like this

A relation is a subset of AxB.

Here it will be a subset of AxA.

now AxA will contain $n^2$ terms

now number of relations is same as the number of binary bit strings of length $n^2$

Answer 2

∣A∣ =n

∣A⨉A∣ = n^2

Relation is the subsets of A⨉A, so the total no of binary relation on set A = cardinality of power set of (A⨉A)  = ∣ p(A⨉A) ∣ =2^(n^2)

                                                                                                                   

So, the correct answer is 2^(n^2).

                                                                                     

Answer 3

 

we know that 

number of elements in ∣A∣ =n

so total number of elements in ∣A⨉A∣ = n x n = n²

 

Relation is the subsets of A⨉A,

so the total no of binary relation on set A = cardinality of power set of (A⨉A) 

 

= ∣ p(A⨉A) ∣ =2^(n²)

Answer 4

here is another way to think about the answer

similar to functions , think about how many ways are there to map 1 element in domain A to the co-domain A?

as one element can be related/mapped to multiple elements at once in relations, there are $2^{|A|}$ mapping from a unique element in A to A because every element in codomain has a choice to be or not to be part of the mapping.

so total possible relations = $\Pi_{i=1}^n \text{mapping of }A_i = (2^n)^n = 2^{n^2}$