Section 1.7: Problem 13-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 an effectively enumerable set of expressions, and moreover that we have an effective procedure that lists exactly the members of
in such a way that each expression on the list is longer than the expressions occurring earlier on the list. Explain why
is decidable.
Having an input wff
(if the input expression is not a wff, we reject it), we just check the length of it, and run the procedure listing the members of
until there is a sentence having the same length as
, and if there is one, we check whether it is
or not.
Note. This is the idea used in Exercise 6 of Section 2.6.