Show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible.

Suppose \(\alpha\) is a wff of length \(2\), and \(\langle \varepsilon_1,\ldots,\varepsilon_n\rangle\) is it’s construction sequence. We have that \(\alpha = \varepsilon_n\), where \(\varepsilon_n\) is one of the three possibilities 1) \(\varepsilon_n\) is a sentence symbol 2) \(\varepsilon_n = \varepsilon_\lnot(\varepsilon_j)\) where \(j<n\) 3) \(\varepsilon_n = \varepsilon_\square(\varepsilon_j,\varepsilon_k)\) where \(j,k <n\) and \(\square\) is one of \(\land,\lor,\to,\leftrightarrow\)

If \(\varepsilon_n\) is a sentence symbol then \(\alpha\) has length \(1\), a contradiction. Thus, \(\varepsilon_n\) is not a sentence symbol.

If \(\varepsilon_n = \varepsilon_\lnot(\varepsilon_j)\) then since \(\varepsilon_j =\beta\) must have length at least \(1\), \(\alpha = \varepsilon_\lnot(\varepsilon_j) = (\lnot\beta)\) has length at least \(4\), a contradiction.

Thus \(\varepsilon_n = \varepsilon_\square(\varepsilon_j,\varepsilon_k)\) where \(j,k < n\) and \(\square\) is one of \(\land,\lor,\to,\leftrightarrow\) Since \(\varepsilon_j = \beta\) and \(\varepsilon_k = \gamma\) have length at least \(1\), \(\alpha = \varepsilon_\square(\varepsilon_j,\varepsilon_k) = (\beta\square\gamma)\) will have length at least \(5\), another contradiction.

Therefore, it is impossible for \(\alpha\) to have length \(2\).

The previous argument can be repeated exactly to show that there are no wffs of length \(3\).

Now, suppose that \(\alpha\) is a wff of length \(6\), and \(\langle \varepsilon_1,\ldots,\varepsilon_n\rangle\) is its construction sequence.

Obviously, \(\alpha\) is not a sentence symbol. If \(\varepsilon_n = \varepsilon_\lnot(\varepsilon_j)\) and \(\varepsilon_j =\beta\), then \(\alpha = \varepsilon_\lnot(\varepsilon_j) = (\lnot\beta)\) having length \(6\) implies that \(\beta\) must have length \(3\). But this is impossible, since we know there are no wffs with length \(3\).

Thus, it must be that \(\varepsilon_n = \varepsilon_\square(\varepsilon_j,\varepsilon_k)\). Since \(\varepsilon_j = \beta\) and \(\varepsilon_k = \gamma\) are wffs, we have that \(\alpha = (\beta\square\gamma)\), so that the concatenation \(\beta\gamma\) is of length \(3\). Since wffs must be of length at least \(1\), we must have either \(\beta\) or \(\gamma\) of length \(2\). But this is a contradiction, since there are no wffs of length \(2\).

Therefore, there are no wffs of length \(6\).

Now, all that remains to be seen is that there are wffs of all positive lengths besides \(2,3\) and \(6\). Obviously, there exists wffs of length \(1\) since sentence symbols are wffs. Since negation of a wff of length \(k\) yields a new wff with length \(k+3\), we know that there exists wffs of lengths \(1,4,7,10,\ldots\) given by \begin{equation}A_1\quad(\lnot A_1)\quad (\lnot(\lnot A_1))\quad (\lnot(\lnot(\lnot A_1)))\end{equation} Now consider the wff \((A_1\land A_2)\) which has length \(5\). Through repeated negation of this wff as in the above step, we get wffs with lengths \(5,8,11,14,\ldots\)

The only remaining step is to show that there exists wffs of lengths \(9,12,15,18,\ldots\) These can be obtained by considering the wff \((A_1\lor(A_2\land A_3))\) which has length \(9\), and performing repeated negations as above.

Therefore, there exists wffs with length \(k\) for any positive integer \(k\) besides \(2,3\) and \(6\).