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?
Asked
Active
Viewed 67 times
0
-
1Do you really want all four properties at the same time? In that case, one might consider what it means to be both symmetric and anti-symmetric. If I'm not mistaken, this means you're dealing with a relation which is a subset of $=$, so you're basically counting the number of subsets of $A$. – HSN Oct 07 '13 at 13:56
-
@HSN But only some subsets, as he also wants reflexivity... – martini Oct 07 '13 at 13:59
1 Answers
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.
Nick Peterson
- 32,430