solution to :If ϕ occurs in a shortest formation sequence of ψ then ϕ is a subformula of ψ

Question

Can anybody help me solve this question?

If ϕ occurs in a shortest formation sequence of ψ then ϕ is a subformula of ψ I know that the proof is by induction but I do not specificly know how to solve it.

Answer 1

Hint

Yes, by induction, using the def of subformula :

$\text {Sub} (\varphi) = \{ \varphi \}$, if $\varphi$ is atomic

$\text {Sub} (\varphi_1 \square \varphi_2) = \text {Sub} (\varphi_1) \cup \text {Sub} (\varphi_2) \cup \{ \varphi_1 \square \varphi_2 \}$, for $\square \in \{ \lor, \land \to \}$

$\text {Sub} (\lnot \varphi) = \text {Sub} (\varphi) \cup \{ \lnot \varphi \}$.

---

Base :

If $\psi$ is atomic, e.g. $p$, then its shortest formation sequence will be : $p$.

Thus, if $\varphi$ occurs in it, it must be $p$ itself, that is a subformula of $\psi$.

Induction :

Case (i) : $\psi$ is $\varphi_1 \lor \varphi_2$.

Then, if $\varphi$ occurs in the formation sequence of it, either it occurs in that of $\varphi_1$ or in that of $\varphi_2$.

Thus, by induction hypotheses, either it is a subformula of $\varphi_1$ or it is a subformula of $\varphi_2$, and so it is a subformula of $\psi$.

The cases for the other conncetives are similar.