Relationship between the number of atomic formulas in a given formula and the number of right arrows

Question

Here's the problem I'm doing;

Let $L_P$ be the language of propositional logic (consisting of parentheses, $\lnot$, $\rightarrow$ and a countable set of atomic formulae). Let $\alpha$ be any formula of $L_p$. Let $s(\alpha)$ be the number of atomic formulas in $\alpha$ (counting repetitions) and let $c(\alpha)$ be the number of occurences of $\rightarrow$ in $\alpha$. Show that $s(\alpha) = c(\alpha)+1$.

---

Proof Attempt:

We proceed by induction on the number of left-parentheses of a given formula. Suppose that a given formula has $0$ left-parentheses. Then, it has $0$ right-parentheses. Hence, it can only be an atomic formula. So, $s(\alpha) = 1 = 1+0 = 1+c(\alpha)$, where $c(\alpha) = 0$ because $\rightarrow$ does not appear in an atomic formula. So, the assertion holds in the base case.

Now, suppose that the assertion holds for any formula with $n$ left-parentheses. Let $\alpha$ be such a formula. Then, there are only 3 ways to construct a new formula with $n+1$ left-parentheses:

1. $(\lnot \alpha)$

2. $(\alpha \rightarrow A_n)$

3. $(A_n \rightarrow \alpha)$

where $A_n$ is an arbitrary but fixed atomic formula. In the first case, the number of occurences of $\rightarrow$ does not change and the number of atomic formulae does not change. So, the assertion holds for this formula. In the last two cases, the number of occurrences of $\rightarrow$ and the number of atomic formulae in the given formulas each increase by $1$. So, the assertion will hold for them as well.

Hence, the assertion holds for any formula with $n+1$ left parentheses. This proves that the assertion holds for all formulas of $L_P$. $\Box$

Does the proof above work? If it doesn't, then why? How can I fix it?

Answer 1

The induction must be on the rank of $\alpha$, i.e. on the number of connectives in the formula.

You have already verified the base case.

The case for $\lnot$ is trivial: no new atoms and no new occurrences of $\to$.

The only case left is $\to$.

We have that $\alpha$ is $(\alpha_1 \to \alpha_2)$ and we assume that the property holds for $\alpha_i, i=1,2$, i.e.

$s(\alpha_i)=c(\alpha_i)+1$.

Now compute: $s(\alpha)=s(\alpha_1)+s(\alpha_2)$; no new atoms added to those already present.

$c(\alpha)=c(\alpha_1)+c(\alpha_2)+1$, because we add a new occurrence of $\to$.

Substituting:

$$s(\alpha)=s(\alpha_1)+s(\alpha_2)=[c(\alpha_1)+1]+[c(\alpha_2)+1]=[c(\alpha_1)+c(\alpha_2)+1]+1=c(\alpha)+1.$$