Proof by induction of propositional formulas

Question

I have two inductively defined operations:

1. $\text{bin}$

   base case:

   If $p$ is a propositional letter, then $\text{bin}(p) = 0$

   inductive step

   $\text{bin}(\neg \phi) = \text{bin} (\phi)$

   $\text{bin}(\phi \wedge \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$

   $\text{bin}(\phi \vee \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$

   $\text{bin}(\phi \rightarrow \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$

   $\text{bin}(\phi \leftrightarrow \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$

2. $S$, which is defined as

   $S(p) = \emptyset$

   $S(\neg \phi) = S(\phi)$

   $S(\phi \square \psi) = S(\phi) \cup S(\psi) \cup \{\phi, \psi\}$ where $\square$ can be $\wedge, \vee, \rightarrow or\leftrightarrow$

The inductive proof I have to give: Let bin($\phi$) be equal to the number of binary connectives in $\phi$, and |V| the number of elements of the set V.

Prove with induction that the following inequality holds for every propositional formula $\phi$: |S($\phi$)| $\leq$ 2 $\cdot$ bin($\phi$).

For the base case, I have the following:

Base case:

If $\phi$ is an atomic propositional formula, then bin($\phi$) = 0 and |S($\phi$)| = |$\emptyset$| = 0, and so |S($\phi$)| $\leq$ 2 $\cdot$ bin($\phi$) holds.

Inductive step:

I have no idea how to tackle this, but I have to prove for negation and for the binary connectives.

I would say I would start with:

"Assume the inductive hypothesis is true, i.e., |S($\phi$)| $\leq$ 2 $\cdot$ bin($\phi$) is true", or, maybe better, "Assume the property holds for formulas $\phi$ and $\psi$"

Then, case negation: S($\neg \phi$) = S($ \phi$) and bin($\neg \phi$) = bin($ \phi$), and therefor the property holds for $\neg \phi$

Then, case conjunction: bin($\phi \wedge \psi$) = bin($\phi$) + bin($\psi$) + 1, and S($\phi \wedge \psi$) = S($\phi$) $\cup$ S($\psi$) $\cup$ {$\phi$, $\psi$}.

Now, what I think I see is that with the operation bin 1 gets added, and with S *two* elements are added to the set. I just don't know how to formulate this nicely.

Answer 1

I'm not sure I understand what you want, but here it goes: suppose that $\left|S(\phi)\right|\leq 2\text{bin}\left(\phi\right)$ and $\left|S(\psi)\right|\leq 2\text{bin}\left(\psi\right)$ both hold. Let $\square$ denote an arbitrary binary connective.

The goal is to prove that $\left|S\left(\phi \square \psi\right)\right|\leq 2\text{bin}\left(\phi \square \psi\right)$. Note the following: $$\begin{align} \left|S\left(\phi \square \psi\right)\right|&=\left|S(\phi)+S(\psi)+\{\phi, \psi\}\right| &\text{Definition of }S\\ &\leq \left|S(\phi)\right|+\left|S(\psi)\right|+\left|\{\phi, \psi\}\right| &\text{Inclusion Exclusion Principle}\\ &\leq 2\text{bin}\left(\phi\right)+2\text{bin}\left(\psi\right)+2 &\text{Inductive Hypothesis}\\ &=2\left(\text{bin}\left(\phi\right)+\text{bin}\left(\psi\right)+1\right) &\text{Distributitivy of} + \text{over}\cdot\\ &=2\left(\text{bin}\left(\phi \square \psi\right)\right)&\text{Part 1}. \end{align}$$

This concludes the induction.