Suppose $g$ is a total computable injective function and $f$ is a total computable function satisfying $$g(x)<f(x)$$ for all sufficiently large $x$. Then we have $ran(f)\le\_Tran(g)$; basically, elements enter $ran(f)$ only when "permitted" to do so by $g$, and the injectivity of $g$ prevents this from happening unexpectedly.


It just occurred to me that I don't know if an appropriately-formulated *converse* is true. Suppose $g$ is a total computable injective function with noncomputable range, and $X$ is a noncomputable c.e. set with $X\le\_Tran(g)$. Is there a total computable $f$ outputting *canonical codes for finite sets* with $\bigcup\_{n\in\omega}f(n)=X$ and $g(x)<\min(f(x))$ for all sufficiently large $x$? What if we simply require $\bigcup\_{n\in\omega}f(n)\equiv\_TX$? After looking for a positive proof for a while, I'm starting to suspect that the answer is in fact negative; however, the construction of a counterexample $g, X$ seems a bit difficult.


(I suspect the answer to this question is in Soare's old book somewhere, but I don't have my copy at hand right now.)



Does permission always work?
No, there is a counterexample. The idea is that the use of the computation $X \le\_T ran(g)$ can be much worse than identity, and since we only care about the reduction in one direction, we can drive that use up very large. In contrast, a function $f$ trying to maintain $X \equiv\_T ran(f)$ can't freely increase the use on one side without making changes on the other.


We are building $g$ and $X$, and a basic module must diagonalize against a tuple $(f, \Phi, \Psi, k)$, ensuring that if $f$ is total and $g(y) < \min(f(y))$ for all $y > k$, then it's not the case that $\Phi(X) = \bigcup\_n f(n)$ and $\Psi(\bigcup\_n f(n)) = X$. For ease of notation, let $Z = \bigcup\_n f(n)$.


For this module, we choose large $m\_1 > m\_0$ and enumerate the axiom $m\_0 \not \in X$ with use $m\_1 \not \in ran(g)$. We require that all future definitions of $g$ must use values greater than $m\_1$, and we wait until we see $f$ converge on all $y \le k$ and all $y$ where we have already defined $g(y) < m\_0$. We wait further until we see an expansionary stage: some $s$, $r\_0$ and $r\_1$ with $\Phi\_s(X\_s\upharpoonright r\_0) = Z\_s\upharpoonright r\_1$ and $\Psi(Z\_s\upharpoonright r\_1) = X\_s\upharpoonright m\_0+1$. We pick an $m\_2 > r\_1$, we use our next definition of $g$ to enumerate $m\_1$ into $ran(g)$, and we enumerate the axiom $m\_0 \not \in X$ with use $m\_2 \not \in ran(g)$. We then require that there be no enumerations into $X$ below $r\_0$ and no further definitions of $g$ with values below $r\_1$.


Now, we wait until $f$ converges on all $y$ where we have already defined $g(y) < r\_1$. If $f$ uses any of these values to enumerate a new element into $Z$ below $r\_1$, we then have $\Phi\_s(X\_s\upharpoonright r\_0)$ incompatible with $Z$, so we win by maintaining the restraint on $X$ below $r\_0$.


If $f$ does not take this opportunity to enumerate new elements into $Z$ below $r\_1$, then $f$ will have lost the opportunity to ever again enumerate further elements into $Z$ below $r\_1$ (assuming that our choice of $k$ was correct and we maintain the restraint on $g$). So $Z\upharpoonright r\_1 = Z\_s\upharpoonright r\_1$. Now we enumerate $m\_0$ into $X$ and $m\_2$ into $ran(g)$, giving us $\Phi(Z)(m\_0) = \Phi\_s(Z\_s\upharpoonright r\_1)(m\_0) = 0 \neq X(m\_0)$, so we have won.


Now just arrange these modules into a finite injury priority argument.


