# 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
of sentences has the

*finite model property*iff each member of , if it has any models at all, has a finite model. Assume that is a set of sentences in a finite language (i.e., a language with finitely many parameters) and that has the finite model property. Give an effective procedure that, given any member of , will decide whether or not has any models.*Suggestion*: Is the set of such sentences effectively enumerable? Is its complement effectively enumerable?
where
consists of sentences of
having a finite model, and
consists of sentences of
not having a model at all. For a given
we need to effectively decide whether
or
.
, and
is effectively enumerable by Theorem 26D.
, and
is effectively enumerable by the Enumerability Theorem (p. 142), as
iff
is valid. Therefore, the procedure may look as follows: we list members of both
and
one by one and check whether
is in one of them (Theorem 17F, and Exercise 8 of Section 1.7).