Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In counting the amount of relations on finite sets, we can quite easily count the amount of reflexive and symmetric relations on a finite set. We just consider (in accordance with the definition of a relation on a set as a subset of the cartesian product of the set with itself) a grid with on the vertical axis all the elements of the set and on the horizontal axis all elements of the set. We can then mark the points on the grid which are elements of the relation.

Consider a set $S$ with $|S|=n$ for some $n\in\mathbb{N}$.

The amount of relations on this set is simply $|\mathcal{P}(S^2)|=2^{|S^2|}=2^{n^2}$.

The amount of reflexive relations $S$ can be found by considering that these relations on the grid are all the relations in which in any case the diagonal is in the relation. We see that $n$ pairs are already "chosen", so we can still choose for $n^2-n$ pairs whether or not they are in the relation while keeping the relation reflexive. So there are $2^{n^2-n}$ reflexive relations on $S$.

For the amount of symmetric relations we know that the pairs under the diagonal are in the relation if the corresponding ones above the diagonal are also in the relation. We have the freedom to choose any of the pairs above or on the diagonal of the grid, the amount of which is equal to $T_n=\frac{n(n+1)}{2}$. So there are $2^{\frac{n(n+1)}{2}}$ symmetric relations on $S$.

Relations both symmetric and reflexive are relations for which we can freely choose any pair above the diagonal of the grid. There are $T_{n-1}=\frac{n(n-1)}{2}$ pairs above the diagonal, so there are $2^{\frac{n(n-1)}{2}}$ relations both symmetric and reflexive on $S$.

Now I'm sorry for not getting the point sooner and please correct me if I am wrong about any of them, but I am wondering if there are similar simple expressions for the amount of antisymmetric and transitive relations on this set $S$. I have been told before it is very difficult to visualise transitive relations with the grid I suggested. For antisymmetric relations I think it means the diagonal is definitely in the relation and either a pair above the diagonal is in the relation or the corresponding pair below the diagonal, but not both. I don't really have any ideas as to how I could use these things to come up with a formula for the amount of relations.

Any help and/or comments are appreciated.

Thank you

share|improve this question
3  
"amount" is used for unindividuated quantities, e.g. "the amount of damage" -- what you mean is "number". –  joriki Nov 24 '12 at 15:48
1  
I only just saw this. I see I have talked about an "amount" in a similar way as well in another question. I will try to be more careful and use "number" from now on. –  user50407 Nov 24 '12 at 20:27

1 Answer 1

up vote 1 down vote accepted

The number of antisymmetric relations is still relatively easy to find. I don't know why you say the diagonal has to be in the relation; the usual definition doesn't require this. Under the usual definition, the diagonal is unconstrained, yielding a factor $2^n$, and each off-diagonal pair has three possibilities, yielding a factor $3^{n(n-1)/2}$, for a total of $2^n3^{n(n-1)/2}$ antisymmetric relations. This is OEIS sequence A083667.

The number of transitive relations is indeed more difficult to determine. This is OEIS sequence A006905. The OEIS page cites this article, which obtains a recurrence relation by establishing a bijection with partial orders.

Quite generally, for this sort of sequence the best way to find what's known about it is to calculate the first few terms and use them to locate the sequence in OEIS.

share|improve this answer
    
OK, I will take a better look at antisymmetric relations and keep in mind for the future that OEIS will generally have the sequence I am looking for. Thank you. –  user50407 Nov 24 '12 at 16:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.