Proof that WFFs with indistinguishable parentheses have unique decomposition/readability
(Credit to GitGud, ProofWiki)
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.
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.
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.
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.