Section 2.6: Problem 11-A 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
(Additional) Assume that is a finitely axiomatizable theory (in a finite language). Assume that every sentence not in fails in some finite model of . Show that the theory is decidable.
We have where, in fact, . Then is effectively enumerable (Corollary 26I). The complement of consists of sentences that are false in some finite model of , but iff is a model of . Therefore, by Theorem 26C, for every finite model we can decide whether and are in , and if it is found that is in but is not, then . Given that we can effectively enumerate all finite models (in a finite language), we have a semi-decision procedure for the complement of as well.