# 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
.