recategorized by
5,791 views
24 votes
24 votes
How many binary relations are there on a set $A$ with $n$ elements?
recategorized by

4 Answers

Best answer
39 votes
39 votes
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.
edited by
18 votes
18 votes

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

                                                                                     

0 votes
0 votes

 

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

0 votes
0 votes
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}$
edited by

Related questions

24 votes
24 votes
2 answers
1
makhdoom ghaya asked Nov 14, 2016
3,086 views
How many true inclusion relations are there of the form $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
22 votes
22 votes
4 answers
2
makhdoom ghaya asked Nov 9, 2016
5,420 views
State whether the following statements are TRUE or FALSE:The union of two equivalence relations is also an equivalence relation.
3 votes
3 votes
1 answer
3
23 votes
23 votes
3 answers
4
makhdoom ghaya asked Nov 14, 2016
4,238 views
How many one-to-one functions are there from a set $A$ with $n$ elements onto itself?