Unique decomposition of wffs when left and right parentheses are indistinguishable

Question

I'm working through Enderton's book A Mathematical Introduction to Logic 2nd Edition for self study.

Section 1.3 Exercise 7

Suppose that left and right parentheses are indistinguishable. Thus, instead of (α∨(β∧γ)) we have

|α∨|β∧γ||. Do formulas still have unique decomposition?

He is referring to the wffs (well formed formulas) I think. I'm trying to understand either why it has a unique decomposition through a proof, or why it doesn't through a counterexample or proof. So far I have not been able to come up with a counterexample so I have tried to develop an algorithm.

1. The first parenthesis will be treated as a left parenthesis.

2. Scan for the next parenthesis.

   • If it is immediately preceded by a binary connective, then it is a left parenthesis.
   • If it is immediately preceded by a sentence symbol, it is a right parenthesis.
   • If it is immediately preceded by a parenthesis, it is the same type as the preceding parenthesis.

However, I am not sure how to prove if it is correct and I am now stuck.

Answer 1

Proof that WFFs with indistinguishable parentheses have unique decomposition/readability

(Credit to GitGud, ProofWiki)

Theorem 1

Let A be a WFF of propositional logic. Let S be an initial part of A. Then S is not a WFF of propositional logic.

Proof Let l(Q) denote the length of a string Q.

By definition, S is an initial part of A iff A=ST for some non-null string T.

Thus we note that l(S)<l(A).

Let A be a WFF such that l(A)=1

Then for an initial part S, l(S)<1=0.

That is, S must be the null string, which is not a WFF.

So the result holds for WFFs of length 1.

Now, we assume an induction hypothesis: that the result holds for all WFFs of length k or less.

Let A be a WFF such that l(A)=k+1.

Suppose D is an initial part of A which happens to be a WFF.

That is, A=DT where T is non-null.

There are two cases:

• A=¬B, where B is a WFF of length k. D is a WFF starting with ¬, so D=¬E where E is also a WFF. We remove the initial ¬ from A=DT to get B=ET. But then B is a WFF of length k which has E as an initial part which is itself a WFF. This contradicts the induction hypothesis. Therefore no initial part of A=¬B can be a WFF.

• A=|B∘C| where ∘ is one of the binary connectives. In this case, D is a WFF starting with |, so D=|E∗F| for some binary connective ∗ and some WFFs E and F. Thus B∘C|=E∗F|T. Both B and E are WFFs of length less than k+1. By the inductive hypothesis, then, neither B nor E can be an initial part of the other. But since both B and E start at the same place in A, they must be the same: B=E. Therefore B∘C|=B∗F|T. So ∘=∗ and C|=F|T. But then the WFF F is an initial part of the WFF C of length less than k+1. This contradicts our inductive hypothesis. Therefore no initial part of A=(B∘C) can be a WFF.

So no initial part of any WFF of length k+1 can be a WFF.

The result follows by strong induction.

Theorem 2

Each WFF of propositional logic which starts with a | or a negation sign has exactly one main connective.

Thus, on a higher level, there is only one way to interpret the semantics of a given WFF of propositional logic.

Proof There are two cases to consider.

Consider the case where A=|B∘C| for some WFFs B and C and some binary connective ∘.

Suppose also that A=|D∗E| where D and E are also WFFs, and ∗ is another binary connective.

The WFFs B and D are strings which both start in the same place, right after the first left | in A.

By Theorem 1, neither B nor D can be an initial part of the other.

Therefore B=D.

It follows that ∗=∘ and C=E.

Now consider the case where A=¬B.

The result follows directly from the definition of the main connective for a WFF of this form.

Hence the result. ■

Answer 2

The proof given in the answer(using strong induction on length) is fine, but one can also prove this using only structural induction: prove using structural induction that for $|| \text{wffs}$(Here $||\text{wffs}$ denotes the wffs constructed with indistinguishable parentheses) the following property holds for any $||\text{wff}$, $ \phi:$

• "No proper initial sub-segment of $\phi$ is a $||\text{wff}$ nor is $\phi$ the proper initial sub-segment of any $|| \text{wff}$."