Coding on computable subdomains

BlogCoding on computable subdomains
Ludovic Patey Admin asked 7 months ago   /   Blog

The computable analysis of stable Ramsey’s theorem for pairs and two colors ($SRT^2_2$) is closely related to the combinatorial analysis of the infinite pigeonhole principle ($RT^1_2$) for arbitrary instances. In particular, $SRT^2_2$ is computably equivalent to $D^2_2$, the statement that every $\Delta^0_2$ set has an infinite subset in it or its complement.

Theorem (Monin and Patey). For every non-$\Delta^0_2$ set $C$ and every set $A$, there is an infinite subset $H$ of $A$ or of $\overline{A}$ such that $C$ is not $\Delta^0_2(H)$.

The proof is arguably natural, but involves a very complicated notion of forcing. The restriction of the theorem to $\Delta^0_2$ sets $A$ is however much simpler, thanks to the following theorem, and the cone avoidance basis theorem relative to $\emptyset’$.

Theorem (Cholak, Jockusch and Slaman). For every $\Delta^0_2$ set $A$ and every set $P$ of PA degree over $\emptyset’$, there is an infinite subset $H$ of $A$ or of $\overline{A}$ such that $H’ \leq_T P$.

It is therefore natural to try to reduce the main theorem to the $\Delta^0_2$ case by relativizing to a Turing degree $d$ such that the set $A$ is $\Delta^0_2(d)$. A negative answer to the following question would be a way of doing so.

Is there a set $A$ such that for every infinite computable set $X = \{x_0 < x_1 < \dots \}$, letting $A_X = \{ n : x_n \in A \}$, $\emptyset” \leq_T A_X \oplus \emptyset’$?

1 Answers
Best Answer
Ludovic Patey Admin answered 7 months ago

The answer is yes. It is easy to build an infinite set $A$ such that the principal function $p_A$ which on $n$ outputs the $n$th element of $A$ dominates the modulus of $\emptyset”$, and such that for every infinite computable set $X$, $A \cap X$ is infinite.
Then, using $A_X$ will compute.a function dominating $p_A$, hence will compute $\emptyset”$.