Let \(\alpha\) be a wff; let \(c\) be the number of places at which binary connective symbols \((\land,\lor,\to,\leftrightarrow)\) occur in \(\alpha\); let \(s\) be the number of places at which sentence symbols occur in \(\alpha\). (For example, if \(\alpha\) is \((A\to(\lnot A))\) then \(c=1\) and \(s=2\).) Show by using the induction principle that \(s = c+1\).

For an arbitrary formula \(\alpha\), let \(s[\alpha]\) denote the number of binary connective symbols which occur in \(\alpha\), and let \(c[\alpha]\) denote the numbber of places at which sentence symbols occur in \(\alpha\). Let \(S\) denote the set of wffs such that if \(\alpha\in S\) then \(s[\alpha] = c[\alpha] + 1\).

The goal is to show that \(S\) contains all wffs. To show this, I show that \(S\) contains all the sentence symbols and is closed under all 5 sentence building operations. By the induction principle, this will mean that \(S\) is the set of all wffs.

Consider \(A_i\) an arbitrary sentence symbol. Since \(s[A_i] = 1\) and \(c[A_i] = 0\), it is clear that \(s[A_i] = c[A_i] + 1\). Thus, \(A_i \in S\) for all integers \(i\geq 1\).

Now suppose that \(\alpha,\beta\in S\). Then we have that \(s[\alpha] + s[\beta] = c[\alpha] + c[\beta] + 2\). We consider \((\alpha\square\beta)\) where \(\square\) is one of \(\land,\lor,\to,\leftrightarrow\). Then \(s[(\alpha\square\beta)] = s[\alpha] + s[\beta]\) and \(c[(\alpha\square\beta)] = c[\alpha] + c[\beta] + 1\) The equation established earlier then implies that \(s[(\alpha\square\beta)] = c[(\alpha\square\beta)] + 1\), so that \((\alpha\square\beta)\in S\)

Therefore, by the induction principle, \(S\) is the set of all wffs.