Section 1.3: Problem 7 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 left and right parentheses are indistinguishable. Thus, instead of
we have
. Do formulas still have unique decomposition?
It seems that we can always distinguish which parentheses are left and which are right. Indeed, left and right parentheses cannot go together, as neither
nor
is possible (this could be easily verified by the induction principle). Hence, we have groups of same parentheses going together. Further,
always indicates the beginning of a subformula, while
always indicates the ending of a subformula. The beginning of a formula that is not a sentence symbol may start with
,
or
while the ending of the formula can be one of
,
. Moreover, none of the following is possible:
,
,
,
, which is also verified by the induction principle easily. Hence, by taking each group of consequent indistinguishable parentheses we can uniquely determine whether they are all left parentheses, or right parentheses, or there is a syntax error in the expression if we see something like
,
etc.
For example, in the expression
there are three groups of parentheses, where the first and second must be
, as they both are followed by sentence symbols, while the third group must consist of
, as it follows a sentence symbol. The example of Exercise 4 would look like
where the first and forth groups of parentheses are
(followed by sentence symbols), the second group is also
(followed by
), while the third and fifth groups are
(both following sentence symbols).