6
$\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$
10
$\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$
  • $\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$ – bof Feb 28 '17 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$ – Daniel R. Collins Nov 11 '18 at 3:03
1
$\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$
0
$\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$
  • $\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$ – Sam Farjamirad Jul 9 '18 at 17:08
  • $\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$ – Lauren Arvanitis Jul 26 '18 at 17:33
  • $\begingroup$ More briefly, transitivity is a "for all" statement, and when there are no relations, then it is vacuously true. $\endgroup$ – Daniel R. Collins Nov 11 '18 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.