Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Natural Numbers Proof?

  1. Apr 6, 2012 #1
    If 'n' is a natural number such that n>1, prove that there exists a natural number k such that n-k=1.

    It raises the question: What is the definition of a natural number?

    Could you say that because n is natural, n-1 must be natural so that if k = n-1, n-k = 1?

    BiP
     
  2. jcsd
  3. Apr 6, 2012 #2
    That seems like a good argument, just mention that n-1 > 0 since n > 1.

    As for the definition of "natural number", they simply the positive integers. So, n-1 is natural because a)n is natural so n-1 is an integer and b)b>1 so n-1 >0
     
  4. Apr 6, 2012 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This is actually a surprisingly difficult question. Of course, it's very easy on the first glance. But if you want to work it out fully from the very definition of natural numbers, then it can be difficult.

    There are two common definitions of natural numbers.

    1) The Peano-axioms.
    Natural numbers are a triple (N,s,0) with N a set,[itex]s:N\rightarrow N[/itex] a function (intuitively s(n)=n+1) and 0 an element of N such that
    - there exists no x in N such that s(x)=0
    - if s(x)=s(y) then x=y
    - induction: if [itex]A\subseteq N[/itex] is a set such that [itex]0\in A[/itex] and such that if [itex]x\in A[/itex] than [itex]s(x)\in A[/itex], then A=N

    From these axioms, you can reconstruct the theory of natural numbers. In particular you can prove the question in the OP. It is not that easy, however.

    2) The set-theoretic definition.
    We define
    [itex]0=\emptyset[/itex]
    [itex]1=\{0\}[/itex]
    [itex]2=\{0,1\}[/itex]
    [itex]3=\{0,1,2\}[/itex]
    [itex]4=\{0,1,2,3\}[/itex]
    and so on. (this needs to be made rigorous)

    The set of all such sets is called the natural numbers. This satisfied the Peano-axioms with [itex]s(n)=n\cup \{n\}[/itex]. The advantage here is that there is a unique set of natural numbers. In the first approach, there could be many such sets (which are homeomorphic). Another advantage is that induction is no longer an axiom, but can be proven from the set theoretic axioms. This might be preferable as induction might not be so intuitive to be taken an axiom.
     
  5. Apr 6, 2012 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    If you want a proof from basic definitions, that's a long proof!

    One way to define the "natural numbers" is to use the Peano axioms:

    The natural numbers consist of a set N, together with a function, s (called the "successor function") from N to N such that
    1) There exist a unique member of N, called "1" such that s is a one-to-one function from N to N-{1}. (In other words, every natural number has a successor, every natural number except 1 is the successor of some natural number.)
    2) If X is a set of natural numbers such that 1 is in X and, whenever n is in X so is s(n), then X is the set of all natural numbers. (This is the "induction axiom.)

    We can define ">" by "m> n if and only if there exist a natural number x such that x+ n= m.

    From there we can define "m+ n", for m and n natural numbers, by
    1) 1+ n= s(n).
    2) if [itex]m\ne 1[/itex], then there exist x such that m= s(x) and we define
    m+ n= s(x+ n).

    One needs to show that is "well defined". That is, that given any m,n in N, there exist a unique member of N equal to m+n.

    Once we have that, we can define n- m as the unique number, x, such that m+ x= n.

    Now, if n> 1, by definition of ">", there exist k such that k+1= n and therefore, n- k= 1.

    (micromass got in ahead of me again!)
     
  6. Apr 7, 2012 #5
    How can we prove induction from the set theoretic axioms? sounds very interesting.
     
  7. Apr 7, 2012 #6


    What "set theoretic axioms"?? The Principle of Induction is equivalent, under the usual axioms of arithmetic, to the well (natural) ordering of the set of the natural numbers...is this what you meant?

    DonAntonio
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Natural Numbers Proof?
  1. Natural numbers Z? (Replies: 6)

Loading...