# Section 2.6: Problem 9 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Say that a set $\Sigma$ of sentences has the finite model property iff each member $\sigma$ of $\Sigma$ , if it has any models at all, has a finite model. Assume that $\Sigma$ is a set of sentences in a finite language (i.e., a language with finitely many parameters) and that $\Sigma$ has the finite model property. Give an effective procedure that, given any member $\sigma$ of $\Sigma$ , will decide whether or not $\sigma$ has any models. Suggestion: Is the set of such sentences effectively enumerable? Is its complement effectively enumerable?
$\Sigma=F\cup I$ where $F$ consists of sentences of $\Sigma$ having a finite model, and $I$ consists of sentences of $\Sigma$ not having a model at all. For a given $\sigma\in\Sigma$ we need to effectively decide whether $\sigma\in F$ or $\sigma\in I$ . $F\subseteq\Delta=\{\tau|\tau\mbox{ has a finite model}\}$ , and $\Delta$ is effectively enumerable by Theorem 26D. $I\subseteq K=\{\sigma|\sigma\mbox{ has no model}\}$ , and $K$ is effectively enumerable by the Enumerability Theorem (p. 142), as $\sigma\in K$ iff $\neg\sigma$ is valid. Therefore, the procedure may look as follows: we list members of both $\Delta$ and $K$ one by one and check whether $\sigma$ is in one of them (Theorem 17F, and Exercise 8 of Section 1.7).