The class of all finite structures is not $EC_\Delta$ (Enderton’s Corrolary 26B)

first-order-logiclogicmodel-theory

I am reading Enderton's book, A mathematical introduction to logic, beggining of the section $2.6$. I have two following question (page 147).

First question

He says that some sentences have only infinite models and the negation of such a sentence is true in every finite structure.

  • Is it there any proof of this statement? Or, what is the intuition behind this statement?

Second question

(Theorem 26A) If a set $\Sigma$ of sentences has arbitrarily large finite models, then it has an infinite model.

For a set $\Sigma$ of sentences, let $\text{Mod } \Sigma$ be the class of all models of $\Sigma$.

A class $K$ of structures for our language is an elementary class (EC) iff $K = \text{Mod } \tau$ for some sentence $\tau$.

A class $K$ of structures for our language is an elementary class in the wider sence ($EC_\Delta$) iff $K = \text{Mod } \Sigma$ for some set $\Sigma$ of sentences.

(Corollary 26B)

  1. The class of all finite structures (for a fixed language) is not $EC_\Delta$.
  2. The class of all infinite structures is not $EC$.

Proof: 1) follows immediately from theorem 26A.
2) […]

We consider some fixed language and the class $K$ of all finite structure of the language (i.e., all structure of the language such that the domain of the structure is finite). By the definition we need to show that there is no set $\Sigma$ of sentences such that $K = \text{Mod }\Sigma$.

How can apply Theorem 26A to prove this part of the corollary?

Best Answer

For the first question, the point is that there are basic algebraic/combinatorial phenomena which can only occur in infinite structures. The simplest example is an injective non-surjective function: in the language with a unary function symbol $f$, the sentence $$[\forall x, y(x\not=y\implies f(x)\not=f(y))]\wedge[\exists x\forall y(f(y)\not=x)]$$ does have models but does not have any finite models. Another easy example is linear orders without endpoints: in the language with a binary relation symbol $R$, the sentence asserting that $R$ is a linear order with no greatest (or least, if you prefer) element has only infinite models.

(There are also surprisingly deep examples, e.g. Wedderburn's little theorem says that the sentence saying "the universe is a non-commutative division ring" has only infinite models.)

For the second question, this is just a direct application of the theorem. Let $\mathbb{K}$ be the class of all finite structures (in some fixed language). If $\mathbb{K}$ were $EC_\Delta$, then there would be some set of sentences $\Gamma$ such that $\mathbb{K}$ is exactly the class of all models of $\Gamma$. But:

  • Do you see why such a $\Gamma$ must have arbitrarily large finite models? (HINT: how large can elements of $\mathbb{K}$ be?)

  • Do you see why such a $\Gamma$ cannot have infinite models? (HINT: how large can elements of $\mathbb{K}$ not be?)

This gives a contradiction, so our assumption that $\mathbb{K}$ was $EC_\Delta$ must have been wrong.

Related Question