Proof about a function from the naturals.

[cragar]

Homework Statement

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.

The Attempt at a Solution

Let's 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.

 

[micromass]

There exists some x in N such that f(x) equals the first natural number.

Why?

 

[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.

 

[micromass]

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.

 

[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

 

[lurflurf]

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

 

[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.

 

[HallsofIvy]

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