# A countable expression expressible in $\mathrm{FO}_3$ with only one binary predicate?

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

• Also asked at CSThE. Mar 28, 2020 at 2:01
• What is FO3/FO2/FOL/F03/F02? doesn't occur in the linked paper.
– YCor
Mar 28, 2020 at 8:25
• @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.) Mar 28, 2020 at 8:28
• 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. Mar 28, 2020 at 15:26