7
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ There are seevral recent books : Heinz-Dieter Ebbinghaus & Jörg Flum, Finite Model Theory (1999), Erich Gradel & Phokion Kolaitis & Leonid Libkin, Finite Model Theory and Its Applications (2007), Leonid Libkin, Elements of Finite Model Theory (2012). $\endgroup$ – Mauro ALLEGRANZA Apr 30 '14 at 21:16
  • 1
    $\begingroup$ Thank you. I have already started reading the book by Ebbinghaus & Flum. I was more interested in knowing where research interest lay (if there are any) for a model theorist. $\endgroup$ – UserB1234 Apr 30 '14 at 21:19
  • $\begingroup$ Are you interested in the model theory of modal logics by any chance? If yes, there are some applications of finite model theory in proving certain (in)definability results in modal logics. I'd check out Blackburn et al. Modal Logic for bits and pieces on that. There should be a more systematic treatment somewhere, but I haven't come across it yet. $\endgroup$ – Hunan Rostomyan Apr 30 '14 at 21:49
  • $\begingroup$ Kind of. I'm trying to figure out which one I want to delve in to deeper; fuzzy logic or finite model theory. $\endgroup$ – UserB1234 Apr 30 '14 at 21:51
7
$\begingroup$

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, especially this paper, which (among other things) addresses the question of when the theory of a Fraïssé limit is super-simple.

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.

$\endgroup$
1
  • $\begingroup$ They did pique my interest. This is what more or less what I was looking for. Thanks! $\endgroup$ – UserB1234 May 10 '14 at 22:57
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ There are some zero one laws that have already been proven. But I'm not sure if there are any open ones. $\endgroup$ – UserB1234 Apr 30 '14 at 21:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.