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.