Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Does anyone know an example of a mathematically interesting first order theory $T$ such that the following conditions hold?

  1. $T$ can be formalized in the classical predicate calculus.
  2. It is provable in ZFC that $T$ is consistent and has no infinite models.
  3. No upper bound is presently known for the cardinal numbers of the finite models of $T$, even though it has been proved that these models cannot be arbitrarily large.
share|improve this question
    
Take any finite set of finite models of finite signature. The first order theory of that set is what you need (if and only if). –  Mark Sapir Oct 7 '11 at 22:24
    
@Mark: What about (3)? –  Emil Jeřábek Oct 7 '11 at 22:53
1  
Not overly interesting interesting, but one could encode some sort of open problem into the size of available models. For example, take sigma to be the sentence "there are at most BB(n) elements," where n is your favorite number and BB(n) is the nth busy beaver number. Obviously you could fit this to whatever natural numbers problem you like, but it's a bit contrived. –  Richard Rast Oct 7 '11 at 23:17
3  
What I wanted to say is that your question is about first order theories of finite sets of finite models. Condition (3) is equivalent to asking that the size of the set should be unknown. There are lots of examples. Say, Vinogradov proved that almost all natural numbers are sums of three primes. Consider the set of all natural numbers which are not sums of three primes. This set is finite but we do not know if it is empty. A "number" can be easily viewed as a model in an appropriate signature. So this is (or easily converts to) an example of your theory. –  Mark Sapir Oct 7 '11 at 23:28
    
Thanks for your answers. Using BB(n) may be just what is needed, provided that BB(n) was definable within the theory T. The closest resemlance to T that I could think of was to imagine a "theory" of simple "sporadic" groups before the discovery of the Monster. The only problem was that I do not know what axioms characterize "sporadic" groups and I do not know how to prove that there are no infinite "sporadic" groups. –  Garabed Gulbenkian Oct 10 '11 at 14:44
show 1 more comment

1 Answer 1

Really, this is just a comment, but it's way too long:

First, a quick observation: assuming your language is finite, every example must be finitely axiomatizable. (Although that finite axiomatization may not be known.)

I want to give two potentially interesting classes of examples: one having a Ramsey-theoretic flavor, and the other coming from complexity theory. I'm hampered by the fact that I don't really know anything about either subject, so what follows is purely speculative.


In model theory, often we want to construct models of a given theory with nice combinatorial patterns - e.g., with indiscernible sequences of a given order-type, etc. I don't know if this is true, but I suspect that in finite model theory, finite combinatorial patterns are also important. Now, suppose I'm given a theory $T$ and a Ramsey-type theorem "Every sufficiently large structure exhibits pattern $P$." Then the 'bad' models of $\varphi$ are bounded in size - and hence the class of them is axiomatized by a single formula $\varphi$, even if $T$ is not finitely axiomatizable - but no upper bound on this size need be known. Even if an upper bound is known, there is a good chance (Ramsey theory being what it is) that it is truly terrible.

Now, I suspect that these classes of models are interesting only insofar as they make finite model theory difficult, that is, such a class might be relevant for studying the finite model theory of the corresponding theory $T$ but I doubt they are particularly interesting on their own. However, I could be wrong. (I could also be wrong that anything like this is of interest in finite model theory.) Hopefully, someone who actually knows finite model theory will set me straight on this.


Now let me give a class of potential examples coming from complexity theory.

Let $X$ be a set in some 'large' complexity class, say $NEXPTIME$. Call a Turing machine (deterministic or non) $\Phi$ an $X$-guesser if $\Phi(n)=1$ implies $n\in X$; that is, $\Phi$ may not compute $X$, but it never gives false positives.

There may be a collection $\{\Phi_i: i\in\omega\}$ of particularly nice $X$-guessers with extremely small runtime; maybe these arise in trying to 'build $X$ from below' to get a better upper bound on the complexity of $X$. If so, then if $X$ is sufficiently natural and these runtimes really are sufficiently small, we can probably prove that each $\Phi_i$ outputs 1 only finitely many times. Then, for each $i$, the set $X_i=\{n: \Phi_i(n)=1\}$ is a finite set of natural numbers; but upper bounds for these may not be known.

What does this have to do with finite models? Well, take the case where $X\in NEXPTIME$. An old result of ??? shows that the sets of the form $\{n: \exists A\models\varphi (\vert A\vert=n)\}$ (called (finite) spectra) are precisely the sets in $NEXPTIME$. So, given this sequence of sets $X_i$, starting with a formula $\varphi$ corresponding to $X$ we get formulas $\varphi_i$ corresponding to $X_i$ for each $i$. At this point, it's in principle possible that the structure of these formulas can be attacked by finite model theory more efficiently than the sets $X_i$ can be attacked from complexity theory. (Although to the best of my knowledge, this sort of idea isn't nearly as effective as one would hope.) So this would potentially give an interesting sequence of examples of your phenomenon.

I'm sticking to sequences of examples, rather than individual examples, here because I can't imagine a single $X$-guesser with such small runtime being that interesting on its own. Admittedly, I'm also very dubious that any of this is interesting, but it passes my own 'smell' test at least for now.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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