# checking proof that no natural number can be both even and odd

• Apr 4th 2013, 03:12 AM
issacnewton
checking proof that no natural number can be both even and odd
Hi

I am here after a long time. I want to prove that no natural number can be both even and odd. This is from basic analysis book. So I start by saying that let S be the set of natural numbers such that they are both even and odd.

$\displaystyle S=\{ n\in \mathbb{N}| \mbox{ n is even and n is odd} \}$

I assume the negation. So let S be non-empty. Since S is a subset of $\displaystyle \mathbb{N}$, by well ordering principle, S has a least element $\displaystyle k$. So
$\displaystyle k$ is both odd and even. $\displaystyle k = 2m$ and $\displaystyle k = 2n-1$ for some $\displaystyle m,n \in \mathbb{N}$. Which means $\displaystyle 2m = 2n-1$.
$\displaystyle \Rightarrow 2(m-n)=1$. Which means that $\displaystyle 1$ is an even number. At this point can I say that I have reached a contradiction. Or do I first need
to prove that $\displaystyle 1$ is an odd number to use that property ?

thanks
(Emo)
• Apr 4th 2013, 03:53 AM
Plato
Re: checking proof that no natural number can be both even and odd
Quote:

Originally Posted by issacnewton
Hi

I am here after a long time. I want to prove that no natural number can be both even and odd. This is from basic analysis book. So I start by saying that let S be the set of natural numbers such that they are both even and odd.

$\displaystyle S=\{ n\in \mathbb{N}| \mbox{ n is even and n is odd} \}$

I assume the negation. So let S be non-empty. Since S is a subset of $\displaystyle \mathbb{N}$, by well ordering principle, S has a least element $\displaystyle k$. So
$\displaystyle k$ is both odd and even. $\displaystyle k = 2m$ and $\displaystyle k = 2n-1$ for some $\displaystyle m,n \in \mathbb{N}$. Which means $\displaystyle 2m = 2n-1$.
$\displaystyle \Rightarrow 2(m-n)=1$. Which means that $\displaystyle 1$ is an even number. At this point can I say that I have reached a contradiction. Or do I first need to prove tthathat $\displaystyle 1$ is an odd number to use that property

How do you know that $\displaystyle 1\notin S~?$
• Apr 4th 2013, 03:59 AM
issacnewton
Re: checking proof that no natural number can be both even and odd
Good Afternoon Plato,

Yes, I don't know if $\displaystyle 1\notin S$. I think this problem could be done with induction. But I want to stick with well-ordering principle just for the fun. So would you suggest an alternative ?
• Apr 4th 2013, 05:00 AM
HallsofIvy
Re: checking proof that no natural number can be both even and odd
Are you saying that you do not know whether or not 1 is even? I'll give you hint- 1 is NOT even!

But you don't need either "induction" or "well ordering". Just use an indirect proof. Suppose there exist integer, x, that is both even and odd.
Since x is even, x= 2m for some integer m. Since x is odd, x= 2n- 1 for some integer n.
Then x= 2m= 2n- 1. 2n- 2m= 2(n- m)= 1. n- m= 1/2. Do you see why that is a contradiction?
• Apr 4th 2013, 06:01 AM
issacnewton
Re: checking proof that no natural number can be both even and odd
Hello HallsofIvy,

At that point, I can say that subtraction of two integers is an integer, so we reach a contradiction. But I was wondering about my original post. So is my approach correct ?.
1 is ODD, and I did reach a contradiction. Am I right ?
• Apr 4th 2013, 09:47 AM
emakarov
Re: checking proof that no natural number can be both even and odd
Quote:

Originally Posted by issacnewton
But I was wondering about my original post. So is my approach correct ?

The biggest remark about the OP is that it is not necessary to use the well-ordering principle. You never use the fact that k is the least element of S, just that it is some element of S.

Quote:

Originally Posted by issacnewton
1 is ODD, and I did reach a contradiction. Am I right ?

Yes. Proving that 1 is odd, if this is necessary, is trivial for normal people: if 1 = 2n for an integer n, then n = 1/2, and 1/2 is not an integer. I said for normal people because a pedant may ask why 1/2 is not an integer. Then we need some definition or axiomatization of integers to rely on. In Peano arithmetic, for example, the fact that 2n ≠ 1 for all n is proved by induction, though the induction hypothesis is not used.
• Apr 4th 2013, 04:34 PM
issacnewton
Re: checking proof that no natural number can be both even and odd
emakarov

That is a good explanation. I see that I never used the least element of S. I will try to come up with some other argument for this.

thanks