# 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 '13 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 '13 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 '13 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 '13 at 6:26
• Isn't this a problem from Enderton's logic textbook? Sep 6 '13 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 '13 at 6:50
• One more question, does the notation "\ {2, 3, 6}" mean that you are excluding that set of numbers from ℕ? Sep 6 '13 at 7:03
• negation increases by 3 because you have three new symbols: $(, ), \lnot$. Sign "\" is set substraction. Sep 6 '13 at 9:18
• @Trismegistos I see, thank you. Sep 6 '13 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 '19 at 7:19