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?

  • $\begingroup$ 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 :-) $\endgroup$ Apr 1, 2011 at 9:05
  • $\begingroup$ ya sure. I correct it accordingly. $\endgroup$
    – bo198214
    Apr 1, 2011 at 9:49
  • $\begingroup$ 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. $\endgroup$ Apr 1, 2011 at 10:26

1 Answer 1


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

  • $\begingroup$ 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$ $\endgroup$
    – bo198214
    Apr 1, 2011 at 18:52
  • $\begingroup$ @bo198214: Yes, that's right. $\endgroup$ Apr 2, 2011 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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