# How to count binary relations?

Printable View

• Sep 3rd 2009, 03:50 AM
kjey
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?
• Sep 3rd 2009, 04:48 AM
Plato
Quote:

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$.
• Sep 3rd 2009, 03:00 PM
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?

Thanks for the answer by the way (Nod)
• Sep 3rd 2009, 03:29 PM
Plato
Quote:

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|}$