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

Question

Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible.

The wffs in question are those associated with sentential/propositional logic. So, sentence symbols would have length 1, where a sentence symbol represents some statement that evaluates to true or false, i.e. "The dog ran across the room" could be represented by the capital letter D. Also, the only eligible binary connective are (^, v, ->, <->).

I can see how there couldn't be wffs of length 2, because each wff must be surrounded by parentheses and contain at least one sentence symbol:

    (D) has length 3

I am not sure how to complete this proof using induction though.

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

Answer 2

This is an old question, but here's my less rigorous proof:

Given a wff:

• Inserting $\lnot$, will always add 3 characters: e.g $\dots (a \land b) \dots \to \dots (a \land \color{red}{(\lnot b)}) \dots$
• Inserting $\Box$ (any binary operator), will always add 4 characters: e.g $\dots (a \land b) \dots \to \dots (a \land \color{red}{(b\ \Box\ c)}) \dots$

The smallest expression we can ever have is a sentence symbol itself, so the possible lengths must be: $$1 + 3a + 4b, \text{ where } a, b \in \mathbb{N}$$ We temporarily ignore the $1+$ and focus on $3a + 4b$ only.

We make a table where the first row is $3a$, and the first column is $4b$, and their intersections as their sums:

$$ \begin{bmatrix} 0 & 3 & 6 & 9 & \dots \\ 4 &4+3 &4+6 & \dots\\ 8 &8+3 & \ddots\\ 12 & \vdots \\ \vdots \end{bmatrix} \to \begin{bmatrix} 0 & 3 & 6 & 9 & \dots\\ 4 & 7 & 10 & 13 \\ 8 & 11 & 14 & \\ 12 & 15 & & \ddots \\ \vdots & & & & \end{bmatrix} \to \begin{bmatrix} 0 & 3 & \color{red}{6} & \color{blue}{9} & \dots\\ 4 & \color{red}{7} & \color{blue}{10} & \color{red}{13} \\ \color{red}{8} & \color{blue}{11} & \color{red}{14} & \\ \color{blue}{12} & \color{red}{15} && \ddots \\ \vdots \end{bmatrix} $$

We notice all numbers $\geq$ 6 are in the table (colored $\color{red}{\text{red}}$ & $\color{blue}{\text{blue}}$). This means $3a + 4b$ can equal: $0, 3, 4, 6, 7, 8 \dots$ but not $1, 2, 5$

Since we had $1 + 3a + 4b$, we just add 1 and the numbers it can't equal and we get: $2, 3, 6$.