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.