# Proving that the number of atoms in a formula is equal to the number of the symbols $\land,\lor,\rightarrow$ plus 1

This is only correct for a formula only having the symbols $\land,\lor,\rightarrow$ .The proof behind this shouldn't be complicated but i'm having difficulty writing the induction step since I'm a novice with proofs by inductions.

I have started the proof like this: let $C(\varphi)$ be the number of occurences of the symbols $\land,\lor,\rightarrow$,and let $S(\varphi)$ be the number of atoms for a well formed formula $\varphi$.

Base step:$\varphi$ is an atom ,then $C(\varphi)=0,S(\varphi)=C(\varphi)+1=1.$

Induction step:Here i'm thinking of taking some $S(\varphi_1),S(\varphi_2)$ for a well formed formulas and then checking the 3 cases where i do $S(\varphi_3)=S(\varphi_1\lor\varphi_2) \implies S(\varphi_3)=S(\varphi_1)+S(\varphi_2)+1.$ similiary for $\land,\rightarrow...$

Is my induction step correct? if so i need a little help in writing it correctly to be considered a proper proof because i'm thinking that i'm failing to do that.

• I removed the (induction) tag because this question is about structural induction and the tag is reserved for mathematical induction. – Git Gud May 13 '18 at 12:15
• @GitGud You could certainly do an ugly induction on the number of connectives instead of a structural induction, but I suppose the desird form of proof is up to the OP – Mark S. May 13 '18 at 12:40
• @MarkS. Certainly, but the OP's question suggests they are using structural induction, that's why I removed the tag. – Git Gud May 13 '18 at 12:48

The idea is correct. You only need to notice that

$$S(\varphi_3) = S(\varphi_1 \land \varphi_2) = S(\varphi_1) + S(\varphi_2) = C(\varphi_1) + 1 + C(\varphi_2) + 1 = C(\varphi_1)+ C(\varphi_2) + 2$$

and

$$C(\varphi_3) = C(\varphi_1 \land \varphi_2) = C(\varphi_1) + C(\varphi_2) + 1$$

You don't really need to distinguish the $3$ cases as we are not really using the properties of the connectives.

• How are you going to prove it for the negation without distinguishing it? – Git Gud May 13 '18 at 12:14
• @Git Gud there is no negation case in the given formulas ,@Manlio It is then a sufficient proof? – user3133165 May 13 '18 at 12:27
• @user3133165 - The base step in the OP is OK. Also Manlio's answer is OK for a formula of the form $\varphi = \varphi_1 \circ \varphi_2$ where $\circ \in \{\land, \lor, \to\}$. But in that answer the case where $\varphi = \lnot \varphi_1$ is missing! In this case, $S(\varphi) = S(\varphi_1) = C(\varphi_1) + 1 = C(\varphi) + 1$, where the second identity holds by induction hypothesis. – Taroccoesbrocco May 13 '18 at 12:42
• @user3133165 You're right, I missed that. I should say, however, that $\neg$ not being present is probably a fluke. Also it's unlikely that your version of structural induction doesn't require the negation. – Git Gud May 13 '18 at 12:50
• @user3133165 Yes, to prove the claim I don't see anything needed on top what I wrote – Manlio May 13 '18 at 13:22