Can a number be both odd and even? Can a number be neither?
You proved that zero is even last class (0 = 2*0).
Does that mean zero is not odd? Our intuition says "yes", but
can we
prove it?
Note: we had an
in-class activity about proving
this!
The in-class activity had three prose-style "proofs" that zero is not
odd. Two of the proofs were flawed, one was correct. You
were supposed to figure out which proof was correct and what
was wrong with the other two proofs. This is important!
It is easy to verify the correctness of a full first-order
proof (though not necessarily easy to find the proof in the
first place!)
Zero is not odd.
Assume by way of contradiction that odd(0).
Then let $k$ be an integer such that $2*k+1=0$.
By the trichotemy law, there are three cases:
-
case $k = 0$: then $2*k+1 = 1 \neq 0$.
-
case $0 \lt k$: then $2*0 \lt 2*k$ and so $0 \lt 2*k$. Since
$-1 \lt 0$, by the transitivity of $\lt$, $-1 \lt
2*k$. Adding 1 to both sides gives $0 \lt 2*k + 1$, so
$2*k+1 \neq 0$.
-
case $k \lt 0$: then $k = -1$ or $k \lt -1$ by the Gaps
everywhere theorem.
if $k = -1$ then $2*k + 1 = -2 + 1 = -1 \neq 0$
if $k \lt -1$ then $2*k \lt -2$ and so $2*k + 1 \lt -1$,
therefore $2*k+1 \neq 0$
In all cases $2*k+1 \neq 0$, which contradicts our assumption.
So there is no $k$ such that $2*k+1 = 0$, i.e.
$\neg \exists k[0 = 2*k+1]$, therefore
$\neg \text{odd}(0)$.
So zero is even and not odd. Are there any numbers that are
both even and odd?
No integer is both even and odd.
Let $n$ be an arbitrary but fixed integer.
By way of contradiction assume $\text{even}(n) \wedge \text{odd}(n)$.
Then there are constants $k_1$ and $k_2$ such that
$n = 2*k_1$ and $n=2*k_2+1$. So
$
\begin{array}{rcl}
2*k_1 &=& 2*k_2 + 1\\
0 &=& 2*k_2 + 1 + -(2*k_1)\\
0 &=& 2*k_2 + 2*(-1*k_1) + 1\\
0 &=& 2*(k_2 + -1*k_1) + 1
\end{array}
$
But this means $0$ is odd, which is a contradiction.
Thus $n$ cannot be both even and odd. Finally since $n$ is
arbitrary but fixed, that means that for all $n$, $n$ is not
both even and odd.
We now know that no integer can be both odd and even, but are
there integers out there that are neither? Certainly our
intuition is that this is impossible, but can we prove it?
Every integer is either even or odd (but, by the previous
theorem, not both!).
It is easy to prove that for all $x$,
$\text{odd}(x) \Leftrightarrow \text{odd}(-x)$ and
$\text{even}(x) \Leftrightarrow \text{even}(-x)$.
So if we prove this theorem for the non-negative integers, the
theorem holds for all integers. We will prove
$\text{even}(n) \vee \text{odd}(n)$, call this condition $(*)$,
for all non-negative $n$
by induction.
Case $n=0$: then $\text{even}(n)$ since 0 is even, so $(*)$ holds.
Case $n>0$: then by the inductive hypothesis
$\text{even}(n-1) \vee \text{odd}(n-1)$ holds. If $\text{even}(n-1)$,
then there is a $k$ such that $n-1=2*k$, so
$n = 2*k+1$, and thus $\text{odd}(n)$.
If $\text{odd}(n-1)$, then there is a $k$ such that
$n-1 = 2*k+1$, so $n = 2*k+2 = 2*(k+1)$, and thus $\text{even}(n)$.
Either way, $(*)$ holds.
So, by induction, we deduce $\text{even}(n) \vee \text{odd}(n)$
for all non-negative $n$.