1

Section 1.3, A Parsing Algorithm, presents an algorithm that given a wff, will produce its "ancestral tree". That is, a tree whose root is the complete wff, each leave is a sentence symbol, and each other node is an application of a connective symbol $\neg,\wedge,\vee,\to$, or $\leftrightarrow$ to one or two nodes (its children). This is how the relevant parts go:

  1. If all minimal vertices (the ones at the bottom) have sentence symbols, then the procedure is completed. (The given expression is indeed a wff, and we have constructed its tree.) Otherwise, select a minimal vertex having an expression that is not a sentence symbol. We examine that expression.
  2. The first symbol must be $($. If the second symbol is the negation symbol, jump to step 4. Otherwise, go on to step 3.
  3. Scan the expression from the left until first reaching $(\alpha$, where $\alpha$ is a nonempty expression having a balance between left and right parentheses. Then $\alpha$ is the first of the two constituents. The next symbol must be $\wedge$, $\vee$, $\to$, or $\leftrightarrow$. This is the principal connective. The remainder of the expression, $\beta)$, must consist of an expression $\beta$ and a right parenthesis. We extend the tree by creating two new vertices below the present one, with $\alpha$ as the expression at the “left child” vertex, and $\beta$ as the expression at the “right child” vertex. Return to step 1.
  4. ...

Enderton then gives "comments in support of the correctness" of the algorithm. In particular, he says the following:

Secondly, the choices made by the procedure could not have been made differently. For example, in step 3 we arrive at an expression $\alpha$. We could not use less than $\alpha$ for a constituent, because it would not have a balance between left and right parentheses (as required by Lemma 13A). We could not use more than $\alpha$, because that would have the proper initial segment $\alpha$ that was balanced (violating Lemma 13B). Thus $\alpha$ is forced upon us. And then the choice of the principal connective is inevitable. We conclude that this algorithm constructs the only possible tree for the given expression.

The first assertion about the impossibility of taking less than $\alpha$ is clear, although I reason that Lemma 13B is the one that guarantees it (any proper initial sequence of a wff has more left parenthesis than right parenthesis).

The second assertion is where the real confusion comes from. "We could not use more than $\alpha$, because that would have the proper initial segment $\alpha$ that was balanced (violating Lemma 13B)." What does "taking more than $\alpha$" have anything to do with a proper initial sequence of $\alpha$? Is he just recycling symbols in a confusing way? I can see intuitively why the algorithm works, but I don't see how this admittedly informal argument supports it.

MuchToLearn
  • 323
  • If you take more than $\alpha$, then $\alpha$ is a proper initial segment of what you took. Since $\alpha$ has equal numbers of left and right parentheses, and since proper initial segments of formulas never have equal numbers of left and right parentheses, $\alpha$ cannot be a proper initial segment of a formula. Thus, what you took is not a formula. – Andreas Blass Jan 05 '18 at 01:27
  • Ah! I see what you mean. Thanks a lot! – MuchToLearn Jan 05 '18 at 02:39

1 Answers1

0

After a comment from Andreas Blass, it makes a lot of sense. I made the mistake of forgetting everything that was true prior to a claim and failed to see the connection as a result. An alternative, more explicit reading of that paragraph could be the following.

Secondly, the choices made by the procedure could not have been made differently. At the start of step 3, the expression must be of the form $(\gamma\square\delta)$ if it is to be a wff, where $\gamma$ and $\delta$ are wffs themselves (called the left and right constituents, respectively). Hence we could not use less than $\alpha$ (i.e. the first balanced expression) for the left constituent because Lemma 13A requires it. Furthermore, $\alpha$ must make up the entirety of the left constituent (in other words, $\alpha = \gamma$) or it would be a proper initial segment of $\gamma$ that was balanced, contradicting Lemma 13B. Thus $\alpha$ is forced upon us. And then the choice of the principal connective is inevitable. We conclude that this algorithm constructs the only possible tree for the given expression.

MuchToLearn
  • 323