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)

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~?$

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 ?

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?

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 ?

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.

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