Relation between depth and lenght of a formula in First-Order Logic

Question

I'm currently reading Mathematical Logic by Helmut Schwichtenberg, and he introduces the concepts of length and depth of formulas like this [see page 3] :

Definition. The depth $dp(A)$ of a formula $A$ is the maximum length of a branch in its construction tree.

Defintion. The size or length $|A|$ of a formula $A$ is the number of occurrences of logical symbols and atomic formulas (parentheses not counted) in $A$.

Further, he writes

One can show easily that $$|A| + 1 \leq 2^{dp(A)+1}$$

I have drawn some short constructions trees and noticed that it seems to hold, though I can't really see how I would go about to prove the statement?

Answer 1

Prove it by induction on complexity $k$ of the formula $A$, where $k$ is the depth $\text {dp}(A)$ associated to the constructiion tree of $A$.

Base case : $A$ atomic. Then $\text {dp}(A)=0$ and $|A|=1$.

We have that :

$|A|+1=2 \le 2^{\text {dp}(A)+1}=2^1+1=2+1=3$.

Induction step : we have to assume that the relation holds for formulas of complexity $k$ and prove it for a formula $A$ of complexity $k+1$.

We have to consider two cases :

(i) $A=\lnot B$, where $|A|=|B|+1$ and $\text {dp}(A)= \text {dp}(B) + 1$, and :

(ii) $A= B \lor C$, where $|A|= |B|+|C|+1$ (in "composite" formulas, we add a connective but we do not add atoms) and $\text {dp}(B \lor C) = \text {max}(\text{dp}(B), \text {dp}(C)) + 1$.

Check (ii) :

$$|A|+1=(|B|+|C| +1)+1= (|B|+1) + (|C| +1) \le (2^{\text {dp}(B)+1})+(2^{\text {dp}(C)+1}) \text { (by induction hypo) } \le 2(2^{\text {max}(\text{dp}(B), \text {dp}(C))+1})=2(2^{\text {dp}(B \lor C)}) = 2^{\text {dp}(B \lor C)+1}.$$