Instead of proving that \(P(n)\) holds for all \(n\in \mathbb {N}\), we prove the stronger statement that both \(P(n)\) and \(P(n+1)\) holds for all \(n\in \mathbb {N}\). To do so, we proceed by induction on \(n\). Indeed, in the base case, if \(n = 0\), then \(P(0)\) and \(P(1)\) hold by assumption.

Now assume that \(P(n)\) and \(P(n+1)\) both hold for some \(n\). We now prove that \(P(n+1)\) and \(P(n+2)\) hold. It follows from the inductive hypothesis that \(P(n+1)\) holds. Furthermore, since \(P(n)\) holds, it follows from the assumptions of the lemma that \(P(n+2)\) also holds. Hence \(P(n+1)\) and \(P(n+2)\) both hold, completing the induction and therefore the lemma.

Since \(n\) is multiplicatively even, there exists \(m\in \mathbb {N}\) such that \(n = 2m\). Then \(n+2 = 2m+2 = 2(m+1)\), hence \(n+2\) is also multiplicately even, as required.

(\(\Rightarrow \)) Assume \(n\) is additively even. Then \(n+2\) is also additively even, since the set of additively even numbers is closed under adding \(2\).

(\(\Leftarrow \)) Now assume \(n+2\) is additively even. If \(n\) was not additively even, then \(E\setminus \{ n+2\} \) would still be a set containing \(0\) that is closed under adding \(2\). But the set of additively even numbers \(E\) was defined to be the least such set. Therefore \(n\) must be additively even.

We proceed by induction with step size two on \(n\), from Lemma 6. For our base cases, when \(n = 0\) we have that \(0\) is additively even and \(\texttt{iseven}(0) = \texttt{true}\) by definition. When \(n = 1\), \(1\) is not additively even, since if it were, there would need to exist some \(m\in E\) such that \(m+2 = 1\), but this is not possible for naturals. Furthermore, \(\texttt{iseven}(1) = \texttt{not}\ \texttt{iseven}(0) = \texttt{false}\neq \texttt{true}\), so the statement holds for \(n=1\) as well.

Now assume the equivalence holds for \(n\). We prove it also holds for \(n+2\). To this end, note that \(n+2\) is additively even if and only if \(n\) is additively even by Lemma 12. Furthermore, \(\texttt{iseven}(n+2) = \texttt{not}\ \texttt{iseven}(n+1) = \texttt{not}\ \texttt{not}\ \texttt{iseven}(n) = \texttt{iseven}(n)\). Therefore the statement for \(n+2\) is equivalent to the statement for \(n\) and hence holds. This completes the induction.

(\(\Rightarrow \)) Assume that \(n\) is multiplicatively even. Then there exists \(m\in \mathbb {N}\) such that \(n = 2m\). By Lemma 13, to prove that \(n\) is additively even, it suffice to prove that \(\texttt{iseven}(2m) = \texttt{true}\). We proceed by induction on \(m\). When \(m = 0\), clearly \(\texttt{iseven}(2m) = \texttt{iseven}(0) = \texttt{true}\).

Now assume that \(\texttt{iseven}(2m) = \texttt{true}\). We want to prove that \(\texttt{iseven}(2(m+1)) = \texttt{true}\) as well. But then

This completes the induction.

(\(\Leftarrow \)) Assume that \(n\) is additively even. We proceed by induction with step size two on \(n\), from Lemma 6. For our base cases, when \(n = 0\), \(n\) is additively even and \(n = 2\cdot 0\) is also multiplicatively even. When \(n = 1\), then \(n\) is not additively even by the same reasoning as in Lemma 13, hence the statement also holds.

Now assume that the statement holds for \(n\). We prove it holds for \(n+2\). To see this note that by Lemma 12, \(n+2\) is additively even if and only if \(n\) is. If \(n\) was not additively even, then we are done. Otherwise, by the inductive hypothesis, it follows that \(n\) is multiplicatively even. But then, by Lemma 11, \(n+2\) is also multiplicatively even. This completes the proof.

By Lemma 13, conditions (ii) and (iii) are equivalent. By Lemma 14, conditions (i) and (ii) are equivalent. Hence we are done by transitivity of equivalence.