8
$\begingroup$

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$?

$\endgroup$

4 Answers 4

Reset to default
11
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ 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)\}.$ $\endgroup$ Commented Feb 28, 2017 at 8:48
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Nov 11, 2018 at 3:03
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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 :)

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Jul 9, 2018 at 17:08
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Jul 26, 2018 at 17:33
  • $\begingroup$ More briefly, transitivity is a "for all" statement, and when there are no relations, then it is vacuously true. $\endgroup$ Commented Nov 11, 2018 at 3:09
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.