# How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it?

For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but how to find only the transitive relations? Is there a formula for finding this or is it a counting problem?

Also how to find this for any number of elements $n$?

There is no simple formula for this number (but see http://oeis.org/A006905 for the values for small $n$). The case $n=2$ is small enough that you can list out all 16 different relations and count the ones that are transitive. (You should get 13 of them.)

• It's easier to just find the three nontransitive relations on $\{a,b\};$; they are $\{(a,b),(b,a)\}\cup S$ where $S$ is a proper subset of $\{(a,a),(b,b)\}.$
– bof
Commented Feb 28, 2017 at 8:48
• @bof: That's true for size $n = 2$ but not true for any sizes past that. E.g., for $n = 3$, only 33% are transitive; for $n = 4$, 6%; for $n = 5$, 0.5%; etc. Commented Nov 11, 2018 at 3:03

Although there's no formula, results for small $$n$$ can be obtained by recursion. This paper proves that, if there are $$T_n$$ transitive relations and $$P_n$$ partial orders on an $$n$$-element set, and if we define $$N_k\left( n\right):=\sum_{s=0}^k\binom{n}{s}S\left( n-s,\,k-s\right)$$ where $$S\left( n,\,k\right):=\frac{1}{k!}\sum_{i=1}^k\left( -1\right)^{k-i}\binom{n}{k}i^n$$, then $$T_n=\sum_{k=1}^n N_k\left( n\right)P_k$$. Unfortunately, $$P_n$$ is also only known for small $$n$$; we can't obtain further $$P_n$$ with any known recursion, which in turn caps computing $$T_n$$.

As noticed by @universalset, there are 13 transitive relations among a total of 16 relations on a set with cardinal 2. And here are they :)

• Could you please explain why for instance the first one (on the top left corner) is transitive? I don't see it, should be at least need three element to define transitivity?
– user427132
Commented Jul 9, 2018 at 17:08
• You can test transitivity using the definition of transitivity and a the truth table for the implies operator (→) A relation is transitive if, in simple terms, a is related to b, and b is related to c implies that a is related to c. aRb & bRc → aRc The '→' works as follows: | p | q | p→q | | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 | So to answer Sam Farjamirad's question, In a two node graph with NO connections: aRb = FALSE bRc == FALSE aRb→bRc = TRUE So it is transitive Commented Jul 26, 2018 at 17:33
• More briefly, transitivity is a "for all" statement, and when there are no relations, then it is vacuously true. Commented Nov 11, 2018 at 3:09

Counting transitive relations on a set is probably very hard. Just recently, in this paper of mine titled, "On the number of transitive relations on a set", I was able to find several recursive relations and lower bounds for the number of transitive relations on a set.