Unique decomposition of wffs when left and right parentheses are indistinguishable 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.


*

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

*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.
 A: 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.
■
A: 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}$."
