I don't understand this proof for proving that N is either even or odd but not both.

Question

Lemma 1: $\forall x\in N$, x is either an even number or an odd number (without being both at the same time).

Proof:

Let $x\in N$. Let us choose $k\in N$ as the minimum such that $2(k + 1)> x$.

Note that the integer k exists since $k\leq x$.

Since k is minimum, we have $2k\leq x \leq 2k + 1. $

This means that $x = 2k$ or $x = 2k+1$ which implies $ x $ is even or $ x $ is odd, but does not guarantee uniqueness.

On the other hand, if $ x = 2k = 2k'+ 1$ for $k'\in N $ then $2(k-k') = 1$ which is impossible.

$2k + 1 = 2k' $ for $k'\in N$ then $2(k'-k) = 1$ which is impossible.

We conclude that $x = 2k$ or $x = 2k + 1$ without being both at once.

---

My questions:

What does it mean that k is minimum? why does it automatically imply that we have $2k\leq x \leq 2k + 1 $ ?

Is k' different from k? In this case $2(k'-k) = 1$ would be possible. It's not clear to me what k' is.

Answer 1

I do not understand the proof either.
Here is a simple direct proof.

If x is divisible by 2, then x is even.
If x is not divisible by 2, then x divided by 2 has a remainer of 1; thus x is odd.

If x is both odd and even, then exists integers a,b with x = 2a and x = 2b + 1.
Thus 2a = 2b + 1, 2(a - b) = 1, a contradiction.

Answer 2

We choose $k$ to be the smallest number so that $2(k+1) \gt x$. Any larger $k$ will also satisfy the inequality. For example, if $x=9$, we choose $k=4$.

Now, since $x \lt 2k+2, x \le 2k+1$. On the other hand, if $x \lt 2k$, we would have $2((k-1)+1) \gt x$ and $k$ would not be minimal, so $2k \le x$

As $2k \le x \le 2k+1$ and $2k$ and $2k+1$ are neighboring, $x$ has to be equal to one of them. If it is equal to $2k$ it is even and if it is equal to $2k+1$ it is odd. I believe this is your definition of even and odd.

$k'$ is some number other than $k$. The worry is that $x=2k$, so is even, but also $x=2k'+1$, so would be odd. They are using the fact (maybe you have proved it already) that there is no integer $m$ such that $2m=1$. $k-k'$ would be an integer.