10
$\begingroup$

Is there a non-computable set $X\subset\omega$ such that, for some $Y\subset\omega$, any infinite subset or cosubset (=subset of the complement) of $Y$ computes $X$?

More generally, call a set $X$ $n$-hintable if there is some $f\in n^\omega$ such that, whenever I am told infinitely many bits of $f$, I can compute all of $X$. Then: What are the $n$-hintable sets?

(I ran into this question while thinking about stable ramsey's theorem: given a stable $k$-coloring of pairs - that is, a $k$-coloring of pairs $c$ such that $\lim_yc(x<y)$ always exists - the map $f: x\mapsto \lim_yc(x<y)$ is an element of $k^\omega$ such that, given infinitely many bits of $f$, we can compute an infinite $c$-homogeneous set. So we could say that the mass problem of solutions to $c$ is $k$-hintable; and now the question arises whether there are individual reals which are hintable.)

I suspect the answer is "every $n$-hintable set is computable," but I can't see how to prove it.

By way of background, a set $X$ is bi-introreducible if any infinite subset or cosubset of $X$ computes $X$. So 2-hintability is a much weaker property than bi-introreducibility. Seetapun (http://projecteuclid.org/download/pdfview_1/euclid.ndjfl/1040136917, theorem 2.19) showed that the bi-introreducible sets are all computable, but his argument doesn't answer my question, as far as I can tell. EDIT: As Liang Yu's answer below shows, Seetapun's arguments do answer my question, at least for $n=2$.

$\endgroup$
4
  • $\begingroup$ You want to require $Y$ to be infinite, lest the condition holds for every noncomputable $X$. $\endgroup$ Sep 29, 2014 at 7:16
  • $\begingroup$ I don't see why - if $Y$ is finite, then there are infinite cosubsets of $Y$ which are computable. $\endgroup$ Sep 29, 2014 at 7:40
  • $\begingroup$ Sorry, I misread it as a coinfinite subset. What is a cosubset, actually? A quotient? $\endgroup$ Sep 29, 2014 at 10:10
  • $\begingroup$ I've added the definition in the body of the question - by "cosubset" I just mean a subset of the complement. $\endgroup$ Sep 29, 2014 at 17:02

1 Answer 1

8
$\begingroup$

There is no 2-hintable set by the same argument from Seetpun.

Suppose that there is such a pair $X$ and $Y$. By Freidberg's Theorem, there is a set $A$ such that $A$ is not above either $X$ or $Y$, but $A'$ computes $X\oplus Y$. By Theorem 2.18 in the paper, there is a function $f\leq_T A:[\omega]^2\to 2$ such that any infinite $f$-homogeneous set is either subset of $Y$ or of the complement of $Y$. Now by Theorem 2.1 in the paper, there is an $f$-homogeneous set $H$ not computing $X$.

I think that, by a simple modification of this argument, one may show that there is no $n$-hintable set for any $n\geq 2$.

$\endgroup$
4
  • 1
    $\begingroup$ I believe you mean $f \leq_T A$. $\endgroup$ Sep 29, 2014 at 13:46
  • 1
    $\begingroup$ A different argument, not going through Seetapun's Theorem, is given in Lemma 5.2(i) of D. D. Dzhafarov and C. G. Jockusch, Jr., Ramsey's theorem and cone avoidance, J. Symbolic Logic 74 (2009), 557--578. $\endgroup$ Sep 29, 2014 at 15:32
  • $\begingroup$ Thanks, that answers my main question! I'm still interested in the (non-)existence of $n$-hintables, but I've accepted this answer. $\endgroup$ Sep 29, 2014 at 19:16
  • $\begingroup$ @NoahS, you can iterate the above argument to do $n$-hintables. By induction (and relativization), $n$-hintable relative to $A$ means computable from $A$. Suppose $f \in (n+1)^\omega$ witnesses $X$ being $(n+1)$-hintable, and fix $A$ not computing $X$ but $f \leq_T A'$. Define $g(x) = \min(f(x), 1)$, and apply the above reasoning to get $H \subseteq g^{-1}(i)$ such that $H \oplus A$ does not compute $X$. But consideration of $f\upharpoonright_H$ shows that $X$ is $n$-hintable relative to $H \oplus A$, contrary to hypothesis. $\endgroup$ Sep 30, 2014 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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