Editing Transitive relation (section)

==Counting transitive relations==

No general formula that counts the number of transitive relations on a finite set {{OEIS|id=A006905}} is known.<ref>Steven R. Finch, [http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf "Transitive relations, topologies and partial orders"] {{Webarchive|url=https://web.archive.org/web/20160304111410/http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf |date=2016-03-04 }}, 2003.</ref> However, there is a formula for finding the number of relations that are simultaneously reflexive, symmetric, and transitive – in other words, [[equivalence relation]]s – {{OEIS|id=A000110}}, those that are symmetric and transitive, those that are symmetric, transitive, and antisymmetric, and those that are total, transitive, and antisymmetric. Pfeiffer<ref>Götz Pfeiffer, "[http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html Counting Transitive Relations] {{Webarchive|url=https://web.archive.org/web/20230204151143/https://cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html |date=2023-02-04 }}", ''Journal of Integer Sequences'', Vol. 7 (2004), Article 04.3.2.</ref> has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also Brinkmann and McKay (2005).<ref>Gunnar Brinkmann and Brendan D. McKay,"[http://cs.anu.edu.au/~bdm/papers/topologies.pdf Counting unlabelled topologies and transitive relations] {{Webarchive|url=https://web.archive.org/web/20050720092229/http://cs.anu.edu.au/~bdm/papers/topologies.pdf |date=2005-07-20 }}"</ref>

Since the reflexivization of any transitive relation is a [[preorder]], the number of transitive relations an on ''n''-element set is at most 2<sup>''n''</sup> time more than the number of preorders, thus it is asymptotically <math>2^{(1/4+o(1))n^2}</math> by results of Kleitman and Rothschild.<ref>{{citation|last1=Kleitman|first1=D.|last2=Rothschild|first2=B.|title=The number of finite topologies|journal=Proceedings of the American Mathematical Society|year=1970|volume=25|issue=2|pages=276–282|doi=10.1090/S0002-9939-1970-0253944-9 |jstor=2037205}}</ref>

{{number of relations}}