$\forall n \in \mathbb{N}, n$ is even $\Leftrightarrow n+1$ is odd

Question

I would like to prove this theorem with only basic properties of Peano's axioms, addition, and multiplication. Please have a check of my below proof. Many thanks for your help!

In my definition:

$n$ is even $\Leftrightarrow n=2t$ for some $t \in \mathbb{N}$.

$n$ is odd $\Leftrightarrow n$ is not even.

I do NOT assume the property that $2t+1$ is odd for all $t \in \mathbb{N}$.

Lemma:

$\forall n \in \mathbb{N}, n$ is even $\implies n+1$ is odd.

Proof:

Assume the contrary, i.e. there exists $n$ such that $n$ is even and $n+1$ is even. This means $n = 2a$ and $n+1=2b$ for some $a, b$. As a result, $2a+1=2b$. We have three possible cases in total.

In case $a=b \implies 2a+1=2a \implies 1=0$ (contradiction)

In case $a>b \implies \exists t \in \mathbb{N}, a=b+t+1 \implies 2(b+t+1)+1=2b \implies 2t+2=0$ (contradiction)

In case $a<b \implies \exists t \in \mathbb{N}, b=a+t+1 \implies 2a+1=2(a+t+1) \implies 2t+1=0$ (contradiction)

To sum up, there does NOT exist any $n$ such that $n$ is even and $n+1$ is even, or equivalently If $n$ is even, then $n+1$ is odd.

Theorem:

$\forall n \in \mathbb{N}, n$ is even $\Leftrightarrow n+1$ is odd.

Proof:

Let $T =\{n \in \mathbb{N} \mid n \text{ is even } \Leftrightarrow n+1 \text{ is odd}\}$. Now we prove $T=\mathbb{N}$.

First, $0=2.0 \implies 0$ is even. Applying Lemma, we have $0+1$ is odd. This implies $0 \in T$.

Assume $k \in T$, then $k \text{ is even } \Leftrightarrow k+1 \text{ is odd}$.

If $k+1$ is even, then $(k+1)+1$ is odd (from our Lemma). As a result, $k+1 \in T$.

If $k+1$ is odd, then $k$ is even (Since $k \in T$). We have $(k+1)+1=k+2=2t+2=2(t+1)$ (Since $k$ is even). Thus, $(k+1)+1$ is even. As a result, $k+1 \in T$ too.

To sum up, $k \in T \implies k+1 \in T$. By principle of induction, $T=\mathbb{N}$.

Answer 1

I actually have a number of complaints about your proof:

First, you write:

$n$ is odd if $n$ is not even.

I assume you meant:

$n$ is odd $\color{red}{iff}$ $n$ is not even.

Second, you say:

Let $T =\{n \in \mathbb{N} \mid (n \text{ is even } \implies n+1 \text{ is odd }) \vee (n \text{ is odd } \implies n+1 \text{ is even})\}$.

No! That should be $T =\{n \in \mathbb{N} \mid (n \text{ is even } \implies n+1 \text{ is odd }) \color{red}\land (n \text{ is odd } \implies n+1 \text{ is even})\}$.

If you use $\lor$, then the condition is trivially satisfied because of your Lemma: you have already shown that for any $n$ that $(n \text{ is even } \implies n+1 \text{ is odd }) $, and hence we automatically have that for any $n$ that $(n \text{ is even } \implies n+1 \text{ is odd }) \vee (n \text{ is odd } \implies n+1 \text{ is even})$.

Later on you make the same mistake:

Assume $k \in T$, then $(k \text{ is even } \implies k+1 \text{ is odd })$ or $(k \text{ is odd } \implies k+1 \text{ is even})$.

No, the inductive hypothesis is that:

$(k \text{ is even } \implies k+1 \text{ is odd }) \color{red}{and} (k \text{ is odd } \implies k+1 \text{ is even})$

The $\lor$ that you are thinking of is of course that $k$ is even or $k$ is odd. But you are trying to show both that $k$ being even implies $k+1$ being odd, and that $k$ being odd implies $k1$ being even.

Third, note that with:

If $k$ is even, then $k=2x$ for some $x$ and $k+1$ is odd. As a result, $(k+1)+1=k+2=2x+2=2(x+1)$. So $(k+1)+1$ is even.

what you end up showing is that $k$ is even $\implies$ $(k+1)+1$ is even, which is not the same as what you claim you have shown:

In this case, $k+1$ is odd $\implies (k+1)+1$ is even.

Indeed, by assuming $k$ is even, you can use $k=2x$ ... and you're off and running. But, starting with $k+1$ is odd, it's not immediately clear that therefore $k$ is even!

Similarly, when you do:

If $k$ is odd, then $k+1$ is even. Applying Lemma again, we have $(k+1)+1$ is odd.

what you end up showing is $k$ is odd $\implies$ $(k+1)+1$ is odd, which is not what you claim to have shown:

In this case, $k+1$ is even $\implies (k+1)+1$ is odd.

You can fix your proof by starting out by saying that $k+1$ is even or not even, i.e. even or odd. Then, when $k+1$ is even, you can use your Lemma to infer that $(k+1)+1$ is odd. Going from $k+1$ being odd to $(k+1)+1)$ being even is a little bit more involved: By inductive hypothesis we know $k$ is odd $\implies$ $k+1$ is even, so since $k+1$ is odd (i.e. not even), we know $k$ is not odd, i.e. even (this is also why you really want to define odd with an if and only if!). And now that $k$ is even, you can do what you did before. But note the important difference: rather than going from $k$ is even to $k+1$ is odd to $(k+1)+1$ is even, you go from $k+1$ is odd to $k$ is even to $(k+1)+1$ is even.

Answer 2

As far as your lemma goes, the contradiction "$2t+2=0$" could be elaborated on a little more; you assume $2\in\mathbb{N}$ as well as $-2\not\in\mathbb{N}$. Adding $-2$ to both sides yields $2t=-2$, and then the contradiction comes from the fact that $2$ and $t$ are both natural, hence their product must be (because $\mathbb{N}$ is closed under multiplication), yet $-2$ is not. A similar thing goes for $2t+1=0$.

As for the rest, it looks good. Nice use of induction, otherwise nothing to say about it, really.