# Proof about a function from the naturals.

1. Jan 5, 2013

### cragar

1. The problem statement, all variables and given/known data
Prove that there is no function f:N→N such that
for all $n \in N$ , 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. Jan 6, 2013

### micromass

Staff Emeritus
Why?

3. Jan 6, 2013

### cragar

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.

4. Jan 6, 2013

### micromass

Staff Emeritus
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.

5. Jan 6, 2013

### lurflurf

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

6. Jan 6, 2013

### lurflurf

You are onto something though, there does exist a minimum m so that
f(n)>=m
so f cannot continue decreasing

7. Jan 6, 2013

### cragar

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.

8. Jan 6, 2013

### HallsofIvy

Staff Emeritus
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).