Proof of Compactness Theorem’s failure in finite models

110 Views Asked by At

I have a question on Jouko Väänänen’s proof on Compactness Theorem’s failure in finite model theory (FMT) in his “A Short Course on Finite Model Theory” in section 1.1 in page 5 at https://www.lacl.fr/~pvanier/cours/2015-2016/lm/articles/shortcoursefmt.pdf

In this proof, it says $T=\left\{\neg \phi_1, \neg \phi_2,\ldots, \neg\phi_n,\ldots\right\}$, which is infinite. But in the remark, it says $T=\left\{\neg c_n=c_m: n\neq m\right\}$ where $c_n$, $c_m$ are constants. Because it talks about Finite Models that has a finite domain/universe, therefore the number of constants have to be finite. Thus, $T$ is finite. It seems there are two definitions for theory $T$, and they are contradicting. Did I miss anything?

1

There are 1 best solutions below

4
On BEST ANSWER

You write

"Because it talks about Finite Models that has a finite domain/universe, therefore the number of constants have to be finite"

This isn't true: there's no rule that says that you can't have a language larger than the universe being looked at. Indeed, even in classical model theory there are interesting questions about uncountable languages and countable structures.

But if you want, you can whip up a finite-language counterexample: instead of infinitely many constants, use a single constant symbol $c$ and a unary function symbol $f$. We wind up looking at the theory $$\{\forall x,y(f(x)=f(y)\leftrightarrow x=y)\}\cup\{f(c)\not=c, f(f(c))\not=c, f(f(f(c)))\not=c,...\}.$$ Every finite subtheory of this theory has a finite model, but the whole theory does not have a finite model.