6
$\begingroup$

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ought to know. The solution is probably very simple, but I don't see it.

Fix a computable total function $f$ of two variables such that $$f(x, s)\ge f(x, s+1),$$ and let $$F(x)=\lim_{s\rightarrow\infty}f(x, s).$$ Then there is an infinite set $X\subseteq\omega$ satisfying $$i, j\in X, i<j\implies F(i)\le F(j).$$ Call such an $X$ $f$-good. My question is:

How complicated must such an $X$ be?

Specifically,

Is there an $f$ as above such that any $f$-good $X$ computes $0'$?

Note that trivially, $0'$ will always compute such an $X$, so this is the upper bound.

It's easy to show that there are not always computable such $X$ - indeed, there are $f$ such that any $f$-good $X$ computes a DNR function. However, coding $0'$ seems very difficult, because the "current guess" to whether $F(i)\le F(j)$ can only change a (bounded) finite number of times. (Note that by contrast, if we look at $f$ satisfying $f(x, s)\le f(x, s+1)$, then it is very easy to code $0'$.)


EDIT: We can ask an even weaker question:

Suppose $d$ computes an $f$-good $X$ for every computable $f$. Must $d\ge_T0'$?

This ought to be easier to show, but I am at a loss. I can't even show that if $Y$ is such that for every computable $f$ there is some $n$ such that $Y\setminus n$ is $f$-good, then $Y$ computes $0'$!

$\endgroup$
  • $\begingroup$ Just a comment. If you take $F$ as Kolmgorov complexity, then any such $X$ computes a $DNR$-function. $\endgroup$ – 喻 良 Jan 11 '16 at 9:26
  • $\begingroup$ @喻良 Yes, I mention getting DNRs in my last paragraph. $\endgroup$ – Noah Schweber Jan 11 '16 at 9:27
4
$\begingroup$

You're right. This is the kind of things we ought to know. Let $\mathsf{LNS}$ be the statement that every such function f has an f-good set.

Results

I claim that $\mathsf{LNS}$ admits

  • cone avoidance (if A is non-computable, then any computable instance of $\mathsf{LNS}$ has a solution X such that A is not X-computable)
  • preservation of hyperimmunity (if $A_0, A_1, \dots$ are countably many hyperimmune sets, then every computable instance of $\mathsf{LNS}$ has a solution X such that the $A$'s are hyperimmune relative to $X$).

Therefore, $\mathsf{LNS}$ implies neither $\mathsf{ACA}_0$, nor $\mathsf{ADS}$.

Combinatorics

Fix a computable instance $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, let $f_0 : \mathbb{N} \to \mathbb{N}$ and $\tilde{f} : \mathbb{N} \to \mathbb{N}$ be the functions defined by $f_0(x) = f(x, 0)$ and $\tilde{f}(x) = \lim_s f(x, s)$, respectively. Note that $f_0$ is computable, while $\tilde{f}$ is not.

If there is some $i$ such that $\tilde{f}(x) = i$ for infinitely many $x$, then pick the least such $i$, and notice that the set $\{ x : \tilde{f}(x) = i \}$ is c.e. and every infinite computable subset of it is $f$-good. So from now on, we will assume that for every $i$ and almost every $x$, $\tilde{f}(x) > i$.

We will build an $f$-good set by forcing, using a variant of Mathias forcing $(F, X)$, where

  • $F$ is a finite set over which $\tilde{f}$ is non-decreasing.
  • $X$ is an infinite set such that $\max F < \min X$.
  • for every $x \in F$ and $y \in X$, $\tilde{f}(x) \leq \tilde{f}(y)$.

In particular, $(\emptyset, \omega)$ is a valid condition, and given a condition $(F, X)$ and a finite set $H \subseteq X$ which is non-decreasing for $\tilde{f}$, $(F \cup H, X \setminus [0, n])$ is a valid extension for some $n \in \mathbb{N}$.

We now want to decide a $\Sigma^0_1$ formula $\varphi(G)$ given a condition $(F, X)$. Let $\mathcal{C}$ be the $\Pi^{0,X}_1$ class of all functions $h : \mathbb{N} \to \mathbb{N}$ dominated by $f_0$, such that $\varphi(F \cup H)$ does not hold for every finite set $H \subset X$ over which $h$ is non-decreasing. There are two cases.

  • Case 1: $\mathcal{C}$ is empty. In this case, since $\tilde{f} \not \in \mathcal{C}$, there is a finite set $H \subseteq X$ such that $\varphi(F \cup H)$ holds and over which $\tilde{f}$ is non-decreasing. The condition $(F \cup H, X \setminus [0, n])$ for some sufficiently large $n$ is a valid extension forcing $\varphi(G)$ to hold.

  • Case 2: $\mathcal{C}$ is non-empty. By weak K\"onig's lemma, pick an $h \in \mathcal{C}$ and $h \oplus X$-computably thin-out the set $X$ to obtain an infinite set $Y$ over which $h$ is non-decreasing. The condition $(F, Y)$ forces $\varphi(G)$ not to hold.

An example

Suppose for example that we want to prove that $\mathsf{LNS}$ admits cone avoidance. Let $A$ be a non-computable set and $f$ be a computable instance of $\mathsf{LNS}$. We work with conditions $(F, X)$ as above, with the extra property that $A \not \leq_T X$.

Given a condition $(F, X)$ and a $\{0,1\}$-valued Turing functional $\Gamma$, I claim there is an extension forcing $\Gamma^G \neq A$. To see this, for each $n \in \mathsf{N}$ and $i \in \{0,1\}$, let $\mathcal{C}_{n, i}$ be the $\Pi^{0,X}_1$ class of all functions $h : \mathbb{N} \to \mathbb{N}$ dominated by $f_0$, such that $\Gamma^{F \cup H}(n) \uparrow$ or $\Gamma^{F \cup H}(n) \downarrow \neq i$ for every finite set $H \subset X$ over which $h$ is non-decreasing. Consider the $X$-c.e. set $S = \{ (n, i) : \mathcal{C}_{n,i} = \emptyset \}$. We have three cases.

  • Case 1: $(n, 1-A(n)) \in S$ for some $n$. In this case, since $\mathcal{C}_{n,1-A(n)} = \emptyset$, there is a finite set $H \subseteq X$ such that $\Gamma^{F \cup H}(n) \downarrow = 1-A(n)$ and over which $\tilde{f}$ is non-decreasing. The condition $(F \cup H, X \setminus [0, n])$ for some sufficiently large $n$ forces $\Gamma^G(n) \neq A(n)$.

  • Case 2: $(n, 0)$ and $(n, 1) \not \in S$ for some $n$. In this case, by the cone avoidance basis theorem, there are two functions $h_0 \in \mathcal{C}_{n,0}$, $h_1 \in \mathcal{C}_{n,1}$ such that $A \not \leq_T h_0 \oplus h_1 \oplus X$. By $h_0 \oplus h_1 \oplus X$-computably thinning-out the set $X$, we obtain a set $Y$ over which both $h_0$ and $h_1$ are non-decreasing. The condition $(F, Y)$ forces $\Gamma^G(n) \neq 0$ and $\Gamma^G(n) \neq 1$, so forces $\Gamma^G(n) \uparrow$.

  • Case 3: $S = \{ (n, A(n)) : n \in \mathbb{N} \}$. In this case, we can $X$-compute $A$, contradiction.

This completes the proof of cone avoidance.


EDIT: Note that one can easily use cone avoidance of $\mathsf{LNS}$ as a blackbox to build for any non-computable set $A$ a set $X$ such that $A \not \leq_T X$ and for every computable $f$, there is some $n$ such that $X \setminus [0, n]$ is $f$-good.

Indeed, fix the set $A$, and consider Mathias conditions $(F, X)$ such that $A \not \leq_T X$. For every such condition $(F, X)$ and every computable function $f$, one can apply cone avoidance of $\mathsf{LNS}$ to obtain an $f$-good set~$Y \subseteq X$ such that $A \not \leq_T Y$. The condition $(F, Y)$ forces $G$ to be $f$-good up to finite changes. Moreover, for every condition $(F, X)$ and every $e$, there is an extension $(H, Y)$ forcing $\Phi_e^G \neq A$. Every sufficiently generic for this notion of forcing yields the desired set.

$\endgroup$
  • $\begingroup$ Hi Ludovic, this is very nice! I will need to wait a bit before I have time to read it in detail, but I think it works! $\endgroup$ – Noah Schweber Mar 9 '16 at 23:05

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.