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

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.

• Aren't 'A and B' , or 'A or B' wff of length 3? Sep 6, 2013 at 5:45
• No (A ^ B) would have a length of 5. You have to include the parenthesis as part of the length. Sep 6, 2013 at 6:00
• What about $\neg A$ or $\neg\neg A$ of length 2 and 3, respetively? What are your exact syntactical rules? According to th eproblem statement, $(D)$ cannot be a wff as you are supposed to show that there is no wff of length 3. Sep 6, 2013 at 6:22
• I'm also confused; it seems if you could have a sentence of length 4, then you could couple it with a pair (sentence, connective) and get a sentence of length 6, e.g., given a sentence of length 4, attach to it , say, a '=>B' , to get a sentence of length 6. Maybe I'm being slow. Sep 6, 2013 at 6:26
• Isn't this a problem from Enderton's logic textbook? Sep 6, 2013 at 10:01

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

• Thank you for taking the time to work this out. I just have one question. Can you elaborate on how negating increases the length by 3? I am confused because you state that (¬A) has length 4. Does it increase by 3 because we start with L(a) = A, but L(¬a)= (¬A) ? Sep 6, 2013 at 6:50
• One more question, does the notation "\ {2, 3, 6}" mean that you are excluding that set of numbers from ℕ? Sep 6, 2013 at 7:03
• negation increases by 3 because you have three new symbols: $(, ), \lnot$. Sign "\" is set substraction. Sep 6, 2013 at 9:18
• @Trismegistos I see, thank you. Sep 6, 2013 at 17:00
• Thank you for your detailed answer. Could you further explain why for the second point "we conclude 𝐿(𝛽)∈{−1,0,3}, contradicting the induction hypothesis 𝐿(𝛽)∈ℕ∖{2,3,6}" when did we assume that 𝐿(𝛽)∈ℕ∖{2,3,6} and how did we show that 𝐿(𝛽)$\neq$ 3 (I know that it cant be but that is only obvious after exhausting every case) how would one formalize this reasoning thank you. Aug 22, 2019 at 7:19

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