Show that the relation "is subformula of" is transitive

Question

I'm reading Dirk van Dalen's Logic and Structure and I don't know how to approach it.
Do I have to do induction, and if I have, induction in what?

Answer 1

Ref. van Dalen, page 12 for the definition of sub-formula:

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

and the obvious part dealing with connectives, like e.g. $\lor$:

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

What we have to prove is that:

if $\varphi$ is a sub-f of $\psi$ and $\psi$ is a sub-f of $\sigma$, then $\varphi$ is a sub-f of $\sigma$.

The fact is quite obvious; consider the case: $\lor$.

If $\sigma=\sigma_1 \lor \sigma_2$, then $\text {Sub}(\sigma_i) \subseteq \text {Sub}(\sigma)$, for $i=1,2$ by definition.

Thus, if $\psi \in \text {Sub}(\sigma_i)$, then $\psi \in \text {Sub}(\sigma)$.

---

But yes, we can consider it an application of induction on the complexity of $\sigma$ (page 8), adding the trivial case of $\sigma$ atomic, where $\varphi=\psi=\sigma$.