# Even and Odd Natural Numbers

1. Jul 9, 2009

### jgens

1. The problem statement, all variables and given/known data

Prove that every Natural number is either even or odd.

2. Relevant equations

Mathematical Induction
Even: n = 2k where k is an integer
Odd: n = 2k + 1 where k is an integer

3. The attempt at a solution

I think I have a relatively complete proof, however, it doesn't seem quite right (perhaps it's incorrect?). So, any suggestions or comments would be very helpful.

Proof: We define the terms even and odd as follows: A Natural number n is even if it satifies n = 2(j) where jZ. A Natural number n is odd if it satisfies n = 2(j) + 1 where jZ.

Now, let P(x) be the statement that every Natural number is either even or odd. Clearly, we have that n = 1 is odd since if j = 0 then 2(0) + 1 = 1. Additionally, we also have that n = 2 is even since if j = 1 then 2(1) = 2. Now suppose that P(x) is false for some non-empty set of Natural numbers. Since this set is non-empty, by the well-ordering principle it contains a least element n = k + 1. Because 1 and 2 are odd and even respectively and because n = k + 1 is the smallest n such that P(x) is false, we know that P(k) must be true. Therefore, k must either be even or odd. We treat these cases separately.

Case 1: Suppose that k is even, then for some jZ, k = 2(j). Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 1. However, this contradicts our assumption that k + 1 was neither even nor odd.

Case 2: Suppose that k is odd, then for some jZ, k = 2(j) + 1. Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 2 = 2(j + 1). However, this contradicts our assumption that k + 1 was neither even nor odd.

These contradictions prove that our assumption that n = k + 1 was the least n such that P(x) was false was incorrect. Therefore, the set of Natural numbers that are neither even nor odd must be empty and consequently, every Natural number is either even or odd.

Last edited: Jul 10, 2009
2. Jul 10, 2009

### jgens

Thinking back on it, I don't think that I need to prove that 2 is even. Here's the updated proof . . .

Proof: We define the terms even and odd as follows: A Natural number n is even if it satifies n = 2(j) where jZ. A Natural number n is odd if it satisfies n = 2(j) + 1 where jZ.

Now, let P(x) be the statement that every Natural number is either even or odd. Clearly, we have that 1 is odd since if j = 0 then 2(0) + 1 = 1. Hence P(1) is true. Now suppose that P(x) is false for some non-empty set of Natural numbers. Because this set is non-empty, by the well-ordering principle it contains a least element n = k + 1. Since 1 is odd and n = k + 1 is the smallest n such that P(x) is false, we know that P(k) must be true. Therefore, k must be either even or odd. We will treat these cases separately.

Case 1: Suppose that k is even, then for some jZ, k = 2(j). Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 1. However, this contradicts our assumption that k + 1 was not odd.

Case 2: Suppose that k is odd, then for some jZ, k = 2(j) + 1. Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 2 = 2(j + 1). However, this contradicts our assumption that k + 1 was not even.

These contradictions prove that our assumption that P(x) was false for a non-empty set of Natural numbers was incorrect. Therefore, the set of Natural numbers that are neither even nor odd must be empty and consequently, every Natural number is either even or odd. Q.E.D.

3. Jul 10, 2009

### HallsofIvy

Staff Emeritus
I presume you mean that P(x) is the statement that the natural number x is either even or odd. What you give here does not depend on "x" and P(1), P(2), etc. are all the same statement!

That seems a lot more complicated than necessary. Having shown that P(1) is true, I had expected you to just use induction. Suppose P(m) is true. That is, m is either even or odd. Now it is easy to prove that P(m+ 1) is true, thus proving the general statement by induction.

If P(m) is true, then m is either even or odd.

case I: Suppose m is even: m= 2k for some integer m. Then m+ 1= ...

case II: Suppose m is odd: m= 2k+1 for some integer m. Then m+ 1= ...