Prove that every natural number is either odd or even

  • Thread starter Hobold
  • Start date
  • #1
83
1
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 [tex]n[/tex] is even if, and only if, it satisfies the equation [tex]n=2k,~ \forall k \in \mathbb{Z}[/tex] and odd if, and only if, it satisfies the equation [tex]n=2k +1 ,~ \forall k \in \mathbb{Z}[/tex]

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

[tex]A(x) = 2x [/tex]
[tex]A(x) + 1 = 2x + 1[/tex]

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 [tex]i=2j +1,~ \forall j \in \mathbb{Z}[/tex]

[tex]B(j) = 2j +1[/tex]
[tex]B(j) + 1 = 2j + 2 = 2(j+1)[/tex]

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

Answers and Replies

  • #2
Petek
Gold Member
363
8
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
 
  • #3
mathman
Science Advisor
7,898
461
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.
 
  • #4
607
0
"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?
 
  • #5
Landau
Science Advisor
905
0
An specific number [tex]n[/tex] is even if, and only if, it satisfies the equation [tex]n=2k,~ \forall k \in \mathbb{Z}[/tex] and odd if, and only if, it satisfies the equation [tex]n=2k +1 ,~ \forall k \in \mathbb{Z}[/tex]
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.
 
  • #6
Gib Z
Homework Helper
3,346
5
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.
 
  • #7
Landau
Science Advisor
905
0
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.
 
  • #8
83
1
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 [tex] \exists ~ m \in \mathbb{N} ~\text{for which}~ n=2m[/tex]
(ii) odd,if [tex] \exists ~ m \in \mathbb{N} ~\text{for which}~ n=2m-1[/tex]

Theorem: Every natural number is either odd or even.

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

[tex]1 = 2\cdot 1 - 1 \therefore~ \text{1 is odd}~ \therefore 1 \in A[/tex]

Suppose [tex]p \in A[/tex], we have two possibilities:

(a) p is even, [tex]\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[/tex]

(b) p is odd, [tex]\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[/tex]

[tex]\therefore[/tex] by induction [tex] A = \mathbb{N}[/tex]
 
Last edited:
  • #9
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 
  • #10
83
1
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.
 

Related Threads on Prove that every natural number is either odd or even

Replies
4
Views
3K
  • Last Post
Replies
23
Views
11K
Replies
18
Views
16K
  • Last Post
Replies
22
Views
6K
  • Last Post
Replies
9
Views
3K
Replies
1
Views
3K
Replies
1
Views
2K
Replies
3
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
10
Views
14K
Top