Well-formed Formula

Question

Prove that any expression (for propositional logic) with more left parentheses than right parentheses is not a well-formed formula.

My thoughts: Whenever problem states "any expression", I become very suspicious on how is it possible to prove this claim. It would be strongly welcomed to know your ideas on proof of this task.

Note: Well-Formed Formulas of Predicate Logic 1) Atomic formulas are wffs. 2) If α and β are wffs, then so are (¬α), (α ∧ β ), (α ∨ β ) and (α → β). 3) If x is a variable and α is a wff, then (∀x)α and (∃x)α are wffs.

Answer 1

Note that the contrapositive of the statement we want to prove is:

A well-formed formula does not have more left parentheses than right parentheses.

The definition of well-formed formulas has a recursive structure, which lends itself to an inductive approach to such proofs. Indeed we will prove the slightly stronger result that the number of left parentheses is equal to the number of right parentheses in any well-formed formula.

The basis step in our induction follows the way the wffs are defined recursively beginning with "atomic formulas":

1. Atomic formulas are wffs.

In the propositional logic the atomic formulas are propositional variables, typically represented by letters, but technically we want an inexhaustible supply, so formally a logical language will have infinitely many propositional variables available.

However the crux of whatever language is used is that the propositional variables contain no parentheses, so zero left parentheses equals the count of zero right parentheses. And that establishes the basis step.

Now for the induction step. The propositional logic gives us these operations to build up simpler formulas into more complicated ones:

2. If $α$ and $β$ are wffs, then so are $(¬α)$, $(α ∧ β)$, $(α ∨ β)$ and $(α → β)$.

The induction hypothesis is that separately the wffs $\alpha$ and $\beta$ each have an equal number of left and right parentheses. Because each of the "production rules" shown under (2) introduce exactly one left parenthesis and one right parenthesis, the new well-formed formulas generated by these rules will also have an equal number of left and right parentheses.

And that completes the induction step, showing that wffs always have an equal number of left parentheses as right parentheses.