I am working on an exercise from Mendelson's "Introduction to Mathematical Logic":
Define the following order of propositional connectives, from "strongest" to "weakest": $\neg$, $\land$,$\lor$, $\implies$, $\iff$. Polish notation requires us to write $\neg A$ for $(\neg A)$, $\land AB$ for $A\land B$, $\lor AB$ for $A\lor B$, $\implies AB$ for $A\implies B$, and $\iff AB$ for $A\iff B$. If we count $\land$, $\lor$, $\implies$, and $\iff$ as $+1$, and each statement letter as $-1$ (with $\neg$ as $0$), prove that $\mathscr{B}$ is a statement form if and only if $(1)$ The sum of the values of the statement letters and propositional connectives in $\mathscr{B}$ is $-1$, and $(2)$ The sum of the symbols in any proper initial segment of $\mathscr{B}$ is non-negative.
If $\mathscr{B}=\mathscr{C}\mathscr{D}$ and $\mathscr{C}\neq\mathscr{B}$, then $\mathscr{C}$ is a "proper initial segment". I'm confused about several points. Firstly, how is it that we are trying to prove every statement form has symbols summing to $-1$, yet each initial segment which is also a statement form should have a non-negative sum? I'm also not sure how to prove part $(1)$, because I don't know how to generalize a statement form in terms of letters and propositional connectives.
Here is my attempt at proving part $(1)$ in the $\implies$ case: Let $\mathscr{B}$ be a statement form containing letters $A_1,A_2,...,A_{n_1}$ (not necessarily distinct but appearing only once in $\mathscr{B}$), and propositional connectives $c_1,c_2,...,c_{n_2}$ (Again not necessarily distinct but appearing only once in $\mathscr{B}$). We use strong induction on $n_1$ to prove that $n_1=n_2+1$. If $n_1=1$, then $\mathscr{B}=A_1$ so $n_2=0=n_1-1$. Suppose that the statement holds for $n_1=1,2,3,...,k$, and let $\mathscr{B}_k$ be a statement form in $k$ letters. In order to include another letter, $A_{k+1}$ into $\mathscr{B}_k$, we can simply write $c_{k}A_{k+1}\mathscr{B}_k$, where $n_1=k+1=n_2+1$. Suppose that $\mathscr{B}_k=\mathscr{C}_1\mathscr{C}_2\dots\mathscr{C}_L$. Attaching $A_{k+1}$ to any sequence of statement forms $\mathscr{C}_i\dots\mathscr{C}_j$ where $1\leq i\leq j\leq L$ yields at most a statement form of $k$ letters (or $c_{k}A_{k+1}\mathscr{B}_k$ which is already accounted for), which by the inductive hypothesis satisfies $n_1=n_2+1$. This completes the proof.
My concerns:
- Overall, this proof seems strange and far too lengthy.
- I'm not sure that induction was the right way to proceed at all.