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