How to perform induction on the number of connectives and quantifiers in a well-formed formula?

Question

I am trying to prove the following proposition from Mendelson's book.

If the free variables (if any) of a well-formed formula $\textbf{B}$ occur in the list $x_{i_1}, \dots, x_{i_k}$ and if the sequences $s$ and $s^′$ have the same components in the ${i_{1}}^\text{th}, \dots, > {i_{k}}^{th}$ places, then $s$ satisfies $\textbf{B}$ if and only if $s^′$ satisfies $\textbf{B}$. Here $s$ and $s^′$ are denumerable sequences $s = (s_1, s_2, \dots )$ of elements from the domain $D$ of some interpretation $M$.

The book suggests to use induction on the number of connectives and quantifiers in $\textbf{B}$. But I have no idea how the proof is supposed to look like. How do I count the number of connectives in some hypothetical wf $\textbf{B}$?

Answer 1

To prove that all formulas satisfy property $P$ by induction on the construction of a formula:

First, prove $P$ holds for all possible atomic formulas.

Then, prove that if $P$ holds for formulas $\phi, \rho$ (inductive hypothesis), then:

• $P$ holds for $\neg \phi$
• $P$ holds for $\phi \vee \rho$
• $P$ holds for $\phi \wedge \rho$
• $P$ holds for $\exists x: \phi$
• $P$ holds for $\forall x: \phi$

The idea is that if you have a larger formula like $\phi \wedge \rho$, you can assume (inductive hypothesis) the property has already been proven for formulas $\phi$, $\rho$ which have fewer connectives + quantifiers.