6
$\begingroup$

There is this question, but the definition of "even" and "odd" that I am using uses integers instead of just natural numbers; i.e.,

  • An integer $n$ is even iff there is some integer $k$ such that $n=2k$.
  • An integer $n$ is odd iff there is some integer $k$ such that $n=2k+1$.

Here is what I have so far:

First we show that an integer $n$ is even or odd. We first use induction on the positive integers. For the base case, $1=2\cdot0+1$ so we are done. Now suppose inductively that $n$ is even or odd. If $n$ is even, then $n=2k$ for some $k$ so that $n+1=2k+1$ (odd). If $n$ is odd, then $n=2k+1$ for some $k$ so that $n+1=2(k+1)$ (even). This closes the induction, so every $n\in\mathbf{Z}^+$ is even or odd.

Now we show every $n\in\mathbf{Z}^-$ is even or odd. Let $n\in\mathbf{Z}^-$. Then $n=-k$ for some $k\in\mathbf{Z}$ (I think this follows immediately from most definitions of the integers.). Suppose $k$ is even. Then $k=2j$ for some $j$ so that $n=-k=-2j=2(-j)$ (even). Now suppose $k$ is odd. Then $k=2j+1$ for some $j$ so that $n=-k=-(2j+1)=-2j-1=-2j-1+1-1=-2j-2+1=2(-j-1)+1$ (odd).

For $0$, note that $0=2\cdot0$ (even).

Now we show that $n\in\mathbf{Z}$ cannot be both even and odd. Suppose for the sake of contradiction that $n\in\mathbf{Z}$ is both even and odd. Then there are integers $k,j$ such that $n=2k=2j+1$. This implies that $2(k-j)=1$ (like in the referenced question). So we must show that $1$ cannot be even in order to complete the proof.

This is where I am having trouble. I know that if I let $f:\mathbf{Z}\to\mathbf{Z};x\mapsto2x$ be a function, then $f$ is increasing so since $f(0)=0$ and $f(1)=2$ and $0<1<2$, there is no integer $m$ such that $f(m)=1$. But this seems complicated so I was wondering if there was an easier way to do this.

So my real question is: how can I show that $1$ is not even?

(This is not homework.)

$\endgroup$
  • $\begingroup$ $f(m)=1 \implies 2m=1 \implies 2=\frac {1}{m} $ which is not a integer for any $m \in \mathbb Z $ $\endgroup$ – Theorem Jul 4 '12 at 20:57
  • $\begingroup$ @russell11, I think you meant a function $f:\mathbb{Z}^+ \to \mathbb{Z}^+$ (or whatever the appropriate notation is for 'nonnegative'). Otherwise you and Theorem converge on the right idea; suppose $1=2m$ for some integer $m$. $m>0$ comes immediately, as twice a non-positive integer is non-positive. $m<1$ comes from the function being increasing. $\endgroup$ – Eugene Shvarts Jul 4 '12 at 21:02
2
$\begingroup$

To show that $1$ is not even:

I assume you can prove or accept that $a \cdot 0 = 0$ for all $a \in \mathbb{Z}$, the product of a positive and negative number is negative, and $2a > a$ when $a >0$.

If $1$ is even, then there must exists $a < 1$ such that $2a = 1$. However, the only $a < 1$, which is an integer, is $0$ and clearly $2 \cdot 0 = 0$. So $1$ can not be be written as $2 \cdot a$ for any $a \in \mathbb{Z}$. $1$ is odd.

$\endgroup$
  • 1
    $\begingroup$ Do you want to say, "So $1$ cannot be written as $2\cdot a$ for any $a\in\mathbb{Z}$" in the end? $\endgroup$ – Paul Jul 4 '12 at 21:13
  • $\begingroup$ @Paul Yes. Added the missing "not". $\endgroup$ – William Jul 4 '12 at 21:21
0
$\begingroup$

Hint $\ $ Your induction step uses $\rm\:n\,$ even $\rm\,\Rightarrow\: n\!+\!1\:$ odd, and $\rm\:n\,$ odd $\rm\,\Rightarrow\:n\!+\!1\:$ even. The converses are both true, e.g. $\rm\,n\!+\!1\,$ odd $\,\Rightarrow$ $\rm\,n\!+\!1 = 2k\!+\!1\,$ $\Rightarrow$ $\rm\,n = 2k,\,$ since $\rm\,j\!+\!1 = k\!+\!1\,$ $\Rightarrow$ $\rm\,j = k\,$ by Peano axioms. Thus if $\rm\:n\!+\!1\,$ is both even and odd then so too is $\rm\,n.\,$ So, contrapositively, in your induction step you can lift "$\rm n\:$ is not both even and odd" from $\rm\,n\,$ up to $\rm\,n\!+\!1\,$ and hence prove by induction that every natural is even or odd, but not both (this is essentially my hint in the linked answer).

$\endgroup$
  • $\begingroup$ Thanks, this is really neat. I didn't understand your hint in the other question, but now I do. $\endgroup$ – russell11 Jul 5 '12 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.