6
$\begingroup$

Let $L$ be a finite relational language. Let $T$ be a complete theory with infinite models. If $T$ is an almost sure theory then it has the finite model property (in the sense that any model $M$ of $T$ has the property that if $M\models \varphi$, where $\varphi$ is an $L$ sentence, then there is some finite $L$ structure $A$ such that $A\models\varphi$). Also, I believe, if $T$ is $\forall\exists$-axiomatizable where the sentences use at most two variables then you again have the finite model property (This result can be found in chapter 4.1 of "finite model theory" by Ebbinghaus and Flum: http://www.springer.com/us/book/9783540287872).

What other conditions guarantee the finite model property? What would be a good reference to these results?

$\endgroup$
8
  • $\begingroup$ Why has this been down-voted? $\endgroup$ – user75685 May 17 '17 at 3:07
  • $\begingroup$ Don't know but what's an almost sure theory? $\endgroup$ – Bjørn Kjos-Hanssen May 17 '17 at 3:27
  • 4
    $\begingroup$ Theories with this property are also called "pseudofinite"; there are many papers on pseudofinite theories, though I don't recall any significant sufficient conditions off the top of my head. $\endgroup$ – Henry Towsner May 17 '17 at 4:19
  • 1
    $\begingroup$ I could see downvoting this to express that a responsible reference request should summarize the results in the obvious reference first, and that your not bothering to look in Ebbinghaus and Flum is correspondingly inappropriate. But I didn't vote: my own view is in that direction but milder. $\endgroup$ – Matt F. May 17 '17 at 6:02
  • 2
    $\begingroup$ It appears imperative to mention (especially since it is not in the arXiv reference given) a fundamental fact proved by Trakhtenbrot: there does not exist a fixed algorithm which would correctly decide for every (decidably-)given theory whether it has the finite model property. Sure, this is not strictly relevant to you request for sufficient conditions, but in some sense explains the complicatedness of this topic. $\endgroup$ – Peter Heinig May 17 '17 at 15:39
2
$\begingroup$

In my paper Disjoint $n$-amalgamation and pseudofinite countably categorical theories, I did some work on this question for the restricted class of countably categorical theories. (The question is already very hard for these theories! For example, the finite model property for the theory of the generic triangle-free graph is a famous open problem.)

A theory $T$ has disjoint $n$-amalgamation if, for any system of complete types $\{p_X((x_i)_{i\in X})\mid X\subsetneq [n]\}$ which agree on their intersections, there is a type $p_{[n]}((x_i)_{i\in [n]})$ extending all of them. For example, disjoint $3$-amalgamation means that whenever three $2$-types $p_{\{0,1\}}(x_0,x_1)$, $p_{\{0,2\}}(x_0,x_2)$, and $p_{\{1,2\}}(x_1,x_2)$ agree on their intersection $1$-types $p_0(x_0)$, $p_1(x_1)$, and $p_2(x_2)$, then there is a $3$-type $p_{\{0,1,2\}}(x_0,x_1,x_2)$ extending all three. This condition fails for the generic triangle-free graph, since you can't amalgamate three edges into a triangle.

I observed that if $T$ is countably categorical and has disjoint $n$-amalgamation for all $n$, then $T$ has the finite model property. The proof is by a probabilistic argument very similar to the usual proof of the finite model property for the theory of the random graph. This sufficient condition generalizes other sufficient conditions identified previously (see p. 9 of the linked paper), such as the parametric universal theories (Oberschelp), and local Fraïssé classes (Brooke-Taylor & Testa).

In my view, the really interesting thing is that all of the countably categorical theories which I know to have the finite model property have either a "structured/algebraic" flavor (think infinite-dimensional vector spaces over a finite field) or a "random/combinatorial" flavor (think the random graph). And every "combinatorial" example that I'm aware of can be explained by disjoint $n$-amalgamation, either directly (as in the random graph, for example) or indirectly by approximating the theory and taking finite expansions of the language (as in the theories $T^*_{feq}$ and $T_{CPZ}$ analyzed in the linked paper).

It would be very interesting to somehow make these ideas precise, but I haven't yet seen how to do it (again, it seems very hard: a successful realization of this goal would show that the theory of the generic triangle-free graph does not have the finite model property, since it is definitely "combinatorial", but it has a very strong obstruction to $3$-amalgamation). So instead I'll just leave you with two quotes:

“In all those homogeneous structures which I know to have the finite model property, [it] arises either from probabilistic arguments as above [i.e. 0-1 laws], or from stability, or conceivably from a mixture of these.” - Macpherson, A survey of homogeneous structures

“When does a homogeneous structure for a finite relational language have the finite model property? More broadly, is there anything of interest in graph theory besides randomness and algebra?” - Cherlin, Exercises for logicians (worth a read, if you haven't seen them before!)

$\endgroup$

Your Answer

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