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!

Homework Help: 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?
     
  22. Apr 28, 2012 #21
    One of the properties I gave was "if a and b in P, then a*b is also in P", and so if a*a in P for any a ≠ 0 (as shown in previous post), then a*a - 0 is in P, and by definition a*a > 0. Since 1*1 = 1 and 1*1 > 0 then 1 > 0.


    To prove this I depend on the fact that 1 > 0 as proved previously.

    Considering that 1 > 0, that is 1 - 0 in P, then
    (1 - 0) + 0 in P
    (1 - 0) + (x + -x) in P, and so
    (1 + x) - (x + 0) is in P
    1 + x > x
     
  23. Apr 28, 2012 #22

    I like Serena

    User Avatar
    Homework Helper

    Okay.
    That looks correct.

    Let me give a shorter version.
    We have: "a > b" is defined as "a - b in P".

    Now fill in a=x+1, and b=x, then we get:
    (x+1)-x=-x + (x+1)=(-x+x)+1=0+1=1, which is in P.
    So x+1 > x.

    In particular we have 0<1.
    How about other numbers?
    Say we pick a number y.
    What are the possibilities relative to 0 and 1?

    Note that ">" has a transitive property.
    Oh wait. You did not mention the properties of an inequality yet...
     
  24. Apr 28, 2012 #23
    Sorry, but I don't understand how is this "shorter". It looks exactly the same, since you depend on the fact that 1 is in P to conclude that (x+1)-x = 1 is in P.

    Since 1 in P is the same as 1-0 in P, that is 1 > 0, then we need to prove first that 1 > 0.

    The way you wrote it, looks like that you started with (x + 1) - x in P and than concluded as a specific case that 1 in P. Maybe I misunderstood it?

    Anyway, regarding transitivity of the >, I can say the following.

    If a-b in P and b-c in P, then (a-b) + (b-c) in P, and therefore (a-c) in P.

    And I still don't get it. Don't know what to say about any number y. A number y could be equal to 0, 1, 0 < y < 1, above 1, or below 0.

    I'm a little lost in all this, but I'm trying to follow your reasoning (and having some fun doing it!). More hints please? :)
     
  25. Apr 28, 2012 #24

    I like Serena

    User Avatar
    Homework Helper

    If I understood you correctly the definition of "a>b" is based on the set P.
    I am assuming that all natural numbers are in the set P.

    You seem to use ">" to deduce that a number is in P, but that would be a circular argument.


    I believe we decided that the natural numbers consist of 1 and multiple addititions of 1 to it.
    Did we?

    If we did than 1<1+1<1+1+1<...
    Any natural number y must be one of these numbers.
    By transitivity, y is either 1,2, or a bigger number.
    In particular it cannot be a number between 1 and 2, because it has to be one of these other numbers.
     
  26. Apr 28, 2012 #25

    jgens

    User Avatar
    Gold Member

    If you really want a definition of the natural numbers and integers in [itex]\mathbb{R}[/itex], then this definition is adequate: Define a set [itex]A[/itex] to be inductive if and only if [itex]1 \in A[/itex] and [itex]k+1 \in A[/itex] whenever [itex]k \in A[/itex]. Let [itex]\mathbb{N}[/itex] be the intersection of every inductive subset of [itex]\mathbb{R}[/itex] and let [itex]\mathbb{Z} = \mathbb{N} \cup \{0\} \cup -\mathbb{N}[/itex]. You will have to go through some work to show that these sets have the desired properties, but if you are insistent on a definition of [itex]\mathbb{N}[/itex], then this suffices.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook