Computable reducibility · Computability Theory

An ω-reduction may use any number of instances of $\mathsf Q$ , each built from the solutions of the previous ones. Dzhafarov proposed to count: a computable reduction solves an instance of $\mathsf P$ with a single instance of $\mathsf Q$ . This finer notion separates problems that are equivalent in ω-models, and it is the analogue for problems of the reductions of complexity theory.

2.1 Computable and strong computable reducibility

Definition 2.1.#

Let $\mathsf P$ and $\mathsf Q$ be problems.

$\mathsf P$ is computably reducible to $\mathsf Q$ , written $\mathsf P \leq_c \mathsf Q$ , if every instance $X$ of $\mathsf P$ computes an instance $\widetilde X$ of $\mathsf Q$ such that, for every solution $\widetilde Y$ to $\widetilde X$ , the set $X \oplus \widetilde Y$ computes a solution to $X$ .
$\mathsf P$ is strongly computably reducible to $\mathsf Q$ , written $\mathsf P \leq_{sc} \mathsf Q$ , if moreover $\widetilde Y$ alone computes a solution to $X$ .
$\mathsf P$ is computably true if every instance computes a solution to itself.

Strong reducibility forbids the use of the original instance in the second step: all the information needed must be coded in the solutions of $\mathsf Q$ . Both relations are preorders, and $\mathsf P \leq_{sc} \mathsf Q$ implies $\mathsf P \leq_c \mathsf Q$ .

Proposition 2.2.#

If $\mathsf P \leq_c \mathsf Q$ , then $\mathsf P \leq_\omega \mathsf Q$ . A problem $\mathsf P$ is computably true if and only if $\mathsf P \leq_c \mathsf{Id}$ , if and only if every Turing ideal satisfies it.

Proof of Proposition 2.2.

Let $\mathcal I \models \mathsf Q$ and $X \in \mathcal I$ an instance of $\mathsf P$ . The instance $\widetilde X \leq_T X$ belongs to $\mathcal I$ , so it has a solution $\widetilde Y \in \mathcal I$ ; then $X \oplus \widetilde Y \in \mathcal I$ computes a solution to $X$ , which belongs to $\mathcal I$ .

If $\mathsf P$ is computably true, take $\widetilde X = X$ as an instance of $\mathsf{Id}$ . Conversely, if $\mathsf P \leq_c \mathsf{Id}$ , the only solution to $\widetilde X$ is $\widetilde X \leq_T X$ , so $X$ computes a solution. If every Turing ideal satisfies $\mathsf P$ , so does $\{ Y : Y \leq_T X \}$ , so $X$ computes a solution. Conversely, if $\mathsf P$ is computably true, every instance in a Turing ideal computes a solution, which belongs to the ideal.

For instance, $\mathsf{RT}^1_2$ is computably true: one of the two color classes is infinite, and it is computable from the coloring. The game of the previous lesson refines into a hierarchy: write $\mathsf P \leq^n_\omega \mathsf Q$ if Player 2 has a strategy in $G(\mathsf Q \rightarrow \mathsf P)$ that wins within $n + 1$ rounds, that is, after at most $n$ instances of $\mathsf Q$ . Then $\mathsf P \leq^0_\omega \mathsf Q$ means that $\mathsf P$ is computably true, and $\mathsf P \leq_c \mathsf Q$ implies $\mathsf P \leq^1_\omega \mathsf Q$ , with equivalence when $\mathsf Q$ has a computable instance.

Proposition 2.3.#

$\mathsf{KL} \leq^2_\omega \mathsf J$ , but $\mathsf{KL} \not\leq_c \mathsf J$ .

Proof of Proposition 2.3.

Player 2 plays $T$ , then $T'$ , and receives $T''$ , which computes a path through $T$ , as in Proposition 1.4.

No set is PA relative to itself, since it would compute a function that differs from every function it computes; so by Theorem 5.6 of “Finitely branching trees” there is an infinite computable finitely branching tree $T$ without $\emptyset'$ -computable path. Every instance $\widetilde X \leq_T T$ of $\mathsf J$ is computable, so its solution $\widetilde X'$ is computable in $\emptyset'$ , and $T \oplus \widetilde X' \leq_T \emptyset'$ computes no path through $T$ .

So computable reducibility is strictly finer than ω-reducibility. It is also incomparable with provability over $\mathsf{RCA}_0$ : a proof may use the hypothesis several times, and a computable reduction may rely on properties of the standard natural numbers, such as instances of induction, that $\mathsf{RCA}_0$ does not prove. In practice, many implications over $\mathsf{RCA}_0$ are proved by computable reductions that formalize in $\mathsf{RCA}_0$ .

2.2 Computable reductions to weak König’s lemma

