8
$\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$ Apr 30, 2014 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, 2014 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$ Apr 30, 2014 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, 2014 at 21:51

2 Answers 2

9
$\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, 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.

$\endgroup$
6
  • $\begingroup$ They did pique my interest. This is what more or less what I was looking for. Thanks! $\endgroup$
    – UserB1234
    May 10, 2014 at 22:57
  • $\begingroup$ @AlexKruckman I couldn't find Hil's paper by clicking the link. I'm wondering if you can proved the link or the title of the paper. Thanks! $\endgroup$
    – Alice.H
    Jul 25, 2021 at 3:12
  • $\begingroup$ @Alice.H thanks for pointing out the dead link. I don't remember which paper of Cameron's I linked to when I wrote this answer, so I updated the link to his faculty research page. There's a lot of relevant work there, especially in the "submitted" section. $\endgroup$ Jul 25, 2021 at 3:24
  • $\begingroup$ @AlexKruckman Thank you! The new link doesn't work to me! $\endgroup$
    – Alice.H
    Jul 25, 2021 at 3:49
  • $\begingroup$ @Alice.H Haha I changed the text but forgot to change the link. Fixed now! $\endgroup$ Jul 25, 2021 at 11:41
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
  • 2
    $\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, 2014 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.