6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand what it means for a formula to have a unique decomposition. Can you please explain? $\endgroup$ – Git Gud Aug 6 '14 at 1:28
  • $\begingroup$ @GitGud: I think ignoramus is talking about 'unique readability'. $\endgroup$ – Kyle Aug 6 '14 at 1:30
  • $\begingroup$ @KyleGannon I see. Thanks. $\endgroup$ – Git Gud Aug 6 '14 at 1:39
  • 2
    $\begingroup$ OP, if this is the case, then you can just try to copy the proof for the usual unique readability theorem. Copy the proof from here to a text editor, use the replace function to replace ( and ) with | and you're done. $\endgroup$ – Git Gud Aug 6 '14 at 1:40
  • $\begingroup$ Shouldn't the expression be $|a \lor | \beta \land \gamma ||$? $\endgroup$ – copper.hat Aug 6 '14 at 2:39
3
$\begingroup$

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=|BC| where ∘ is one of the binary connectives. In this case, D is a WFF starting with |, so D=|EF| for some binary connective ∗ and some WFFs E and F. Thus BC|=EF|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. ■

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.