For $\mathsf{WKL}$ , the two reducibilities coincide, because a single instance of $\mathsf{WKL}$ can produce a whole Scott ideal.

Theorem 2.4 (Scott).#

Let $A$ be a set and $P$ a set that computes $A$ and is PA relative to $A$ . There is a Scott ideal containing $A$ all of whose members are computable in $P$ .

Proof of Theorem 2.4.

For a set $Z$ , let $D^Z$ be the class of $\{0, 1\}$ -valued functions $g$ with $g(e) \neq \Phi^Z_e(e)$ whenever $\Phi^Z_e(e)$ converges; it is a non-empty $\Pi^0_1(Z)$ class, uniformly in $Z$ . Let $\mathcal C$ be the class of sequences $(X_i)_{i \in \nat}$ , coded as $\bigoplus_i X_i$ , such that $X_0 = A$ and, for every $i$ , $X_{i+1} \in D^{Z_i}$ , where $Z_i = X_0 \oplus \cdots \oplus X_i$ . It is a $\Pi^0_1(A)$ class, non-empty since each $D^{Z_i}$ is non-empty. Since $P$ computes $A$ and is PA relative to $A$ , it computes a member $(X_i)$ of $\mathcal C$ , by Theorem 4.2 of “PA degrees” relativized to $A$ ; and every $Z_i$ is computable in $P$ .

Let $\mathcal I = \{ Y : \exists i\ Y \leq_T Z_i \}$ , a Turing ideal containing $A$ , with all members computable in $P$ . The set $Z_{i+1} = Z_i \oplus X_{i+1}$ computes $Z_i$ and a $\{0, 1\}$ -valued function that is diagonally non-computable relative to $Z_i$ , so it is PA relative to $Z_i$ , by Theorem 4.2 of “PA degrees” relativized to $Z_i$ ; hence it is PA relative to every $Y \leq_T Z_i$ , since every non-empty $\Pi^0_1(Y)$ class is a $\Pi^0_1(Z_i)$ class. So every member $Y \leq_T Z_i$ of $\mathcal I$ has a member $Z_{i+1}$ of $\mathcal I$ that is PA relative to it, and $\mathcal I$ is a Scott ideal by Proposition 2.3 of “Weak König's lemma”.

The sets $Z_i$ are used rather than the $X_i$ : a function that is diagonally non-computable relative to $Z$ need not compute $Z$ , and the join ensures that the sequence increases.

Theorem 2.5 (Hirschfeldt, Jockusch).#

For every problem $\mathsf P$ , $\mathsf P \leq_\omega \mathsf{WKL}$ if and only if $\mathsf P \leq_c \mathsf{WKL}$ .

Proof of Theorem 2.5.

One direction is Proposition 2.2. Suppose $\mathsf P \leq_\omega \mathsf{WKL}$ , and let $X$ be an instance of $\mathsf P$ . Let $\widetilde X$ be an $X$ -computable infinite binary tree whose paths are the members of $D^X$ , the $\{0, 1\}$ -valued functions diagonally non-computable relative to $X$ . For every path $\widetilde Y$ , the set $X \oplus \widetilde Y$ computes $X$ and is PA relative to $X$ . By Theorem 2.4, there is a Scott ideal $\mathcal I$ containing $X$ , all of whose members are computable in $X \oplus \widetilde Y$ . It satisfies $\mathsf{WKL}$ , hence $\mathsf P$ , so $X$ has a solution in $\mathcal I$ , which is computable in $X \oplus \widetilde Y$ .

2.3 Cylinders

The product $\mathsf P \times \mathsf Q$ of two problems has as instances the sets $X_0 \oplus X_1$ with $X_0$ an instance of $\mathsf P$ and $X_1$ an instance of $\mathsf Q$ , and as solutions the sets $Y_0 \oplus Y_1$ with $Y_i$ a solution to $X_i$ .

Definition 2.6.#

A problem $\mathsf Q$ is a cylinder if $\mathsf{Id} \times \mathsf Q \leq_{sc} \mathsf Q$ .

A cylinder can code any given set into its solutions. For cylinders, the strong and the ordinary reducibilities agree.

Proposition 2.7.#

A problem $\mathsf Q$ is a cylinder if and only if, for every problem $\mathsf P$ , $\mathsf P \leq_c \mathsf Q$ implies $\mathsf P \leq_{sc} \mathsf Q$ .

Proof of Proposition 2.7.

