Finite Model Theory

Question

It seems that finite model theory is regarded (in a sense) as a computer theoretic subject. Is this the case or are there questions of interest that are of interest to mathematical logicians or more properly model theorist? And if so what would be a good place to learn about them?

Answer 1

As you're aware, the phrase "Finite Model Theory" usually refers to a field of math which has more to do with computer science than model theory. The books by Ebbinghaus and Flum, Libkin, etc. are good resources for this material.

Recently, however, some model theorists have been taking a stronger interest in the model theory of finite structures, especially where connections with the ideas of modern (post-Classification Theory) model theory are possible. A good example of this is Hrushovski's work on pseudo-finite dimensions, which started in his approximate subgroups paper and was fleshed out in this paper (behind a paywall, sorry). The idea is that the counting measure on a class of finite structures can be lifted to give notions of dimension and measure on models of the theory of their ultraproduct. This allows ideas from "geometric" model theory to be used in the context of pseudo-finite theories, and sometimes one can prove things in finite combinatorics by way of the pseudo-finite limit (see, for example, Tao's post on the algebraic regularity lemma, or, for the more general philosophy, "Ultraproducts as a Bridge Between Discrete and Continuous Analysis").

There is some very recent work by García, Macpherson, and Steinhorn (which I believe hasn't even been written up yet), using pseudo-finite dimensions to give sufficient conditions for stability, simplicity, supersimplicity, etc. of pseudo-finite theories.

Macpherson and Steinhorn have also worked on two contexts, called "asymptotic classes" and "robust classes", in which properties of a class of finite structures allow one to draw connections with the infinitary model theory of their limits. Here is a survey of these ideas.

You might be interested in the work of Cameron Hill, who has done a lot of work around super-simplicity and measurability of Fraïssé limits.

Regarding zero-one laws, certainly not everything is known. There is a nice survey (of the state of the art in 1989... well, it's a good place to start) by Kevin Compton called "0-1 Laws in Logic and Combinatorics" (paywall again, sigh).

Here's an example of a very interesting open zero-one law (it has to do with finitely presented structures, not finite structures, but it's still interesting!): Consider the random group model $G(n,r,l) = \langle x_1,\dots,x_n \mid w_1,\dots,w_r\rangle$, where $w_1,\dots,w_r$ are relations of length $l$ chosen uniformly at random from all reduced words of length $l$ in the generators $x_1,\dots,x_n$. Julia Knight conjectured that for any $n\geq 2$ and $r\geq 0$, in the limit as $l\rightarrow\infty$, 1. the $G(n,r,l)$ satisfy a zero-one law and 2. the almost-sure theory is the theory of the free group on $n$ generators. Both conjectures are open.

If you're interested in finite groups, you might also take a look at these mathoverflow questions: Is there a 0-1 law for the theory of groups? (and the linked math stackexchange question) and Density of first-order definable sets in a directed union of finite groups.

Something I'm very interested in is the phenomenon that in many interesting examples the zero-one law for a class of finite structures, when it exists, coincides with the theory of the Fraïssé limit of this class. Of course, there are examples where these theories both exist but differ, but sometimes this can be fixed by replacing the Fraïssé limit with a Hrushovski construction (see, for example, Baldwin and Shelah, "Randomness and semigenericity"). To my knowledge, there is no satisfying understanding of this phenomenon in general.

Doubtless there's much more to say, but this is already quite long, and I didn't intend to write a comprehensive survey. I hope some of these things pique your interest.

Answer 2

I seem to recall having heard that if $\varphi$ is a first order sentence, then the limit as $n\to\infty$ of the probability that $\varphi$ is true in models of size $n$ must be either $0$ or $1$. It seems to me that that might interest people other than computer scientists.