7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I think you meant to write $g(x) < f(x)$ in the first sentence of your post (rather than $f(x) < g(x)$). $\endgroup$ May 9 at 5:40
  • $\begingroup$ 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$. $\endgroup$ May 9 at 5:44
  • 1
    $\begingroup$ @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! $\endgroup$ May 9 at 5:49
  • 2
    $\begingroup$ Sometimes it's easier to ask for forgiveness than to wait for permission. Does that help? $\endgroup$
    – Asaf Karagila
    May 9 at 8:13

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.