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

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'$!

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$ is DNR. 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'$.)

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