Induction proof for the lengths of well-formed formulas (wffs)

Solution 1:

I assume that a wff is either

• a sentence symbol of length 1
• of the form $(\neg \alpha)$ of length $L+3$ where $\alpha$ is a wff of length $L$
• of the form $(\alpha\circ\beta)$ of length $L_1+L_2+3$, where $\alpha,\beta$ are wff of lengths $L_a,L_2$ and $\circ\in\{\land\lor,\to,\leftrightarrow\}$

Then use structiral induction to show

Proposition. If $\alpha$ is a wff then its length $L(\alpha)$ is in $\mathbb N\setminus\{2,3,6\}$

Proof: We assume that $L(\alpha)\in\mathbb N$ is already known, so it suffices to show $L(\alpha)\notin\{2,3,6\}$.

• If $\alpha$ is a sentence symbol then $L(\alpha)=1\in\mathbb N\setminus\{2,3,6\}$
• If $\alpha$ is of the form $(\neg\beta)$, then $L(\alpha)=L(\beta)+3$. If we assume that $L(\alpha)\in\{2,3,6\}$ we conclude $L(\beta)\in \{-1,0,3\}$, contradicting the induction hypothesis $L(\beta)\in\mathbb N\setminus\{2,3,6\}$. Therefore $L(\alpha)\in\mathbb N\setminus\{2,3,6\}$ also in this case
• If $\alpha$ is of the form $(\beta\circ\gamma)$, we have $L(\alpha)=L(\beta)+L(\gamma)+3$, especially $L(\alpha)\ge 5$. We need only exclude $L(\alpha)=6$, which would require that of of the sub-lengths is $1$ and the other os $2$, but that is not possible.

Proposition. If $n\in\mathbb N\setminus\{2,3,6\}$, then there exists a wff $\alpha$ with $L(\alpha)=n$.

Proof: $A$, $(\neg A)$, $(A\land A)$ are examples of lengths $1,4,5$. $((A\land A)\land A)$ is of length $9$ Since negating increases the length by $3$, we can obtain any length $n=4+3k$ and any length $n=5+3k$ and any lenbgth $n=9+3k$ with $k\ge 0$.