Transitivity on a set is defined as follows $$\forall x \forall y\forall z( T(x,y) \land T(y,z) \rightarrow T(x,z))$$ Now if we wanted to count total number transitive relations which are defined on an arbitrary set, then we don't have a closed-form expression to do so. The sequence is given here https://oeis.org/A006905

My question is whether you know of any non-trivial expression, which requires at least three variables and one binary predicate and only uses universal quantifiers to be expressed (i.e requires $\mathrm{FO}_3$ with one binary predicate and only universal quantifiers), which has a closed-form counting expression. i.e a generator function that takes the cardinality of domain elements and maps them to the model count of the $\mathrm{FO}_3$ expression.

Through this investigation, I want to understand if there is a link between the countability of a certain process with its expressibility in first-order logic.

Example of what it means that a closed-form counting expression exists. $$\forall_x\forall_y \mathsf{Smokes}(x) \land \mathsf{Friend}(x,y) \rightarrow S(y)$$ If we have $n$ individuals, then the number of models of this expression is given below. Notice this entire expression is expressed in $\mathrm{FO}_2$ $$a(n) = (3^{n}+4^{n})^{n}$$ Source: https://www.ijcai.org/Proceedings/16/Papers/607.pdf

  • $\begingroup$ Also asked at CSThE. $\endgroup$ Mar 28, 2020 at 2:01
  • $\begingroup$ What is FO3/FO2/FOL/F03/F02? doesn't occur in the linked paper. $\endgroup$
    – YCor
    Mar 28, 2020 at 8:25
  • 1
    $\begingroup$ @YCor $\mathrm{FO}_k$ is the fragment of first-order logic consisting of formulas that use at most $k$ distinct variables. (They may be reused.) $\endgroup$ Mar 28, 2020 at 8:28
  • $\begingroup$ Alright, I found a simple answer. The number of equivalence relations on a set is given as $\sum_{k=0}^{n} S(n, k)$. But I would still appreciate interesting answers. Also, I would be happy to know if there is some theory that tells us whether a closed-form for a sequence would exist or not. $\endgroup$
    – SagarM
    Mar 28, 2020 at 15:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.