Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $A$ be the smallest set of the following functions on the positive reals:

  • The identity function is in $A$,
  • for a function $f\in A$ also the inverse $f^{-1}$ is in $A$,
  • for two functions $f,g\in A$ also the sum $f+g$, the product $f\cdot g$ and the composition $f\circ g$ is in $A$.

In each generation the following properties are conserved: each function is strictly increasing and maps the positive reals surjectively to the positive reals. That's why we always can take the inverse above. The set $A$ is a group with respect to the composition operation.

The set $A$ contains all the polynomials with positive integer coefficients and zero constant term. Each non-trivial polynomial has finitely many fixpoints. Having finitely many fixpoints also implies being linearly orderable by "orders of infinity" (Hardy), i.e. by $f<_\infty g$ if there is an $x_0$ such that $f(x)\lt g(x)$ for all $x\gt x_0$ .

Do all the functions of $A$, except the identity function, have finitely many fixpoints?

share|improve this question
    
I guess you mean that the set $A$ contains all the polynomials with positive integer coefficients and zero constant term (since clearly every function in $A$ maps $0$ to $0$). And of course you want to exclude the identity function in your final question :-) –  Tom De Medts Apr 1 '11 at 9:05
    
ya sure. I correct it accordingly. –  bo198214 Apr 1 '11 at 9:49
    
Note that all functions in $A$ are analytic; in particular, the set of fixpoints of a non-identity function in $A$ cannot have an accumulation point. –  Tom De Medts Apr 1 '11 at 10:26
add comment

1 Answer

up vote 8 down vote accepted

Yes. Every function $f\in A$ is definable by a first-order formula in the structure $(\mathbb R,+,\cdot,\le)$. It follows that the set $F$ of its fixpoints is also definable. Since the structure is o-minimal, $F$ is a finite union of intervals (possibly degenerate). (The o-minimality follows from the Tarski–Seidenberg theorem: $\mathbb R$ admits elimination of quantifiers in the language of ordered rings, hence every definable set is a Boolean combination of sets defined by $p(x)\ge0$ for some polynomial $p\in\mathbb R[x]$.) Moreover, every $f\in A$ is an analytic function, and so is $f(x)-x$, hence if $F$ contains a nondegenerate interval, it contains the whole of $\mathbb R^+$, and $f$ is the identity. Otherwise, $F$ only contains degenerate intervals, i.e., it is finite.

The same property will hold if you also include in $A$ all functions $ax$, where $a\in\mathbb R^+$, and the exponential function (modified so that the property of being increasing and mapping $\mathbb R^+$ onto itself is maintained, e.g., $e^x-1$). (The o-minimality of the real field with exponentiation is a result of Alex Wilkie.)

Note that if you are only interested in the functions’ being linearly ordered by $<_\infty$, you don’t need the number of fixpoints to be finite, it suffices if they are bounded, and o-minimality gives this right away. That is, if you have any collection $A$ of functions $f\colon(a_f,+\infty)\to\mathbb R$, each of which is first-order definable in $(\mathbb R,+,\cdot,\exp,\le)$ with parameters (but they do not have to be injective, continuous, or anything like that), then for every $f,g\in A$, either $f<_\infty g$ or $f=_\infty g$ or $g<_\infty f$.

share|improve this answer
    
So due to the result of Alex Wilkie also the following set $E$ of bijections of $\{x\colon x>1\}$ would only contain functions with finitely many fixpoints (except the identity function)? - identitiy function is element of $E$ - for each function also the inverse function is in $E$ - for each two functions $f,g$ also $f^g$ and $f\circ g$ is in $E$ –  bo198214 Apr 1 '11 at 18:52
    
@bo198214: Yes, that's right. –  Emil Jeřábek Apr 2 '11 at 12:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.