Prove that every natural number is either odd or even

[Hobold]

Hello people.

I'm a freshman in college and I'm looking forward to enter an advanced mathematics program. The admission test is basically number theory & sometimes I get stuck with some questions (I'm using Spivak's Calculus to study).

I'm stuck on question 8, chapter 2.

"Prove that every natural number is either odd or even."

I've come to a solution though I don't think it is right and it doesn't seem very elegant. I'm doing this by induction.

Let X be a non-empty set of natural numbers that are not even or odd.

Let A an specific set of natural numbers that are not odd, so they must be even.

An specific number n is even if, and only if, it satisfies the equation n=2k,~ \forall k \in \mathbb{Z} and odd if, and only if, it satisfies the equation n=2k +1 ,~ \forall k \in \mathbb{Z}

So if A is a non-empty set, it must have a smallest number y=2x,~ \forall x \in \mathbb{Z}

A(x) = 2x
A(x) + 1 = 2x + 1

This way, we proved that the first natural number following an even is odd.

Let B be an specific set of natural numbers that are not even, so it must be odd.

So if B is a non-empty set, it must have a smallest number i=2j +1,~ \forall j \in \mathbb{Z}

B(j) = 2j +1
B(j) + 1 = 2j + 2 = 2(j+1)

Therefore, the smallest natural number after an odd is even. So A \cup B = \mathbb{N} therefore X = \varnothing, which contradicts a previous statement, therefore every natural number is either odd or even.

 

[Petek]

Let A an specific set of natural numbers that are not odd, so they must be even.

With this statement you are, in effect, assuming what you're trying to prove. In other words, you're saying that if a natural number is not odd, then it must be even. I think, however, that you can "rescue" this proof. Try this: Let A be the set of all natural numbers that are neither odd nor even and suppose that A is nonempty. Let n be the smallest element of A. Then ... .

Try to finish the proof from here. You should be able to arrive at a contradiction. Please post again if you'd like additional hints.

Petek

 

[mathman]

It is a strange question. What are the precise definitions of even and odd that you are using?

Usually, even means divisible by 2, while odd means not divisible by 2. From this definition there is nothing to prove.

 

[g_edgar]

"even" means of the form 2n, "odd" means of the form 2n+1. So proving every natural number is either even or odd has some content.

Proof by induction (or well-ordering) is the way to go, but as noted the proof given by the OP is flawed.

Suppose there is a natural number n that is neither even nor odd. Consider n-1 ... there are three possibilities for n-1 that must be eliminated ... Can you continue?

 

[Landau]

An specific number n is even if, and only if, it satisfies the equation n=2k,~ \forall k \in \mathbb{Z} and odd if, and only if, it satisfies the equation n=2k +1 ,~ \forall k \in \mathbb{Z}

This is absurd. There is no n that satisfies n=2k FOR ALL k! You meant THERE EXISTS k such that n=2k, i.e. you confused the existential and universal quantifiers.

Induction is indeed the way to go, but I would do it slightly different than g_edgar. Assume that for some k, we have that k is either even or odd. We want to prove that k+1 is either even or odd. Now, for k there are two possibilities: k=2n, or k=2m+1 (for some natural numbers n,m). In both cases, consider k+1, and finish the proof.

 

[Gib Z]

Is this one valid?

Define S to be the set of all natural numbers that are neither even or odd, and assume it is non empty. Every subset of the natural numbers must have a least element; let this element be s. Consider s-2. s-2 can not be of the form 2n, because then s= 2n+2 = 2(n+1) for some natural number n, ie even, which it can not be. So s-2 is not even. s-2 can not be of the form 2n+1 either, as s would be 2(n+1) + 1, which it can not be. So then s-2 is neither even nor odd, so is in the set S. But s-2 is less than s, and s was defined the be the least element. Contradiction.

 

[Landau]

Looks good. One detail: you should notice that s>2, so that s-2>0, otherwise s-2 would be negative and hence not in S which gave you the contradiction. Of course, s>2 because 1 and 2 are even or odd.

 

[Hobold]

Thanks for posting, people, it's nice to see other solutions. I've come to a new one. Is this correct?

---

Definition: A natural number n is:

(i) even,if \exists ~ m \in \mathbb{N} ~\text{for which}~ n=2m
(ii) odd,if \exists ~ m \in \mathbb{N} ~\text{for which}~ n=2m-1

Theorem: Every natural number is either odd or even.

Demonstration: Let A = \{ n \in \mathbb{N} :~ \text{n is odd or n is even}~ \}

1 = 2\cdot 1 - 1 \therefore~ \text{1 is odd}~ \therefore 1 \in A

Suppose p \in A, we have two possibilities:

(a) p is even, \therefore p=2m~ \text{for some}~ m\in \mathbb{N} \therefore p +1 = 2m+1 = 2(m+1)-1 \in \mathbb{N} \therefore p+1~ \text{is odd}~ \therefore p+1 \in A

(b) p is odd, \therefore p=2m-1~ \text{for some}~ m\in \mathbb{N} \therefore p +1 = 2m-1+1 = 2m \in \mathbb{N} \therefore p+1~ \text{is even}~ \therefore p+1 \in A

\therefore by induction A = \mathbb{N}

 

[CRGreathouse]

Steps a and b use N instead of A in several places, and you don't say "by induction" which makes the final step slightly unclear. But the basic idea is right.

 

[Hobold]

Steps a and b use N instead of A in several places, and you don't say "by induction" which makes the final step slightly unclear. But the basic idea is right.

Thanks, edited a little so things make more sense.