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