Fast question - Number of binary relations on a $3$-element set

Question

I would like you to ask about counting set for $n = 3$. So, this should be $2^9=512$, am I right? In my set, there are:

• reflexive relation = $2^{n^2-n}=64$
• symmetric relation = $2^{(n^2+n)/2}=64$
• transitive relation = $171$
• antisymmetric relation = $2^n\cdot3^{(n^2-n)/2}=216$

Finally, when I add all this relations, I have $64+64+171+216=515$. So, why is the different? I would be grateful for help.

Answer 1

Your question has nothing to do with special properties of relations such as reflexive, symmetric, and so on. Instead, your question is about the general concept of a binary relation.

A binary relation on a set $X$ is, by definition, a subset of $X \times X$. To put it another way, a binary relation on $X$ is an element of the power set $\mathcal P(X \times X)$.

If a set $X$ has $m$ elements then the set $Y = X \times X$ had $n=m^2$ elements.

And if a set $Y$ has $n$ elements then its power set $\mathcal P(Y)$ has $2^n$ elements.

So, the number of binary relations on a set with $m$ elements is equal to $2^{m^2}$.

In your case where $m=4$ you get $$2^{4^2}=2^{16}=65536 $$

Answer 2

You left out:

• None of the above.

And you double counted for all the relations that are one or more of the above types.

The total number is $2^{3^2} = 2^9$ and to get that by type,(if you wanted to get them by type... but there is no reason you should) you'd have to use the inclusion exclusion principal:

Total number is: All the reflexive + all the symmetric + all the transitive + all the antisymmetric - all those that are both reflexive and symmetric - all the both reflexive and transitive - all the both reflexive and antisymmetric - all the both symmetric and transitive - all the both symmetric and antisymmetric - all the both transitive and antisymmetric + all that are reflexive symmetric and transitive + all that are reflexive symmetric and antisymmetric + all that are reflexive transitive and antisymmetric + all that are symmetric transitive and antisymmetric - those that are all four + those that are none of the four.

This would be very complicated to calculate and not all of the even have formulas for calculations.

But that will add to ALL OF THEM.

And the formula for all of them is $2^{n^2}$.

But that's why you didn't get the right answer: You weren't counting any of the relations that were none of those types and you were double counting the ones that were.

In actuality you had utterly no reason to count them by type.