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.

  • $\begingroup$ I removed the (induction) tag because this question is about structural induction and the tag is reserved for mathematical induction. $\endgroup$ – Git Gud May 13 '18 at 12:15
  • $\begingroup$ @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 $\endgroup$ – Mark S. May 13 '18 at 12:40
  • $\begingroup$ @MarkS. Certainly, but the OP's question suggests they are using structural induction, that's why I removed the tag. $\endgroup$ – 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$$


$$ 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.

  • $\begingroup$ How are you going to prove it for the negation without distinguishing it? $\endgroup$ – Git Gud May 13 '18 at 12:14
  • $\begingroup$ @Git Gud there is no negation case in the given formulas ,@Manlio It is then a sufficient proof? $\endgroup$ – user3133165 May 13 '18 at 12:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Taroccoesbrocco May 13 '18 at 12:42
  • $\begingroup$ @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. $\endgroup$ – Git Gud May 13 '18 at 12:50
  • $\begingroup$ @user3133165 Yes, to prove the claim I don't see anything needed on top what I wrote $\endgroup$ – Manlio May 13 '18 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.