1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that every natural number is either even or odd.

  1. Apr 28, 2012 #1
    Hello,

    I'm re-studying calculus using Spivak's Calculus 4ed and I'm stuck in one of the problems. Any help is appreciated.

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

    The theorem to prove is "every natural number is either even or odd".

    The definition of even given by Spivak is the following: A natural number n is even if there exists an integer k such that n = 2k. Similarly, for an odd natural number n, there exists an integer k such that 2 = 2k+1.

    I can also use the basic facts about natural numbers and integers, such as associativity, commutativity, existence of identity, and distributivity.

    The other property of the natural numbers I can use is the principle of mathematical induction.

    2. The attempt at a solution

    First, my understanding of the "either or" is that I must prove that every natural n is even or odd _and not both_. A general argument by induction will look like:
    • The number 1 is odd because there exists a k = 0, such that 2*0 + 1 = 1
    • Suppose n is either even or odd. If even then there exists a k such that n = 2k, and n+1 = 2k+1 and so, n+1 is odd. The case for n odd is similar. And so, if n is even or odd, then n+1 is even or odd.
    By the principle of mathematical induction, all natural numbers are even or odd.

    The problem (one of the problems?) with this proof is that I don't show that a natural number can't be even and odd at the same time.

    I can't even start to show that 1 is not even. I need to prove that there are no integer k such that 1 = 2k. I understand that the only "number" that satisfy the equation is 1/2 and 1/2 is not an integer, but I can't state that in a proof with the principles that were given.

    Any help? :)

    Thanks!
     
  2. jcsd
  3. Apr 28, 2012 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Are you allowed to use inequality properties? For example if a>b and c>0 then ac>bc. Then i 2k>2 if k is a positive integer (and if k is negative 2k<0)
     
  4. Apr 28, 2012 #3
    Yes, I can use inequality properties: a number n is positive, n = 0, or -n is positive; if n and m are positive then n+m and n*m are also positive. The example you give was proved from the previous properties and so I can use that and similar properties too.

    Following your example with the 2k>2, let me try to use it.

    So, to show that 1 is not even, I assume that if 1 is even then there exists a k such that 2k = 1. Now I have three cases:
    a) If k = 0, then 2k = 0 (already proven) and 0 ≠ 1 and so I get a contradiction.
    b) if k > 0, then 2k > 2 and 2 > 1, so 2k> 1, and so 2k ≠ 1.
    c) if k < 0, similar to the previous case.
    By contradiction, there is no integer k such that 2k = 1, and so 1 is not even.

    Is this correct?

    EDIT: this doesn't seem correct. I can't show that if k > 0, then 2k > 2.

    Now I'm not sure if showing that 1 is odd and not even is enough to prove the general case. In the induction step, I'm assuming that n is either even or odd. When even, I show that n+1 is odd but I don't prove that n+1 is not even.
     
    Last edited: Apr 28, 2012
  5. Apr 28, 2012 #4

    I like Serena

    User Avatar
    Homework Helper

    Assume there is a number x that is both even and odd.

    So there must be a k with x=2k, and also an m with x=2m+1.
    That is, 2k=2m+1

    Can you rewrite this?
    And use inequalities?
    (No induction necessary.)
     
  6. Apr 28, 2012 #5
    I can rewrite it as 2(k-m) = 1 and make a similar argument as in the post above.

    If k-m = 0, then 2(k-m) = 0
    if k-m < 0, then 2(k-m) < 0
    The problem is with k-m > 0. 2(k-m) > 0 and 1 > 0 so everything looks fine and I don't get a contradiction. I'm missing something. :\
     
  7. Apr 28, 2012 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    k isn't just positive, it's also an integer, so k>=1.

    EDIT: Similar argument finishes up what you want in your previous post
     
  8. Apr 28, 2012 #7
    Sorry, but I don't know how to prove that if k > 0 and k is an integer, then k >= 1. I don't see how can I show that there aren't integers between 0 and 1.
     
  9. Apr 28, 2012 #8

    I like Serena

    User Avatar
    Homework Helper

    What kind of definition do you have for an inequality?
    And how are your whole numbers defined?

    I expect something like x < x + 1 for any x.
    And that the whole numbers are 1 plus a repeated number of additions of 1, combined with 1 plus a repeated number of subtractions of 1.

    This means that any number is less than x, equal to x, equal to x+1, or greater than x+1.
    So there is no number between x and x+1.
     
  10. Apr 28, 2012 #9
    Hello,

    I have the following three basic properties regarding inequalities:
    1. Trichotomy law. For every number a, one and only one of the following holds:
    • a = 0
    • a is in collection of positive numbers P
    • -a is in collection of positive numbers P
    2. If a and b are in P, then a + b is in P
    3. If a and b are in P, then a * b is in P

    The "a > b" is defined as "a - b in P".

    I have no additional information about the "construction" of numbers, only the basic properties they respect. If I understood your question correctly, the numbers aren't defined starting with 1 and then adding 1's like in natural numbers. I don't think numbers are defined beyond the properties they respect.

    Besides the three properties above, I have:
    a + (b + c) = (a + b) + c
    a + b = b + a
    a + 0 = a
    a + (-a) = 0 (this one doesn't apply to natural numbers)
    a*(b*c) = (a*b)*c
    a*b = b*a
    a*1 = a
    1 ≠ 0
    a*a^-1 = 1 for a ≠ 0 (this property doesn't apply to integers, obviously).
    a(b + c) = ab + ac

    I also have the principle of mathematical induction/well-ordering principle for natural numbers and that's it.

    EDIT: removed comment about my whole numbers.
     
    Last edited: Apr 28, 2012
  11. Apr 28, 2012 #10

    I like Serena

    User Avatar
    Homework Helper

    Your definitions allow real numbers.
    But the term "natural number" means that it is a whole number,which is not negative (and may be zero depending on your definition).

    Now I'm confused. :confused:
    Are we talking real numbers, whole numbers, or natural numbers?
    When you mentioned well-ordering you were again talking about natural numbers and your problem statement also refers consistently to natural numbers...
     
  12. Apr 28, 2012 #11
    Sorry, I misunderstood you when you said "whole numbers". You were referring to the integers. Ignore my comment "My "whole numbers" are the real numbers and so," and consider the rest. I remove that from the previous post.
     
    Last edited: Apr 28, 2012
  13. Apr 28, 2012 #12

    I like Serena

    User Avatar
    Homework Helper

    Sorry, I referred to whole numbers (integers) and gave a definition for that, when I should have defined the natural numbers.

    Just to be clear, should we ignore every reference to the word "natural" in your problem statement, and just read "number" wherever it says "natural number"?
    Or else, what is your definition of a natural number?
     
    Last edited: Apr 28, 2012
  14. Apr 28, 2012 #13
    No, in fact the problem is about natural numbers. Prove that a natural number is either even or odd. Sorry about the confusion. I have no definition for natural number besides the properties they respect.

    Quoting Spivak
    "The simplest numbers are the "counting numbers"
    1,2,3,....
    The fundamental significance of this collection of numbers is emphasized by its
    symbol N (for natural numbers). A brief glance at P1-P12 will show that our
    basic properties of "numbers" do not apply to N—for example, P2 and P3 do not
    make sense for N. From this point of view the system N has many deficiencies."

    The properties P1-P12 are the ones I gave above. P2 and P3 are specifically the 0 identity (since the naturals are defined in this book starting with 1) and the -a inverse existence.
     
  15. Apr 28, 2012 #14

    I like Serena

    User Avatar
    Homework Helper

    Well, I don't have Spivak, but if I understand correctly he defines the natural numbers as the numbers 1,2,3,...
    In particular that is 1, and counting up by adding 1 every time (although he doesn't explicitly say so).

    In particular the trichotomy law is not entirely well defined in this case, since -a is not defined for natural numbers.
    And also your definition of "a > b" is not well defined, since a-b does not exist within the natural numbers.
     
    Last edited: Apr 28, 2012
  16. Apr 28, 2012 #15
    I guess you are right. But I must add that the even definition talks about integer numbers also, namely, a natural number n is even if there exists _an integer k_ so that n = 2k. So I think I can use the trichotomy law for the integer 'k' in this definition. Maybe this isn't enough anyway.
     
  17. Apr 28, 2012 #16

    I like Serena

    User Avatar
    Homework Helper

    It's enough as far as I'm concerned.

    To get back to your problem (now that the definition stuff is out of the way), I believe the last thing you needed is that if k-m>0, that then also k-m≥1...
     
  18. Apr 28, 2012 #17
    Let me restate the argument from the beginning. If an integer n is even then there is an integer k so that n = 2k. Also, if n is odd then there is an integer m so that n = 2m+1.

    Now, if that is true then 2k = 2m+1 and so 2(k-m) = 1.

    When (k-m)<= 0, I can easily get a contradiction.
    When (k-m) > 0 and (k-m) being an integer, let me assume for now that k-m >= 1 (I don't know how to prove this yet).
    If (k-m) ≥ 1 then 2(k-m) ≥ 2 and 2 > 1 so 2(k-m) > 1 and so 2(k-m) ≠ 1. By contradiction, a number n can't be even and odd.

    I believe this is correct but I can't see how to get the "if k-m>0 and (k-m) is an integer, then (k-m)≥1".
     
  19. Apr 28, 2012 #18

    I like Serena

    User Avatar
    Homework Helper

    Good! :)

    What you need is that ...<-1<0<1<2<3<...
    From this inequality it follows that there can be no integers between 0 and 1.

    Can you proof that?
     
  20. Apr 28, 2012 #19
    Well, for any number a, if a is positive then a*a > 0 (by definition).
    Also if a < 0, then (-a) > 0 and (-a)*(-a) > 0. Since (-a)(-a) = a*a[1], then a*a > 0.

    So, for any number a ≠ 0, a2 > 0, and in particular 12 = 1 > 0.

    Given that 1 > 0, then -1 < 0. Also 1 + 1 > 0 + 1, that is 2 > 1. Also 1 - 1 > 0 - 1, and so 0 > -1.
    And so ... < -1 < 0 < 1 < 2 < ...

    From here I don't see how can we conclude that there aren't any integers between 0 and 1. Any hints?

    --

    [1] For any numbers a, b
    ab + a(-b) = a(b + -b) = a*0 = 0
    ab + a(-b) = 0
    -(ab) + ab + a(-b) = -(ab)
    a(-b) = -(ab)

    And also, for any numbers a, b

    (-a)(-b) + a(-b) = (-a + a)(-b) = 0(-b) = 0
    (-a)(-b) + -ab = 0 (using previous result)
    (-a)(-b) + (-ab) + ab = ab
    (-a)(-b) = ab
     
  21. Apr 28, 2012 #20

    I like Serena

    User Avatar
    Homework Helper

    You've lost me there.

    You wrote: "a > b" is defined as "a - b in P".

    So where do all your products factor in?
    There's only addition (actually subtraction) involved as far as I can tell.

    Let's start with x+1>x (for any integer x).
    Can you proof that?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook