# 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? – DBFdalwayse 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. – Derrek Whistle 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. – Hagen von Eitzen 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. – DBFdalwayse Sep 6 '13 at 6:26
• @HagenvonEitzen Yes, you are are right. (D) cannot be a wff. I was just showing how a wff 2 couldn't be possible. I believe ¬A would have a wff of length 1 as because the only binary connective are (^, v, ->, <->) and sentence symbols as well as parenthesis count as 1 length. – Derrek Whistle Sep 6 '13 at 6:35

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) ? – Derrek Whistle 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 ℕ? – Derrek Whistle Sep 6 '13 at 7:03
• negation increases by 3 because you have three new symbols: $(, ), \lnot$. Sign "\" is set substraction. – Trismegistos Sep 6 '13 at 9:18
• @Trismegistos I see, thank you. – Derrek Whistle Sep 6 '13 at 17:00