Is Every Natural Number Either Even or Odd?

[jgens]

Homework Statement

Prove that every Natural number is either even or odd.

Homework Equations

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

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 j ∈ Z. A Natural number n is odd if it satisfies n = 2(j) + 1 where j ∈ Z.

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 j ∈ Z, 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 j ∈ Z, 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.

 

[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 j ∈ Z. A Natural number n is odd if it satisfies n = 2(j) + 1 where j ∈ Z.

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 j ∈ Z, 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 j ∈ Z, 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.

 

[HallsofIvy]

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 j ∈ Z. A Natural number n is odd if it satisfies n = 2(j) + 1 where j ∈ Z.

Now, let P(x) be the statement that every Natural number is either even or odd.

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!

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 j ∈ Z, 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 j ∈ Z, 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.

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= ...