Does a finite first-order theory which has a model always have a finite model?

Question

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)?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.