Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm curious whether this is true or not:

Let T be a finite, first-order theory. If T has a model, then T has a finite model.

I would assume the answer is 'yes', but I wanted to make sure I haven't missed something obvious. The reason I believe this to be the case is that according to my understanding of the Lowenheim-Skolem theorem, the only way a countable first-order theory can 'force' a size onto its potential models is by including a countable number of constants which the model must have representations for. Therefore, if the theory is finite, then the number of constants it can 'force' to exist must also be finite, thereby ensuring the existence of a finite model (assuming any model can exist at all). Is anything wrong with my reasoning (apart from its relative informality)?

share|cite|improve this question
up vote 15 down vote accepted

Noah and Brian have given one of the canonical examples of a finitely axiomatizable theory with no finite model (their examples are essentially the same). I'll give the other - it shows that this behavior is possible even in a relational language without definable functions, so thinking about constant symbols and terms is a red herring (unless you think about Skolemization, as Noah says).

Let $L$ be the language consisting of a single binary relation symbol $\leq$, and let $T$ be the theory asserting that $\leq$ is a non-empty linear order with no greatest element. That is, $T$ contains the three linear order axioms, together with the sentences $\forall x\, \exists y\, (x\leq y\land \lnot (x = y))$ and $\exists x\, x = x$ (to rule out the empty structure, if your semantics for first-order logic allows it).


So it's not true that every finitely axiomatizable theory has a finite model. In fact, the problem of determining whether a given theory has a finite model is undecidable in general. This is known as Trakhtenbrot's theorem.

Time for a tangent: If your guess were correct, and every finitely axiomatizable first-order theory had a finite model, then in fact the decision problem for first-order logic would be decidable. That is, one could write a computer program that takes as input a first-order sentence $\varphi$ and outputs "yes" or "no" according to whether $\varphi$ has a model. This program would start enumerating the finite $L$-structures and checking whether they are models of $\varphi$, while simultaneously searching for proofs of $\lnot \varphi$. If $\varphi$ has no model, a proof of $\lnot\varphi$ will eventually be found (by the completeness theorem), while if $\varphi$ has a model, a finite model will eventually be found.

Of course, the decision problem for first-order logic is well-known to be undecidable. But there are classes of first-order sentences (e.g. in a relational language the universal sentences $\forall \overline{x}\, \varphi(\overline{x})$ with $\varphi$ quantifier-free) which do have the finite model property (if they have a model, then they have a finite model) and hence these classes are decidable by the argument above.

share|cite|improve this answer
4  
Note that this is a really different example than the one Brian and I give - in this example, there are no terms or even (nontrivial) definable functions! Here is one case where you really need to look at the Skolemized language for the infinitely many constants to appear. (Also +1 for Trakhtenbrot.) – Noah Schweber Jan 26 at 1:56
    
Pedantic quibble: Also insert the axiom $\exists x$, so that the empty order is not a model of your theory. – David Speyer Jan 26 at 19:12
    
@DavidSpeyer Standard semantics for first-order logic does not allow empty structures. – Noah Schweber Jan 26 at 19:16
1  
@DavidSpeyer: Just because it isn't your preference doesn't mean that disallowing empty models is dumb. It may look like it works fine in model theory, but it greatly complicates logic and proof theory. As an aside: I have never encountered a logician who use the terms true or false of formulas with free variables (and have been grateful to logicians who have carefully helped me to correct my misuse of those terms). – Rob Arthan Jan 31 at 0:06
1  
@RobArthan If you have a strong argument for banning empty models, I'd encourage you to put it over on math.stackexchange.com/questions/45198 ; the answers there, including one by JDH, suggest that this is very much a technicality where you could go either way. – David Speyer Jan 31 at 1:06

No, this is incorrect. In the language consisting of a single unary function symbol $f$, consider the following statements about $f$:

  • $f$ is injective.

  • $f$ is not surjective.

It is a good exercise to show that these can be written as first-order sentences; but any model of the conjunction of these sentences must be infinite.


