Section 2.6: Problem 6 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
Prove the converse to part (a) of Corollary 26I: An effectively enumerable theory (in a reasonable language) is axiomatizable. Suggestion: The set
is equivalent (in the sense of having the same models) to the set
.
Consider an effectively enumerable theory
. Now,
iff
. And there is a procedure that can construct a sequence
of all sentences in
.
is a set of axioms of
, and it is effectively enumerable, but we need a decidable set of axioms. As suggested, consider the set of axioms
.
is a model of
iff it is a model of
(which is quite straightforward to see). But now,
is decidable. Indeed, having an input sentence
(if it is not a sentence, we reject it), we just check the length of
, and see, if there is a sentence in
having the same length as
by generating a necessary number of sentences (every next sentence in
has the length larger than the previous one), and if there is one, we check whether it is
or not.