# Thread: How to count binary relations?

1. ## How to count binary relations?

Hello.

If I for example have a set $\displaystyle A=\{1,2,3\}$, I know that a binary relation on the set $\displaystyle A$ is any subset of $\displaystyle A \times A=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}$. (I hope I'm correct so far!) The problem however is how many different binary relations there is?

2. Originally Posted by kjey
The problem however is how many different binary relations there is?
If $\displaystyle A$ is a set and $\displaystyle |A|=n$ is the number of elements in $\displaystyle A$ then there are $\displaystyle 2^{n^2}$ binary relations on $\displaystyle A$.

3. But what if I have to find out how many of the relations that are for example reflexive? Is there an easy way to solve such problems?

Thanks for the answer by the way

4. Originally Posted by kjey
But what if I have to find out how many of the relations that are for example reflexive? Is there an easy way to solve such problems?
Yes there is. Any reflexive relation on $\displaystyle A$ contains the diagonal: $\displaystyle \Delta_A=\{(x,x):x\in A\}~\&~|\Delta_A|=|A|$.

Any reflexive relation corresponds to a relation that contains no 'diagonal' elements. So we get: $\displaystyle 2^{|A|^2-|A|}$