Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
    
$f(m)=1 \implies 2m=1 \implies 2=\frac {1}{m} $ which is not a integer for any $m \in \mathbb Z $ –  Theorem Jul 4 '12 at 20:57
    
@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. –  Eugene Shvarts Jul 4 '12 at 21:02
add comment

2 Answers

up vote 1 down vote accepted

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.

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

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).

share|improve this answer
    
Thanks, this is really neat. I didn't understand your hint in the other question, but now I do. –  russell11 Jul 5 '12 at 1:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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