1. Not finding help here? Sign up for a free 30min 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!

Proof about a function from the naturals.

  1. Jan 5, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that there is no function f:N→N such that
    for all [itex] n \in N [/itex] , f(n)>f(n+1).
    There is no infinite decreasing sequence of naturals.
    3. The attempt at a solution
    Lets assume that their is a function f(n)>f(n+1) for all n.
    This would also imply that f(n) will be mapped to all of N using all n in N.
    There exists some x in N such that f(x) equals the first natural number.
    if f(x) gets mapped to the first natural then f(x+1) gets mapped to some natural.
    This is either the first natural or some larger natural. But this is a contradiction
    because we assumed that f(n)>f(n+1). so therefore no function exists.
     
  2. jcsd
  3. Jan 6, 2013 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Why?
     
  4. Jan 6, 2013 #3
    We are assuming that their is a function f that maps
    N to N. so their must exist an x in N so that f(x) equals the first natural number.
    I guess this is something we are assuming.
     
  5. Jan 6, 2013 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I don't see in the problem statement that f is supposed to be surjecive. So I don't think you can assume that anything maps to the first natural number.
     
  6. Jan 6, 2013 #5

    lurflurf

    User Avatar
    Homework Helper

    No f:N→N does not mean the function is "onto"
    just suppose
    f(1)=a
    there are a-1 smaller natural numbers so one of the a numbers
    f(2),f(3),f(4),...,f(a-2),f(a-1),f(a),f(a+1)
    must not be
    not to mention all higher terms
     
  7. Jan 6, 2013 #6

    lurflurf

    User Avatar
    Homework Helper

    You are onto something though, there does exist a minimum m so that
    f(n)>=m
    so f cannot continue decreasing
     
  8. Jan 6, 2013 #7
    ok thanks for the replies. So I just assume their exists an x such that
    f(x)=a where a is the smallest element. then f(x+1) either gets mapped to
    a or something larger than a which is a cont-radiation.
     
  9. Jan 6, 2013 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes. You might want to specifically mention the "well-ordering principle": every subset of N has a smallest member. Let a be the smallest member of the image of N under function f. There exist some x in N such that f(x)= a. Then look at f(x+1).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof about a function from the naturals.
Loading...