I would like to know if a function with the following conditions can exist or not. f must be a total function (not necessarily recursive) such that the following 3 conditions are satisfied:
f is strictly increasing,
Img(f) is recursively enumerable,
Any total recursive function is eventually dominated by f (i.e. if g is a total recursive function, there is some n such that f(m)> g(m) for all m> n).
In order to satisfy 1,3 I went to the usual construction using a diagonal computable in 0^{'}, but I am pretty sure that the image of such a function cannot be r.e. (or my final arithmetic description used more quantifiers...). Even though, that construction is the only one that I know to dominate the recursive functions... thus perhaps there is something else that one can do. Is the existence of such a function possible? If it is, how one can construct it?
There is no such function.
Claim: Any infinite r.e. set A contains the range of a computable strictly increasing function.
Proof: Just take an effective enumeration of A, and skip the elements encountered that are smaller than previously encountered ones. Each time, we only skip finitely many before being able to compute the next value, so there is no problem.
Claim: If $Im(f) \subseteq Im(g)$, and $f$ and $g$ are strictly monotone, then $g$ is eventually dominated by $f$.
Proof: $f$ can only skip some values of $g$, hence grows even faster.
Proof of the main statement: From a function satisfying all three of your criteria we would obtain a computable function eventually dominating all computable functions, contradiction.