Does permission always work?

Question

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

Answer 1

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.

Answer 2

Dan's answer is very nice and should be the accepted answer. However, I thought it might be worth pointing out that there's a much easier counterexample to your first question (with the stricter requirement that $X = \bigcup_{n \in \mathbb{N}}f(n)$). Namely, we can let $g$ be any total computable injective function which enumerates a non-computable c.e. set and then just take $X$ to be the range of $g$ itself.

Here's why. Suppose $f$ is a total computable function with the properties listed in the question. Note that by modifying $f$ we can assume that for all $n > 0$, $g(n) < \min(f(n))$ (rather than all sufficiently large $n$). We can do this by resetting $f(n)$ to be $f(n) \cap \mathbb{N}_{> g(n)}$ and then setting $f(0)$ to consist of all missing values.

We can now compute $X$ (by computing the true stages of $g$) as follows.

1. Set $n_0$ to be the minimum element of $f(0)$. Note that this must actually be the minimum element of $X$: due to the restriction on $f$ and $g$, $f$ cannot enumerate the least element of $X$ on any later stage.
2. Let $m_0$ be the point at which $g$ enumerates $n_0$ and set $n_1$ to be the second least element of $f(0)\cup f(1)\cup \ldots \cup f(m_0)$. Note that $n_1$ must be the second least element of $X$.
3. And so on. This results in a computable increasing enumeration $n_0, n_1, \ldots$ of $X$, hence $X$ is computable.

Note that even if you change the requirement in your question to $g(n) \leq \min(f(n))$, this proof can easily be adapted by taking $X$ to be the range of $g - 1$.