Section 1.3: 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
Suppose that we modify our definition of wff by omitting all right parentheses. Thus instead of we use . Show that we still have unique readability (i.e., each wff still has only one possible decomposition). Suggestion: These expressions have the same number of parentheses as connective symbols.
First observation, as suggested, is that any wff has the number of pairs of parentheses equal to the number of connective symbols. Let be the set of all sentence symbols, and be the set of wffs such that the statement is true. Then, all sentence symbols are in , as such wffs have neither parentheses nor connective symbols. If , then adds one pair of parentheses and one connective symbol to the expression , and adds one pair of parentheses and one connective symbol to the collection of parentheses and connective symbols found in both and . In either case, the statement is true for the resulting wff, and , hence, by the induction principle, .
Second observation is that every wff is either a sentence symbol or ends in a connective symbol followed by a sentence symbol followed by a series of right parentheses. Again, this is obviously true for sentence symbols, and then for and provided that it holds for and . Therefore, by the induction principle, we conclude that this is true for all wffs.
Given these observations, if we form our building rules without right parentheses, then every wff (according to the new definition) will satisfy two new properties as follows: a) the number of left parentheses is equal to the number of connective symbols, and b) each wff is either a sentence symbol or ends in a connective symbol followed by a sentence symbol.
Accordingly, we modify Lemma 13A and Lemma 13B: for any wff, the number of left parentheses equals the number of connective symbols, and for any proper initial segment of wff that is the initial sentence symbol or that ends in a connective symbol followed by a sentence symbol the number of left parentheses is greater than the number of connective symbols (of course, this also implies that a proper initial segment cannot be a sentence symbol). Indeed, this is true for sentence symbols, and if this is true for and , then this is true for with such proper initial segments being and and for with such proper initial segments being , , and .
Now, we modify the parsing algorithm accordingly. Namely, the last two steps are modified as follows. If the sub-expression being parsed is , then we form a new leaf below it with the value (note, that we do not need to check the right parenthesis here, as there are no, and that we exclude for the expression exactly one left parenthesis and one connective symbol from the very left of the expression, so that if our lemmas hold for , they hold for ). If the sub-expression being parsed is such that does not start with , then either starts with a sentence symbol , in which case we set , or we scan from the left all segments of ending in a connective symbol followed by a sentence symbol until we find an initial segment such that has exactly the same number of left parentheses and connective symbols. Then, as before, must be followed by a binary connective symbol, i.e. there must by an expression (otherwise the algorithm halts), which forms two leaves with values and . Similarly to the arguments in the text, the choice of here is uniquely determined, as anything less does not have equal numbers of left parentheses and connectives, but anything bigger would have as a proper initial segment either being a sentence symbol or ending in a connective symbol followed by a sentence symbol with equal numbers of left parentheses and connective symbols.
As an example, let as consider the expression given in the problem, . First parsing gives . Note that does not work as is not followed by a sentence symbol, so that we do not even consider the substring . Hence, we have two leaves, and connected by . Scanning of the first one gives two new leaves and , and the latter gives another leaf , while scanning of the second one gives two leaves and . This is the same tree, as we would have obtained using the textbook parsing algorithm on .