Section 1.1: Problem 5 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
Suppose that is a wff not containing the negation symbol .
(a) Show that the length of (i.e., the number of symbols in the string) is odd.
(b) Show that more than a quarter of the symbols are sentence symbols.
Suggestion: Apply induction to show that the length is of the form and the number of sentence symbols is .
(a), (b). As suggested, we note that all single sentence symbol formulas have symbols, where , at the same time having sentence symbols. Suppose, that two wffs and have lengths and , and and sentence symbols, correspondingly. Then has length and sentence symbols. Hence, by induction, any construction sequence leading to a well-formed formula that does not contain the negation symbol, ends up at an expression having length with sentence symbols.