Suppose $\mathsf Q$ is a cylinder and $\mathsf P \leq_c \mathsf Q$ . Let $X$ be an instance of $\mathsf P$ , and $\widetilde X \leq_T X$ the instance of $\mathsf Q$ given by the reduction. Then $X \oplus \widetilde X$ is an instance of $\mathsf{Id} \times \mathsf Q$ , so there is an instance $V \leq_T X \oplus \widetilde X \leq_T X$ of $\mathsf Q$ such that every solution $W$ to $V$ computes $X \oplus \widetilde Y$ for some solution $\widetilde Y$ to $\widetilde X$ . Then $W$ computes a solution to $X$ . So $\mathsf P \leq_{sc} \mathsf Q$ . Conversely, $\mathsf{Id} \times \mathsf Q \leq_c \mathsf Q$ always holds, with $\widetilde X = X_1$ ; if computable reductions to $\mathsf Q$ are strong, $\mathsf Q$ is a cylinder.

Proposition 2.8.#

$\mathsf{WKL}$ and $\mathsf J$ are cylinders. Consequently, $\mathsf P \leq_\omega \mathsf{WKL}$ implies $\mathsf P \leq_{sc} \mathsf{WKL}$ .

Proof of Proposition 2.8.

Given a set $X$ and a binary tree $T$ , let $S$ be the tree of strings $\sigma$ such that $\sigma(2i + 1) = X(i)$ for all $2i + 1 < |\sigma|$ , and the string $\tau$ of the even bits of $\sigma$ belongs to $T$ . It is computable in $X \oplus T$ , infinite if $T$ is, and its paths are exactly the sets $P \oplus X$ with $P$ a path through $T$ ; each of them computes $X \oplus P$ . For $\mathsf J$ , the jump of $X \oplus T$ computes $X \oplus T'$ . The consequence follows from Theorem 2.5 and Proposition 2.7.

Strong reducibility is strictly stronger than computable reducibility in general. For instance, $\mathsf{Id} \leq_c \mathsf{RT}^1_2$ , since the solution may use the instance. But $\mathsf{Id} \not\leq_{sc} \mathsf{RT}^1_2$ : for a non-computable $X$ , every $X$ -computable coloring has an infinite homogeneous set that does not compute $X$ , by the theorem of Dzhafarov and Jockusch (Dzhafarov, Jockusch). So $\mathsf{RT}^1_2$ is not a cylinder.

2.4 Exercises

Exercise 2.9 ★.

Show that $\leq_c$ is transitive.

Solution

Let $\mathsf P \leq_c \mathsf Q \leq_c \mathsf R$ , and $X$ an instance of $\mathsf P$ . Let $\widetilde X \leq_T X$ be the instance of $\mathsf Q$ , and $\widehat X \leq_T \widetilde X$ the instance of $\mathsf R$ given by the second reduction for $\widetilde X$ . Then $\widehat X \leq_T X$ . For every solution $\widehat Y$ to $\widehat X$ , $\widetilde X \oplus \widehat Y$ computes a solution $\widetilde Y$ to $\widetilde X$ , and $X \oplus \widetilde Y$ computes a solution to $X$ . Since $\widetilde X \leq_T X$ , the set $X \oplus \widehat Y$ computes $X \oplus \widetilde Y$ , hence a solution to $X$ .

Exercise 2.10 ★★.

Show that $\mathsf{RT}^2_2 \not\leq_c \mathsf{WKL}$ , and that $\mathsf{WKL} \not\leq_c \mathsf{RT}^1_2$ .

Solution

By Theorem 2.5, $\mathsf{RT}^2_2 \leq_c \mathsf{WKL}$ would give $\mathsf{RT}^2_2 \leq_\omega \mathsf{WKL}$ , which fails by Exercise 1.11. For the second statement, $\mathsf{RT}^1_2$ is computably true, so $\mathsf{WKL} \leq_c \mathsf{RT}^1_2$ would make $\mathsf{WKL}$ computably true, by transitivity and Proposition 2.2. But there is an infinite computable binary tree without computable path (Theorem 2.6 of “Computable members”).

2.5 Notes and references

Computable reducibility was introduced by Dzhafarov (2015) in his study of cohesiveness, and strong computable reducibility at the same time. Scott (1962) proved that every PA degree bounds a Scott ideal, in the language of completions of Peano arithmetic; Hirschfeldt and Jockusch derived the coincidence of the reducibilities to $\mathsf{WKL}$ .

D. D. Dzhafarov, Cohesive avoidance and strong reductions, Proceedings of the American Mathematical Society 143 (2015), 869–876.
D. Scott, Algebras of sets binumerable in complete extensions of arithmetic, in Recursive Function Theory, Proceedings of Symposia in Pure Mathematics 5, American Mathematical Society, 1962, 117–121.
D. R. Hirschfeldt and C. G. Jockusch, On notions of computability-theoretic reduction between Π¹₂ principles, Journal of Mathematical Logic 16 (2016), 1650002.