Prove that every natural number is either odd or even

In summary: 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-1Theorem: 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 \
  • #1
Hobold
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:
Physics news on Phys.org
  • #2
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
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
"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
Hobold said:
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
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
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
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
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
CRGreathouse said:
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.
 

1. What does it mean for a number to be "odd" or "even"?

A number is considered "odd" if it is not divisible by 2, meaning it has a remainder of 1 when divided by 2. A number is considered "even" if it is divisible by 2, meaning it has no remainder when divided by 2.

2. Can a number be both odd and even?

No, a number cannot be both odd and even. Every number falls into one of these categories.

3. How can you prove that every natural number is either odd or even?

This can be proven using the fundamental theorem of arithmetic, which states that every natural number can be expressed as a unique product of primes. Since 2 is the only even prime number, any number that is not divisible by 2 must be a product of odd primes, making it an odd number.

4. Are there any exceptions to this rule?

No, there are no exceptions to this rule. Every natural number can be classified as either odd or even.

5. Why is it important to understand the concept of odd and even numbers?

Understanding odd and even numbers is important in many mathematical concepts, such as fractions, decimals, and algebra. It also helps in solving problems and patterns in number sequences.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
501
  • Calculus and Beyond Homework Help
Replies
3
Views
545
  • Precalculus Mathematics Homework Help
Replies
4
Views
4K
  • Precalculus Mathematics Homework Help
Replies
2
Views
795
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
495
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
808
Back
Top