Discrete and combinatorial mathematics

Question

Suppose we have a relation on a set $A$, i.e. $A \times A$, where $|A| = n; \;n$ a positive integer. How can we count the number of relations on set $A$ which are reflexive, symmetric, transitive and anti-symmetric?

Answer 1

As HSN mentioned in a comment: if you want all four of these properties satisfied, then there isn't a lot to do: any relation which is both symmetric and antisymmetric is a subset of the "=" relation... if you further want it to be reflexive, then it can ONLY be the "=" relation, where $xRy$ if and only if $x=y$.

Now, if you're trying to count each property separately, then there's something you can do.

For instance: if you are trying to count all relations on $A$ which are reflexive, you are really trying to find the number of subsets of $A\times A$ such that the diagonal $\Delta:=\{(a,a)\mid a\in A\}$ satisfies $\Delta\subseteq R$. You have the freedom to decide whether or not any OTHER element of $A\times A$ is contained in $R$; so, there are $2^{n^2-n}$ such relations, since there are $n^2-n$ elements in $(A\times A)\setminus\Delta$.

You could also pretty easily count the number of symmetric relations: in symmetric relations, we either include both of $(a,b)$ and $(b,a)$, or neither, for all $a\neq b$; we also either include $(a,a)$ or don't. From elements of the type $(a,a)$, there are $2^n$ possibilities; for the rest, there are $2^{\binom{n}{2}}$. So, the total here is $2^{n+\binom{n}{2}}$.

And so on.