WFF of PropLog is Balanced
Theorem
Let $\mathbf A$ be a WFF of propositional logic.
Then $\mathbf A$ is a balanced string.
Proof
We will prove by strong induction on $n$ that:
Let $\map l {\mathbf A}$ denote the number of left brackets in a string $\mathbf A$.
Let $\map r {\mathbf A}$ denote the number of right brackets in a string $\mathbf A$.
Induction Basis
The only WFFs of PropLog of Length 1 are letters of the alphabet and the symbols $\bot$ and $\top$.
By definition, none of these consist of brackets.
So every WFF $\mathbf A$ of length $1$ has $\map l {\mathbf A} = \map r {\mathbf A} = 0$.
So every WFF of length $1$ is balanced.
This provides the induction basis.
Induction Hypothesis
Now, suppose all WFFs of propositional logic of length at most $n$ are balanced.
This provides the induction hypothesis.
Induction Step
Let $\mathbf A$ be a WFF of propositional logic of length $n + 1$.
The following cases are to be considered (with $\mathbf B$ and $\mathbf C$ WFFs):
- $\mathbf A = \neg \mathbf B$
- $\mathbf A = \paren {\mathbf B \circ \mathbf C}$, where $\circ$ is one of the binary connectives
Suppose $\mathbf A = \neg \mathbf B$.
Then $\mathbf B$ is a WFF of length $n$.
By the induction hypothesis, it is hence balanced.
Since $\mathbf A$ contains the same brackets as $\mathbf B$, it must also be balanced.
Suppose now $\mathbf A = \paren {\mathbf B \circ \mathbf C}$, where $\circ$ is one of the binary connectives.
Then:
- $\map l {\mathbf A} = \map l {\mathbf B} + \map l {\mathbf C} + 1$
- $\map r {\mathbf A} = \map r {\mathbf B} + \map r {\mathbf C} + 1$.
Now, $\mathbf B$ and $\mathbf C$ are both of length strictly less than $n + 1$, and thus balanced, by the induction hypothesis.
That is:
- $\map l {\mathbf B} = \map r {\mathbf B}$
- $\map l {\mathbf C} = \map r {\mathbf C}$
It follows that also:
- $\map l {\mathbf A} = \map r {\mathbf A}$
We also note that the first symbol of $\paren {\mathbf B \circ \mathbf C}$ is $($.
Hence as $\mathbf B$ and $\mathbf C$ are both balanced, every prefix of $\paren {\mathbf B \circ \mathbf C}$ must have strictly more left brackets than right brackets.
This precisely states that $\mathbf A$ is balanced.
We assumed that all WFFs of length $n$ and less are balanced.
We have proved as a consequence all WFFs of length $n + 1$ are balanced.
$\Box$
The result now follows by strong induction.
$\blacksquare$
Sources
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): $\S 1.3$: Induction on Length of Wffs: Proposition $1.3.1$