# linear order in a group of functions

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?

• 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

## 1 Answer

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

• 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