The point is that the "constants" you mention are not just things named by constant symbols, but also terms (actually, even broader than this - constant symbols in the larger, "Skolemized" language - but for now it's enough to consider terms). Even a finite language can have infinitely many terms.

share|cite|improve this answer

Take a theory with one unary function symbol $f$, one constant symbol $a$, and axioms

$$\begin{align*} &\forall x\Big(\big(\exists y\big(f(y)=x\big)\leftrightarrow x\ne a\Big)\;,\text{ and}\\ &\forall x\,\forall y\big(f(x)=f(y)\to x=y\big)\;. \end{align*}$$

For intuition, think of $\Bbb N$, $0$, and the successor function.

share|cite|improve this answer
    
@Noah: I wanted to emphasize the point, but it’s probably more confusing that way, so I’ll delete that clause. – Brian M. Scott Jan 26 at 1:51

Let the language contain a single binary predicate symbol, to be interpreted as "less than."

Consider the theory $T$ with the following axioms:

1) There are at least two objects.

2) The relation $L$ is a strict total order.

3) For any $x$ and $y$ such that $L(x,y)$, there exists a $t$ such that $L(x,t)$ and $L(t,y)$.

Then all models of $T$ are infinite. This is the theory of dense linear order. It has nice model-theoretic properties. Cantor proved that any countable densely ordered set with no first or last element is order-isomorphic to the rationals under the usual order. Similarly, a countable densely ordered set with first element and no last is order isomorphic to the rationals in $[0,1)$, with similar results for the other two possibilities.

share|cite|improve this answer
    
Or more simply, the theory of a linear order with no greatest element. – bof Jan 26 at 2:09
2  
I like dense linear order because the Cantor proof is the genesis of back-and-forth arguments, and because completeness, decidability have simple proofs. – André Nicolas Jan 26 at 2:12
    
Is there something missing from the axioms for Cantor's result to hold? Because $<$ on $\Bbb Q \cap [0,1]$ satisfies all the axioms, but is not order-isomorphic to $\Bbb Q$. – Paul Sinclair Jan 26 at 14:22
    
@PaulSinclair: Thank you, somehow I left out the no first or last condition. Have edited. – André Nicolas Jan 26 at 16:39

All the examples so far make use of the equality symbol $=$. In some areas of logic (broadly construed) one often considers first-order languages without the equality symbol that's always interpreted as the true equality. But one can construct a finite theory $T_0$ that doesn't mention equality such that $T_0$ does not have a finite model.

Take $T$ as in one of the other answers. Then let $T_0$ be the theory obtained by:

  1. replacing each $=$ by $\equiv$, a new symbol
  2. adding the sentences that says $\equiv$ is an equivalent relation and
  3. for each other symbol occurring in $T$ (there are finitely many of them), adding the sentence that says the symbol is compatible with (the equivalence relation) $\equiv$.

Suppose $T_0$ had a finite model $M$. Then the quotient $M/\equiv^M$ of $M$ by the interpretation of $\equiv$ is a model of the original theory $T$. But $M/\equiv^M$ is also finite, a contradiction.

share|cite|improve this answer

Here's a very simple example, which requires only one binary relation and equality.

A binary relation can be seen as the edge relation of a graph, so take the theory of the sentence "there is exactly one vertex of degree exactly one, and every other vertex has degree exactly two".

There is a model: you put one vertex of degree one, that you need to connect to a vertex of degree 2, which must be connected to a vertex of degree two, etc. Then you can easily check that there is no finite model to this theory.

share|cite|improve this answer
    
This is basically identical to Brian's answer. (Specifically, it's a reduct: Given the theory $T$ that Brian describes, we can define a relation $E$ as "$E(x, y)$ iff $f(x)=y$ or $f(y)=x$." The resulting structure is a model of the theory you describe. Note that you can't go the other way around: any model of Brian's example reduces in a natural way to a model of your example, whereas given a model of your example there can be many ways to interpret it as a model of Brian's example.) – Noah Schweber Jan 29 at 22:18
    
@NoahSchweber Yes, I posted this answer just to emphasize that you don't need functions symbols and still have a very short description for the theory. – Graffitics Jan 29 at 22:25

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.