Section 1.1: Problem 4 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
Assume we have a construction sequence ending in , where does not contain the symbol . Suppose we delete all the expressions in the construction sequence that contain . Show that the result is still a legal construction sequence.
Consider a construction sequence for formula , i.e. . Consider the last expression , that uses sentence symbol . Since, does not use it, . Moreover, for all , does not use , as cannot use it for , and for , does not use used in . Hence, if we remove step from the sequence, the sequence will remain well-formed, as nothing uses the expression obtained at this step. The resulting sequence is still a construction sequence for , since , but now it has one less expression using . Continuing this way, we can ensure that no expression in the sequence uses , while still the sequence is a construction sequence for the wff . Alternatively, we could use induction by the number of expressions in the sequence that use .