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