0

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\to\}$ and $\textit{propositional symbols}=\{A_n\mid n\in\mathbb{N}\}$ for $n \in \mathbb{N}$ satisfying the following properties:

(1) For each propositional symbol $A_n$ with $n\in\mathbb{N}$, \begin{multline} A_n \in L. \end{multline}

(2) For each pair of finite sequences $s$ and $t$, if $s$ and $t$ belong to $L$, then \begin{multline} (\neg s) \in L \end{multline} and \begin{multline} (s \to t) \in L. \end{multline}

Let $\Psi$ be the property that a formula has the same number of left and right parenthesis.

basis step: Let $A$ be a prop symbol. $\Psi(A)$ holds since there are no parenthesis.

inductive step Let $A$ and $B$ be formulas. $\Psi((\neg A))$ holds since $A$ has the same number of parenthesis, and we are only adding one left and one right with negation, so they remain equal. $\Psi((A\to B))$ holds as well, since $A$ and $B$ both hold, they have an equal number of left and right parenthesis for themselves. So $(A\to B)$ simply adds one left and one right, so we see in fact $\Psi((A\to B))$ holds.

Therefore $\Psi$ holds for all formulas by induction on formulas.

What else can we prove with this induction?

Michael Hardy
  • 1
Kevin Carroll
  • 252

1 Answers1

1

Here are a few, probably in order of increasing difficulty:

  1. In every formula the total number of connectives ($\neg$ and $\to$) is equal to the number of left (or right) parentheses.

  2. In every formula the number of (not necessarily distinct) propositional symbols is at least one more than the number of instance of $\to$.

  3. Every formula has the following property: if you start a counter at $0$ and read the formula from left to right, adding $1$ for each left parenthesis, subtracting $1$ for each right parenthesis, and doing nothing for each connective, your counter will finish at $0$ and will be positive at every intermediate stage.

Brian M. Scott
  • 616,228
  • You can make the proof that all wffs have the same number of L and R parenthesis very useful by on top of that proving that any proper initial segment of a wff has more L parenthesis than R. This allows you to conclude that no proper initial segment can be a wff. – Kevin Carroll Oct 21 '14 at 20:41
  • 1
    @Kevin: That’s essentially part of (3) (‘positive at every intermediate stage’). – Brian M. Scott Oct 21 '14 at 20:43