# Does permission always work?

Suppose $$g$$ is a total computable injective function and $$f$$ is a total computable function satisfying $$g(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.)

• I think you meant to write $g(x) < f(x)$ in the first sentence of your post (rather than $f(x) < g(x)$). May 9 at 5:40
• Also I think that once you make this correction, at least one of your questions has a fairly obvious answer: if $X$ is much denser than $\text{range}(g)$ then it is not possible to enumerate $X$ with a function $f$ such that $f(x) > g(x)$ for all $x$. May 9 at 5:44
• @PatrickLutz Ah, sorry - quite right on both counts! I meant to allow $f$ to enumerate finitely many elements at once (via a canonical code for a finite set). Fixed! May 9 at 5:49
• Sometimes it's easier to ask for forgiveness than to wait for permission. Does that help? May 9 at 8:13

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.

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