Newsgroups: sci.math
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 19 Feb 91 21:01:29 GMT
Subject: Re: monotone function problem

ha...@ruuinf.cs.ruu.nl (Hans Zantema) writes:

>Are there two strictly ascending functions (i.e. m>n => f(m)>f(n)) f and g
>from natural numbers to natural numbers for which
>    f(g(n)) > g(f(f(n)))         (*)
>for all natural numbers n?

pmont...@euphemia.math.ucla.edu (Peter Montgomery) writes:

>No. [...]
>When k = 0, this reduces to g(n) >= n and follows from the monotonicity
>of g.

gate...@rice.edu (John Gateley) writes:

>This is wrong, g(n) >= n does NOT follow from monotonicity.

It does, hoewever, follow from being a monotonic function from natural
numbers to natural numbers.

>There are two functions:
>f(n)=n-1
>g(n)=n-1
>They are monotonic: for all n1>n2, f(n1)=n1-1>n2-1=f(n2).
>And, f(g(n))=n-2, g(f(f(n)))=n-3.

But they map the least natural number to some number that is not
natural, so they do not address this problem.

Dan