Notions of robust information coding

Abstract

We introduce and study several notions of computability-theoretic reducibility between subsets of ω that are “robust” in the sense that if only partial information is available about the oracle, then partial information can be recovered about the output. These notions are motivated by reductions between $Π_{2}^{1}$ principles in the context of reverse mathematics, where some of our results have already been applied, e.g., by Hirschfeldt and Jockusch [to appear]. Our work also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp [J. Lond. Math. Soc. (2) 85(2) (2012), 472–490].

Keywords

Generic computability generic case complexity coarse computability

1. Introduction

The study of relative computation – which subsets of ω are Turing reducible to (i.e., computable from) which others – has been the principal interest of classical computability theory almost from the subject’s inception. While the concept of oracle Turing machines is natural and powerful, working with it quickly leads one to discover that in many cases a set is actually computable from another as a result of a much stronger type of reduction (e.g., $t t$ -reduction, 1-reduction). And indeed, this observation has led to the identification and independent study of a myriad of refinements and modifications of ordinary Turing reducibility, each having to do with a particular method of how information can be coded and decoded.

In this article, we introduce several definitions of computability-theoretic reducibility based on robustness of information coding. The background question for us here is the following: how can information be coded so that it can be recovered with only partial access to the oracle, or with unusual rules for accessing the oracle? This is motivated in large part by the study of $Π_{2}^{1}$ principles in reverse mathematics, i.e., statements of the form, “For every set A (called an instance of the principle) with certain arithmetical properties, there is a set B (called a solution to the instance A) with certain arithmetical properties with respect to A”. Proving an implication from some such theorem (over the base theory ${RCA}_{0}$ ) typically involves building an instance A of the principle such that every solution B to A is computationally powerful. This can be viewed as a way of coding information into the set A, although the method of decoding (i.e., first passing to a solution) may make it appear rather indirect. In particular, as the set of solutions may be closed under various set-theoretic and computability-theoretic operations (e.g., as is not uncommon, under infinite subset), it is important to know how to build A in such a way that the information coded into it can be recovered from any solution, not just a particular one.

One of our reducibilities, $ii$ -reducibility, has already found application in this context. Hirschfeldt and Jockusch [5] used our Theorem 5.1 below, suitably modified, to obtain results about the strength of certain combinatorial principles in reverse mathematics. (See the discussion preceding Observation 2.11 for more details.)

Our aim, then, is to understand the coding strategies that permit this type of “persistent” information retrieval. This leads us to formulate the following reducibilities between sets of numbers:

mod-finite reducibility, $⩽_{mf}$ ;

cofinite reducibility, $⩽_{cf}$ ;

generic reducibility, $⩽_{g}$ ;

coarse reducibility, $⩽_{c}$ ;

mod-recursive reducibility, $⩽_{mr}$ ;

infinite-information reducibility, $⩽_{ii}$ ;

use-bounded-from-below reducibility, $⩽_{ubfb}$ .

All of these, formally defined in Section 2, have the general form described by the following framework.

Framework.
Given a notion of largeness, a set B is reducible to a set A if every set that agrees with A on a large domain uniformly computes a set that agrees with B on a large domain.

The idea is that if A computes B in a sufficiently robust manner, then changing (or losing) a small number of the bits of the oracle should still allow us to recover most of the output. In a sense, then, we are looking at certain kinds of error-correcting or self-redundant codes, in which no single bit is essential for the computation of too many of the rest.

As a simple-minded example, suppose B is 1-reducible to A, written $B ⩽_{1} A$ , and meaning $B = {n \in ω : f (n) \in A}$ for some computable one-to-one function f. Then every set cofinitely equal to A computes a set cofinitely equal to B, via the same 1-reduction. Thus, if “large” is taken to mean “cofinite”, we have that B is reducible to A in the sense of the above framework.

If we use asymptotic density as our notion of largeness, then we obtain either generic reducibility or coarse reducibility (see Definitions 2.1 and 2.5). Generic computability and coarse computability (see Definition 2.2) were introduced by Jockusch and Schupp in 2012 [9] as computability-theoretic analogues of the phenomenon in complexity theory in which the generic case of a problem is sometimes much more readily solved than might be suggested by the worst-case complexity of a problem. Since 2012, there has been a proliferation of work concerning generic computability and coarse computability. Our results tying cofinite and mod-finite reducibility to generic and coarse reducibility has been used in several papers concerning generic and coarse reducibility, e.g., [1,6,8].

In this article, we confine our interest to the seven reducibilities just described, though others can certainly be fitted into our framework. (A discussion of some possible variations and extensions appears at the end of Section 2.) Likewise, our results here are not meant to be definitive, but rather to develop, with a view towards future work, a set of techniques with which our reducibilities, and potentially others, can be studied. This article is organized as follows. In Section 2 we formally define our reducibilities, and more precisely describe our framework for studying them. In Section 3 we prove Theorem 3.1, establishing how our reducibilities compare to one another, and exhibit embeddings of some of these reducibilities into others. Section 4 concerns non-implications, and shows that no relationships between our reducibilities hold other than those of Theorem 3.1. Finally, in Section 5 we focus on $⩽_{ii}$ , and prove that this reducibility admits maximal pairs.
2. Definitions

Unless otherwise noted, we shall follow standard notation and terminology employed in the literature. This includes, for a partial function f on ω, writing $f (n) ↓$ if n is in the domain of f. If f and g are two partial functions, we shall write $f (n) ≃ g (n)$ if $f (n) = g (n)$ provided n is in the domain of both functions, and we shall write $f ≃ g$ if $f (n) ≃ g (n)$ for all n. We shall also always identify sets with their characteristic functions. Though we shall be dealing with various reducibilities, and hence implicitly with various join and meet operators on sets, we shall reserve ⊕ for the ordinary Turing join of sets: $A \oplus B = {2 n : n \in A} \cup {2 n + 1 : n \in B}$ . We refer the reader to Soare [11] for complete background on computability theory, and to Downey and Hirschfeldt [2] for background on algorithmic randomness, which several of our results will relate to. In addition, we refer the reader to Sacks [10] for background on higher recursion theory, which will be applicable to our work in Section 5.

We now pass to the definitions of the reducibilities we shall be concerned with.

Our first examples are motivated by recent work studying generic computability and coarse computability, [3,7,9]. These notions concern being able to correctly compute most of a set in the following sense.

Definition 2.1.
Let A be a subset of the natural numbers. Then A has density 1 if the limit of the densities of its initial segments exists and equals 1, i.e., if ${lim}_{n \to \infty} \frac{| A \cap n |}{n} = 1$ . In this case, we will frequently say that A is density-1.
Definition 2.2 ([9], Definitions 1.4 and 2.3).

A set B is generically computable if there is a partial computable function Φ whose domain has density 1 such that $Φ ≃ B$ .

A set B is coarsely computable if there is a total computable function Φ such that ${n \in ω : Φ (n) = B (n)}$ has density 1.

In other words, a generically computable set is given by a computation that never lies, but might not halt on a domain of density 0. A coarsely computable set, by contrast, is given by a computation that always halts, but might lie on a domain of density 0.

Perhaps the most obvious way to relativize generic computability is to say that B is generically computable from A if there is a functional Φ such that $Φ^{A} ≃ B$ with domain of density 1. This is not by itself a reducibility between sets because it is highly non-transitive. In fact, Igusa [7] has established the following fact: for any reflexive binary relation R on ω there exists a class $C$ of subsets of ω such that $(ω, R)$ is isomorphic to the structure of $C$ under the relation of generic computability.

Thus, we shall work instead with the following relativizations of coarse and generic computability. The latter appears also in [9, Definition 4.3].

Definition 2.3.
A set B is coarsely reducible to a set A, written $B ⩽_{c} A$ , if there exists a Turing functional Φ such that for any set C, if ${n \in ω : C (n) = A (n)}$ has density 1 then $Φ^{C}$ is total and ${n \in ω : Φ^{C} (n) = B (n)}$ has density 1.

Because generic computability intrinsically involves partial computations, if we wish to define generic reducibility, we must first define what a partial oracle is.
Definition 2.4.
Let A be a set. A partial oracle $(A)$ for A is a set of ordered triples $⟨ n, x, l ⟩$ such that:
$\exists l (⟨ n, 0, l ⟩ \in (A)) ⟹ n \notin A$ ;

$\exists l (⟨ n, 1, l ⟩ \in (A)) ⟹ n \in A$ .

We regard $(A)$ as a partial function that maps n to x, and that takes l steps to converge. Under this interpretation, a partial oracle is a partial function $(A) : ω \to {0, 1}$ such that $(A) ≃ A$ . When we refer to querying the nth bit of $(A)$ we are actually initiating a subalgorithm that searches for some x, l such that $⟨ n, x, l ⟩ \in (A)$ . While waiting, a computation is allowed to perform other calculations and even to query other bits of the oracle. The domain of $(A)$ is the set of n so that there exist such x and l.

The primary purpose of the l in the formal definition is to ensure that, when working with a partial oracle, one does not know whether or not the oracle will give an output on some given input. However, in our notation in this article, we will follow the intuitive concept of a partial oracle as a partial function, rather than the formal definition as a set of triples. Under this convention, a set A is a partial oracle for itself that immediately halts on every input.

We may now define generic reducibility. This is not the original definition by Jockusch and Schupp, which used enumeration operators. However, the two definitions are equivalent, as shown in [7, Proposition 3.10].
Definition 2.5.
A set B is generically reducible to a set A, written $B ⩽_{g} A$ , if there exists a Turing functional Φ such that $Φ^{A} = B$ , and for any partial oracle $(A)$ for A with density-1 domain, $Φ^{(A)}$ has density-1 domain, and $Φ^{(A)} ≃ B$ .

Note that generic and coarse reducibility agree with generic and coarse computability when $A = \emptyset$ .

Our next reducibilities are analogues of generic and coarse reducibility that allow only finite omission/error. They are motivated in part as a generalization of 1-reducibility, as was mentioned in the previous section, and in part to help understand the difference between partial oracles and partially incorrect oracles by examining the difference in a simplified framework that does not need to reference asymptotic density.
Definition 2.6.
A set B is mod-finite reducible to a set A, written $B ⩽_{mf} A$ , if there exists a Turing functional Φ such that $Φ^{A} = B$ , and for any set C, if ${n \in ω : C (n) = A (n)}$ is cofinite then $Φ^{C}$ is total and ${n \in ω : Φ^{C} (n) = B (n)}$ is cofinite.
Definition 2.7.
A set B is cofinitely reducible to a set A, written $B ⩽_{cf} A$ if there exists a Turing functional Φ such that $Φ^{A} = B$ , and for any partial oracle $(A)$ for A with cofinite domain, $Φ^{(A)} ≃ B$ with cofinite domain.

Note that for these two reducibilities, and also for the upcoming reducibility, the uniformity hypothesis (that a single Φ must work for all possible mod-finite, or cofinite oracles for A) is essential, because without it, both of the reducibilities would be equivalent to Turing reducibility. The question of uniformity for other reducibilities will be discussed below. Note also that the requirement that $Φ^{A} = B$ is purely a requirement of convenience. If it were omitted, the resulting reducibilities would be the same (see Observation 2.11).

Our next reducibilities do not involve true notions of largeness, in the commonly accepted sense of being closed under intersection and superset. The first takes “large” to be “computable”.
Definition 2.8.
A set B is mod-recursive reducible to a set A, written $B ⩽_{mr} A$ , if there exists a Turing functional Φ such that $Φ^{A} = B$ , and for any set C, if ${n \in ω : C (n) = A (n)}$ is computable then $Φ^{C}$ is total and ${n \in ω : Φ^{C} (n) = B (n)}$ is computable.

This sort of reducibility is somewhat uncommon in computability theory, not counting fairly trivial cases. However, it is quite common in real-world information coding, where, frequently, changes in the input yield predictable changes in the output. It also provides an interesting example that shows that our framework for computation does not require our notion of largeness to be closed under superset. (A mod-recursive computation must be correct exactly on a computable set, not just correct on a set containing a computable set.)
Remark.
We use the term “mod-recursive” rather than “mod-computable” partly to avoid needing to use the phrase “mod-computable computation”, and partly to evoke the feeling of a classically computable set, to help differentiate recursive set from a set that is computable according any of the other notions of computability discussed in this article.

The second notion takes “large” to be “infinite”. Being infinite is arguably the most conspicuous feature of any notion of largeness, and as such the corresponding reducibility is among the most natural for our purposes. By contrast, the results we obtain about it in Section 5 also make it the most counterintuitive to understand.
Definition 2.9.
A set B is infinite-information reducible to a set A, written $B ⩽_{ii} A$ , if there exists a Turing functional Φ such that for any partial oracle $(A)$ for A with infinite domain, $Φ^{(A)} ≃ B$ with infinite domain.

This reduction is motivated by, and closely tied to, coding and de-coding techniques commonly used in reverse mathematics, particularly in the study of Ramsey’s theorem and related combinatorial principles. For instance, knowing an infinite homogeneous set for a computable stable 2-coloring corresponds precisely to knowing an infinite set of bits of a $Δ_{2}^{0}$ set.

Finally, we consider a reducibility defined in terms of restricting our computation techniques, rather than in terms of an explicit notion of largeness with which to measure our oracles and outputs. This reducibility does not explicitly fit into our framework, but it is closely tied to both mod-finite and cofinite reductions.
Definition 2.10.
A set B is use-bounded-from-below reducible to a set A, written $B ⩽_{ubfb} A$ , if there is a Turing functional Φ such that $Φ^{A} = B$ and for every m and all sufficiently large n, the functional does not query $A (m)$ in computing $Φ^{A} (n)$ .

Normally, the use of a computation is thought of in terms of the largest element of the oracle queried to obtain an output, but here, we care instead about the smallest such query. Concordantly, we shall avoid, when necessary, various usual conventions of oracle computation that may interfere with the analysis of $⩽_{ubfb}$ , such as identifying the use with an initial segment of the oracle.

Each of our reducibilities obviously gives rise to a degree structure. We shall call these the mod-finite, coarse, cofinite, generic, mod-recursive, infinite-information, and use-bounded-from-below degrees, respectively.

There are several natural ways in which our definitions above can be modified and extended. The first comes from considering non-uniform versions, in which the functional Φ in the definition of the reducibility is allowed to depend on the specific oracle (or partial oracle). Of course, this does not make sense for use-bounded-from-below reducibility, while for mod-finite, cofinite, and mod-recursive reducibilities, it is easy to check that the non-uniform versions are equivalent to ordinary Turing reducibility. We do not explicitly study non-uniform versions of generic or coarse reducibilities here, but many of the results hold in either version. The situation for non-uniform infinite-information reducibility is largely open. However, one application of this reducibility has been by Hirschfeldt and Jockusch [5, Theorem 3.9] in reverse mathematics. Using a version of Theorem 5.1 below for non-uniform $ii$ -reducibility, they showed that there is a coloring $c : ω \to k + 1$ such that every coloring $d : ω \to k$ has an infinite homogeneous set that computes no infinite homogeneous set for c. This answers a question of Montalbán (private communication), and extends a result of Dzhafarov [4] concerning the strength of various forms of Ramsey’s theorem under so-called strong computable reducibility.

The next natural modification of our definitions is in whether or not we insist that $Φ^{A} = B$ . We do not, in this article, consider versions of generic, coarse, and infinite-information reducibility where this hypothesis is added. Indeed, doing so for generic and coarse reducibility would mean the two no longer extend generic and coarse computability, and doing so for infinite-information reducibility would lose the connection to reverse mathematics mentioned after Definition 2.9. However, these versions might be interesting to study in their own right. For mod-finite, cofinite, and mod-recursive reducibilities, the addition of this hypothesis is actually superfluous, and we add it only because doing so makes the reducibilities more convenient to work with.
Observation 2.11.

Let A, B, Φ be such that Φ witnesses a cofinite reduction of B to A without the hypothesis that $Φ^{A} = B$ (i.e., if $(A)$ is any partial oracle for A with cofinite domain then $Φ^{A} ≃ B$ with cofinite domain). Then B is cofinitely reducible to A (in the full sense of Definition 2.7 ).

The same holds for mod-recursive reducibility.

The same holds for mod-finite reducibility.

Proof.
Fix A, B, Φ be as in 1. Then $\tilde{Φ}$ witnesses a cofinite reduction of B to A, where $\tilde{Φ}$ is defined by $\begin{matrix} {\tilde{Φ}}^{C} (n) = \{\begin{matrix} Φ^{C} (n) & if Φ^{A} (n) ↓, \\ B (n) & if Φ^{A} (n) ↑ . \end{matrix} \end{matrix}$ Note that ${n : Φ^{A} (n) ↑}$ is finite, so the values of B on that set can be coded directly into $\tilde{Φ}$ .

For case 2, assume Φ instead witnesses a mod-recursive reduction of B to A without the hypothesis that $Φ^{A} = B$ . Then $\tilde{Φ}$ witnesses a mod-recursive reduction of B to A, where $\tilde{Φ}$ is defined by $\begin{matrix} {\tilde{Φ}}^{C} (n) = \{\begin{matrix} Φ^{C} (n), & Φ^{A} (n) ↓ = B (n), \\ 1 - Φ^{C} (n), & Φ^{A} (n) ↓ \neq B (n) . \end{matrix} \end{matrix}$ Now ${n : Φ^{A} (n) \neq B (n)}$ is computable, so $\tilde{Φ}$ is a computable modification of Φ.

Case 3 can be handled in either of these ways. □

Finally, we can look further at the differences between the set versus partial oracle versions of our reducibilities, as in mod-finite versus cofinite, and coarse versus generic. The set version of infinite-information reducibility is trivial. Any set is either infinite or coinfinite, and so either the computation that outputs 0 everywhere or the computation that outputs 1 everywhere is correct infinitely often. Thus, every set would be computable from the empty oracle. The partial oracle version of mod-recursive is also trivial, because the empty set is computable, and it is trivial to produce a partial computation of any real whose domain is empty. If one were to demand that the domains of the input and output be computable and infinite, then this reducibility would share many qualities of infinite-information reducibility. However, we do not explicitly study this version.
3. Embeddings and implications

We begin with the following theorem, establishing how our reducibilities compare to one another, as well as to 1-reducibility and Turing reducibility. For notational convenience, if $⩽_{*}$ and $⩽_{*^{'}}$ are any two reducibilities between sets, we shall say $⩽_{*}$ implies $⩽_{*^{'}}$ , and write $⩽_{*} ⟹ ⩽_{*^{'}}$ , if for all sets A and B, $\begin{matrix} A ⩽_{*} B ⟹ A ⩽_{*^{'}} B . \end{matrix}$

Theorem 3.1.

We have $\begin{matrix} ⩽_{1} ⟹ ⩽_{mr} ⟹ ⩽_{T}, \end{matrix}$ and $\begin{matrix} ⩽_{1} ⟹ ⩽_{mf} ⟹ ⩽_{ubfb} ⟹ ⩽_{cf} ⟹ ⩽_{T} . \end{matrix}$

No other implications hold between any of: $⩽_{1}$ , $⩽_{T}$ , $⩽_{mr}$ , $⩽_{mf}$ , $⩽_{ubfb}$ , $⩽_{cf}$ , $⩽_{g}$ , $⩽_{c}$ , and $⩽_{ii}$ .

Proof of part 1.
( $⩽_{1} ⟹ ⩽_{mr}$ ) Suppose $B ⩽_{1} A$ via the computable function f, and let Φ be the corresponding Turing functional. Then for any set C, we have $\begin{matrix} {n : Φ^{C} (n) = B (n)} = {n : C (f (n)) = A (f (n))} ⩽_{T} {n : C (n) = A (n)} . \end{matrix}$ Hence, $B ⩽_{mr} A$ via Φ.

( $⩽_{mr} ⟹ ⩽_{T}$ ) Clear.

( $⩽_{1} ⟹ ⩽_{mf}$ ) Suppose $B ⩽_{1} A$ via the computable function f, and let Φ be the corresponding Turing functional. Then if $C =^{} A$ we have $\begin{matrix} Φ^{C} = {n : f (n) \in C} =^{} {n : f (n) \in A} = B . \end{matrix}$

( $⩽_{mf} ⟹ ⩽_{ubfb}$ ) Suppose $B ⩽_{mf} A$ via the functional Φ. Define a new functional Ψ that works as follows. Given a set S and number n, let $S_{0}, \dots, S_{2^{n} - 1}$ be the $2^{n}$ many possible sets obtained by changing S on the first n many bits. Now $Ψ^{S} (n)$ proceeds by first computing $Φ^{S_{i}} (n)$ for each $i < 2^{n}$ without querying any bits of S below n, and then querying the bits of S below n one by one in decreasing order until all but one of the values from $Φ^{S_{0}} (n), \dots, Φ^{S_{2^{n} - 1}} (n)$ are eliminated. This remaining value is then output. It is not difficult to see that $Ψ^{A} = B$ . Furthermore, since $Φ^{A}$ is a mod-finite reduction, for each m there is an $m^{'}$ such that each of $Φ^{A_{0}}, \dots, Φ^{A_{2^{m} - 1}}$ agree from $m^{'}$ on. Thus, if $n ⩾ m^{'}$ then in particular $Ψ^{A} (n)$ does not query any bit of the oracle below m. This means that $Ψ^{A}$ is a uniform-bounded-from-below reduction.

( $⩽_{ubfb} ⟹ ⩽_{cf}$ ) Assume $A ⩽_{ubfb} B$ via the functional Φ. Then Φ also witnesses that $A ⩽_{cf} B$ , provided we declare $Φ^{(A)} (n)$ to be undefined if during its computation $(A)$ is undefined on some queried bit. Now suppose $(A)$ is a partial oracle for A with cofinite domain. Then if n is sufficiently large, the fact that Φ is a use-bounded-from-below reduction means it will only query bits in the domain of $(A)$ in computing $Φ^{(A)} (n)$ . Hence, on all sufficiently large inputs, $Φ^{(A)}$ will converge and equal $Φ^{A} = B$ .

( $⩽_{cf} ⟹ ⩽_{T}$ ) Immediate from the definition. □

We delay the proof of part 2 of the theorem to the next section.

It follows immediately that if $⩽_{}$ is any of $⩽_{mr}$ , $⩽_{mf}$ , $⩽_{cf}$ , or $⩽_{ubfb}$ then for every set A there is a B such that $B ≰_{} A$ . (Namely, take any $B ≰_{T} A$ .) Thus, these reducibilities are non-trivial. The following result strengthens this observation, and extends it to $⩽_{c}$ , $⩽_{g}$ , and $⩽_{ii}$ .
Proposition 3.2.
Let $⩽_{}$ be any of our reducibilities, and let A be any set. If B is weakly 1-generic or 1-random relative to A, then* $B ≰_{} A$ .
Proof.
As above, this follows for $⩽_{mr}$ , $⩽_{mf}$ , $⩽_{cf}$ , and $⩽_{ubfb}$ by Theorem 3.1. To see it for $⩽_{c}$ , note that for every functional Φ, if $Φ^{A}$ is total, the set of $σ \in 2^{< ω}$ for which there exists an n with $\begin{matrix} \frac{| {n < | σ | : Φ^{A} (n) \neq σ (n)} |}{| σ |} > \frac{1}{2} \end{matrix}$ is computably enumerable relative to A and dense, and as such is infinitely often met by any set weakly 1-generic relative to A. Hence, no such set is coarsely reducible to A.

Likewise, if $Φ^{A}$ is total, then the sequence of sets of $σ \in 2^{< ω}$ with $\begin{matrix} \frac{| {n < | σ | : Φ^{A} (n) \neq σ (n)} |}{| σ |} > \frac{1}{4} \end{matrix}$ is a uniformly enumerable-in-A sequence of open sets with measure uniformly approaching 1. (The measure approaches 1 by the law of large numbers: if you make a large number of guesses, it is very difficult to be incorrect only $\frac{1}{4}$ of the time.)

If B is 1-random relative to A, then B cannot be a member of infinitely many of those sets, and hence B is not coarsely reducible to A.

For $⩽_{ii}$ and $⩽_{g}$ , observe that if $Φ^{A}$ has infinite domain, then the collection of strings σ such that ( $\forall n < | σ |$ ) ( $n \in dom (Φ^{A}) \to Φ^{A} (n) = σ (n)$ ) is a $Π_{1}^{0, A}$ class with measure 0. (The measure drops by a factor of 2 each time a new n enters $dom (Φ^{A})$ .) If B is weakly 1-random relative to A, then B cannot be a member of this class, completing the proof because 1-genericity and 1-randomness both imply weak 1-randomness. □

We shall use the following definitions here and in the rest of this article. Given a set S, define $\begin{matrix} R (S) = {2^{n} m : n \in S, m odd} \end{matrix}$ and $\begin{matrix} \tilde{R} (S) = {2^{n} + m : n \in S, m < 2^{n}} . \end{matrix}$ In other words, a number belongs to $R (S)$ if and only if the highest power of 2 that divides it belongs to S, while a number belongs to $\tilde{R} (S)$ if and only if the highest power of 2 less than or equal to it belongs to S. Jockusch and Schupp [9, Lemma 4.6] showed that the map $S \mapsto R (S)$ induces an embedding of the Turing degrees into the generic degrees. We use the map $S \mapsto \tilde{R} (S)$ to exhibit two similar embeddings. The key distinction is that any partial oracle for $R (S)$ with domain of density 1 uniformly computes S (see [9, Observation 2.11]), while any such oracle for $\tilde{R} (S)$ only uniformly computes a partial oracle for S with cofinite domain.
Proposition 3.3.

The map* $S \mapsto \tilde{R} (S)$ induces an embedding of the cofinite degrees into the generic degrees.

The map $S \mapsto \tilde{R} (S)$ induces an embedding of the mod-finite degrees into the coarse degrees.

The map $S \mapsto R (S)$ induces an embedding of the Turing degrees into the cofinite degrees.

The map $S \mapsto R (S)$ induces an embedding of the Turing degrees into the mod-finite degrees.

Parts 1–3 are very similar, and all follow quickly from the following lemma. Part 4 will require a more subtle construction for reasons that we will discuss in Proposition 3.5.

Note that the embedding $S \mapsto \tilde{R} (R (S))$ , embedding the Turing degrees into the coarse degrees was also independently discovered by Hirschfeldt, Jockusch, Kuyper, and Schupp [6] as a modification of the embedding $S \mapsto \tilde{R} (S)$ , which embeds the Turing degrees into the non-uniform coarse degrees, a structure which we do not otherwise discuss in this article.
Lemma 3.4.

Any cofinite oracle for S can uniformly compute a generic oracle for $\tilde{R} (S)$ , and any generic oracle for $\tilde{R} (S)$ can uniformly compute a cofinite oracle for S.

Any mod-finite oracle for S can uniformly compute a coarse oracle for $\tilde{R} (S)$ , and any coarse oracle for $\tilde{R} (S)$ can uniformly compute a mod-finite oracle for S.

Any (total) oracle for S can uniformly compute a cofinite oracle for $R (S)$ , and any cofinite oracle for $R (S)$ can uniformly compute (a total oracle for) S.

Recall that a cofinite oracle is a partial oracle that halts on cofinite domain, a generic oracle is a partial oracle that halts on density 1, a mod-finite oracle is a total oracle that is correct on a cofinite set, and a coarse oracle is a total oracle that is correct on density 1.

Note that the proof is somewhat lengthy, but is quite straightforward. The only trick involved is the use of a simple voting technique to recover a mod-finite oracle from a coarse oracle.
Proof of Lemma 3.4.
A cofinite oracle for S can easily compute a cofinite (and hence generic) oracle for $\tilde{R} (S)$ as follows. Each bit of S is coded into finitely many bits of $\tilde{R} (S)$ , so removing a finite amount from the oracle for S only removes a finite amount from the domain of the computation of $\tilde{R} (S)$ . Similarly, a finite number of errors in the oracle for S results in a finite number of errors in the computation of $\tilde{R} (S)$ . This produces a coarse oracle for $\tilde{R} (S)$ , since the oracle is correct on a cofinite (and hence density-1) set.

A generic oracle for $\tilde{R} (S)$ can uniformly compute a cofinite oracle for S by searching over all of its coding locations as follows. Let T be a generic oracle for $\tilde{R} (S)$ . To compute whether $n \in S$ , for each $m < 2^{n}$ , ask if $2^{n} + m \in \tilde{R} (S)$ . If T answers any of those $2^{n}$ -many questions, then halt and give the output that T gives. (I.e., output $n \in S$ if and only if $T (2^{n} + m) = 1$ , where m is the first $m < 2^{n}$ that is found such that $T (2^{n} + m)$ halts. If no such m is found, then give no output on n.)

This output is always correct, because the generic oracle never gives false outputs, so it remains to show that if the domain of the generic oracle is, in fact, density-1, then the domain of the computation is cofinite. This is because there must be some k such that $\begin{array}{rcl} \forall l > k, \frac{| dom (T ↾ l) |}{l} > \frac{1}{2} . \end{array}$ When $2^{n + 1} > k$ , T must halt on $2^{n} + m$ for some $m < 2^{n}$ , because otherwise $| dom (T ↾ 2^{n + 1}) | ⩽ 2^{n}$ . Thus, if $n > {log}_{2} (k) - 1$ , then the computation will halt on input n.

Likewise, a coarse oracle for $\tilde{R} (S)$ can uniformly compute a mod-finite oracle for S with a voting algorithm as follows. Let T be a coarse oracle for $\tilde{R} (S)$ . To compute whether $n \in S$ , for each $m < 2^{n}$ , ask if $2^{n} + m \in \tilde{R} (S)$ . When T gives $2^{n - 1}$ identical answers, then halt and give that answer as our output.

This computation always halts, because T is a total oracle, and so, when it gives $2^{n}$ -many answers, at least one of the two different answers must be given at least $2^{n - 1}$ -many times. Thus, it remains to show that if T is correct on density-1, then the computation is correct on a cofinite set. This is because there must be some k such that $\begin{array}{rcl} \forall l > k, \frac{| {s < l : T (s) = \tilde{R} (S) (s)} |}{l} > \frac{3}{4} . \end{array}$ When $2^{n + 1} > k$ , T must be correct on $2^{n} + m$ for over half of the $m < 2^{n}$ , because otherwise $| {s < 2^{n + 1} : T (s) = \tilde{R} (S) (s)} | ⩽ 3 (2^{n - 1})$ .

Finally, we show part 3. Certainly, a total oracle for S can uniformly recover all of $R (S)$ , and so, in particular, can compute a cofinite oracle for $R (S)$ .

For the converse, given a cofinite oracle for $R (S)$ , we compute S as follows. To compute whether $n \in S$ , for each odd number m, we ask whether $2^{n} m \in R (S)$ . When we get an answer from one of these questions, we halt and give this as our output for n. The algorithm must eventually halt, because a cofinite oracle can only fail to converge at finitely many locations. Also, the answer must be correct, because a cofinite oracle never gives false outputs. □

We now proceed to prove our proposition about embeddings.
Proof of Proposition 3.3.
We prove each of the parts of the proposition in turn.

Part 1. To show that $S \mapsto \tilde{R} (S)$ induces an embedding of the cofinite degrees into the generic degrees, assume first that $A ⩾_{cf} B$ . Then, $\tilde{R} (A) ⩾_{g} \tilde{R} (B)$ by the following reduction.

Let S be a generic oracle for $\tilde{R} (A)$ . Apply Lemma 3.4 to S to compute a cofinite oracle, $(A)$ , for A. Use the reduction witnessing $A ⩾_{cf} B$ to compute a cofinite oracle, $(B)$ , for B. Then apply Lemma 3.4 to $(B)$ to compute a generic oracle for $\tilde{R} (B)$ .

The converse is similar. If $\tilde{R} (A) ⩾_{g} \tilde{R} (B)$ , then $A ⩾_{cf} B$ by applying the lemma, using the generic reduction, and applying the lemma again.

Part 2. Analogous to the proof of part 1.

Part 3. Analogous to the proof of part 1.

Part 4. We wish to show that the map $S \mapsto R (S)$ induces an embedding of the Turing degrees into the mod-finite degrees. First, Theorem 3.1 shows that $⩽_{mf} ⟹ ⩽_{T}$ , so if $R (A) ⩾_{mf} R (B)$ , then $R (A) ⩾_{T} R (B)$ . In this case, $A ⩾_{T} B$ , because $A \equiv_{T} R (A) ⩾_{T} R (B) \equiv_{T} B$ .

For the converse, assume $A ⩾_{T} B$ . Then, in particular, $A ⩾_{T} R (B)$ . Assume that this is witnessed by Φ, so that $Φ^{A} = R (B)$ . We will use this Φ to provide a computation of $R (B)$ from $R (A)$ for which a finite error in the oracle will result in a finite error in the output.

For any number, k, and real, X, let $X_{k} = {n : 2^{n} (2 k + 1) \in X}$ . So ${(R (A))}_{k} = A$ . The idea is that $R (A)$ has ω-many distinct copies of A in it, and ${(R (A))}_{k}$ is the kth copy. The most important fact about this is that if C is any mod-finite oracle for $R (A)$ , then for all but finitely many k, $C_{k} = A$ .

So now, let C be a mod-finite oracle for $R (A)$ . To compute whether $k \in R (B)$ , we search for some $l > k$ such that $Φ^{C_{l}} (k) ↓$ . When we find such an l, we halt, and give $Φ^{C_{l}} (k)$ as our output.

To finish the proof, we must show that for every k, we halt, and that for all but finitely many k, we halt and give the correct answer. We halt for every k because for every k, $Φ^{A} (k)$ halts, and there is some $l > k$ such that $C_{l} = A$ , so at some point, we will find that computation and halt (if we have not halted before). We only give finitely many incorrect answers because there are only finitely many n such that $C_{n} \neq A$ , so if k is larger than all of those n, then for every $l > k$ , $C_{l} = A$ and so, in particular, $Φ^{C_{l}} (k) = Φ^{A} (k) = R (B) (k)$ . Thus, for sufficiently large k, the first found output will be the correct output. □

Note that parts 1–3 of Proposition 3.3 all follow from Medvedev reductions. (See, e.g., [2, Section 8.9] for an introduction to Medvedev reducibility and Medvedev degrees.) For instance, the statement of part 1 of Lemma 3.4 can be rephrased as: “For any S, the set of cofinite oracles for S is equivalent to the set of generic oracles for $\tilde{R} (S)$ .”

We now prove that there can be no uniform analogue of part 4 of Proposition 3.3, and moreover that there can be no analogous proof of any embedding from the Turing degrees to either the mod-finite or the coarse degrees.
Proposition 3.5.
If S is noncomputable, then it is not true that any mod-finite oracle for $R (S)$ can uniformly compute a (total) oracle for S.

In fact, if S is noncomputable, then for any T, there is no uniform way to compute S from an arbitrary mod-finite oracle for T, and also there is no uniform way to compute S from an arbitrary coarse oracle for T.

In the language of Medvedev reductions, for any real T, the set of mod-finite (or coarse) oracles for T cannot have the same Medvedev degree as the singleton S.
Proof of Proposition 3.5.
We prove that if S is noncomputable, then for any T, there is no uniform way to compute S from an arbitrary mod-finite oracle for T. The version with coarse oracles follows directly, because every mod-finite oracle for T is a coarse oracle for T, so a uniform way to compute S from an arbitrary coarse oracle for T would be a uniform way to compute S from an arbitrary mod-finite oracle for T. It follows directly that it is not true that any mod-finite oracle for $R (S)$ can uniformly compute S.

So let S be noncomputable, let T be any real, and let Φ be any Turing functional. Assume that for every $R =^{} T$ , $Φ^{R} = S$ . Then we claim that for any $σ \in 2^{< ω}$ , if $Φ^{σ} (n) ↓$ , then $Φ^{σ} (n) = S (n)$ . This is because any $σ \in 2^{< ω}$ can be extended to an R that is $=^{}$ to T. Furthermore, we claim that for every n, there is a $σ \in 2^{< ω}$ such that $Φ^{σ} (n) ↓$ . This is because for every $R =^{} T$ , $Φ^{R} = S$ , and in particular, $Φ^{T}$ is total.

Thus, S can be computed by searching for $σ \in 2^{< ω}$ that make $Φ^{σ} (n) ↓$ for each value of n, since we can always find such a σ and no σ ever gives a false output. This contradicts the noncomputability of S. □

Our final results in this section establish that infinite-information reducibility behaves in many ways opposite* to the rest (a fact we shall find further evidence for in Section 5). Part 2 below, that the Turing join is the infinite-information meet, is false of most reducibilities studied in the literature, including all the other ones we are considering here, as we show subsequently in Proposition 3.7. Proposition 3.6.

For all sets A and B, if $B ⩽_{1} A$ then $A ⩽_{ii} B$ .

The (Turing) join of two sets A and B is their meet under $⩽_{ii}$ .

Proof.
For part 1, suppose f witnesses the 1-reduction of B to A. Let Φ be the corresponding Turing functional, and define Ψ by letting $\begin{matrix} Ψ^{(S)} (m) = \{\begin{matrix} (S) (f^{- 1} (m)) & if m \in ran (f), \\ ↑ & otherwise \end{matrix} \end{matrix}$ for all partial oracles $(S)$ and numbers m. In particular, if $(B)$ is a partial oracle for B and $m = f (n)$ for some n in the domain of $(B)$ then $\begin{matrix} Ψ^{(B)} (m) = B (n) = A (f (n)) = A (m) . \end{matrix}$ It follows that if $(B)$ has infinite domain then $Ψ^{B}$ is a partial oracle for A with infinite domain.

For part 2, we have that $A \oplus B ⩽_{ii} A, B$ , since we can uniformly convert infinitely many bits of A or of B into infinitely many bits of $A \oplus B$ . Furthermore, if $C ⩽_{ii} A$ via Φ and $C ⩽_{ii} B$ via Ψ, then $C ⩽_{ii} A \oplus B$ via the functional which, given oracle S and input m, runs $Φ^{{n : 2 n \in S}} (m)$ and $Ψ^{{n : 2 n + 1 \in S}} (m)$ , returning the output of whichever of these that happens to halt first. □
Proposition 3.7.
The (Turing) join of two sets A and B is also their join under any of our reducibilities other than $⩽_{ii}$ .
Proof.
The result is clear for $⩽_{ubfb}$ , and is easily checked for the remaining reducibilities. For instance, to show that $A \oplus B$ is the join of A and B under $⩽_{mr}$ , note that if $C = C_{0} \oplus C_{1}$ agrees with $A \oplus B$ on a computable domain $D = D_{0} \oplus D_{1}$ then $C_{0}$ and $C_{1}$ agree with A and B on the computable domains $D_{0}$ and $D_{1}$ , respectively. Hence, $A, B ⩽_{mr} A \oplus B$ . On the other hand, if $A, B ⩽_{mr} S$ , say via reductions Φ and Ψ, then $Φ \oplus Ψ$ (which takes oracle $X \oplus Y$ to $Φ^{X} \oplus Ψ^{Y}$ ) witnesses that $A \oplus B ⩽_{mr} S$ . □

4. Non-implications

We divide the task of proving part 2 of Theorem 3.1, that no further implications hold between our reducibilities other than the ones presented there, among the following subsections.

4.1. Infinite-information, generic, and coarse reducibilities

In this section, we show that $⩽_{ii}$ , $⩽_{g}$ , and $⩽_{c}$ are independent of each other and our other reducibilities in terms of implication. For $⩽_{ii}$ , this follows readily from our work at the end of the previous section.

Proposition 4.1.
If $⩽_{}$ is $⩽_{T}$ , $⩽_{1}$ , or any of our reducibilities other than* $⩽_{ii}$ , then $⩽_{} ⇏ ⩽_{ii}$ and* $⩽_{ii} ⇏ ⩽_{}$ .
Proof.
For all sets A, we have $\begin{matrix} A ⩽_{} A \oplus \emptyset ⩽_{ii} \emptyset, \end{matrix}$ by Propositions 3.7 and 3.6. Thus, if $⩽_{} ⟹ ⩽_{ii}$ we have $A ⩽_{ii} \emptyset$ , and $⩽_{ii} ⟹ ⩽_{}$ we have $A ⩽_{} \emptyset$ . Thus, to disprove either implication, let A be any weakly 1-generic or 1-random set, so that by Proposition 3.2, we have $A ≰_{ii} \emptyset$ and $A ≰_{} \emptyset$ . □

We now turn to $⩽_{g}$ and $⩽_{c}$ . The incomparability of these two with one another follows from the work of Jockusch and Schupp [9].
Proposition 4.2.

There exist sets A and B such that $B ⩽_{g} A$ but $B ≰_{c} A$ .

There exist sets A and B such that $B ⩽_{c} A$ but $B ≰_{g} A$ .

Proof.
Jockusch and Schupp [9, Theorem 2.26 and Proposition 2.15] exhibited a set that is generically computable but not coarsely computable, and a set that is coarsely computable but not generically computable. We thus take A to be ∅, and B to be the set from the relevant Jockusch–Schupp construction. □

Finally, we establish that $⩽_{g}$ and $⩽_{c}$ are incomparable with all of the other reducibilities mentioned in Theorem 3.1. Our proof below actually works for both the uniform and non-uniform versions of these reducibilities, as discussed in Section 2. Proposition 4.3.

There exist sets A and B such that $B ⩽_{1} A$ but $B ≰_{c} A$ .

There exist sets A and B such that $B ⩽_{c} A$ but $B ≰_{T} A$ .
Hence, by the positive part of Theorem 3.1 , if $⩽_{}$ is $⩽_{T}$ , $⩽_{1}$ , or any of our reducibilities other than* $⩽_{c}$ , then $⩽_{} ⇏ ⩽_{c}$ and* $⩽_{c} ⇏ ⩽_{}$ . The same is true for* $⩽_{g}$ in place of $⩽_{c}$ .
Proof.
For part 1, fix any $B ≰_{c} \emptyset$ and let $A = {2^{n} : n \in B}$ . Then obviously $B ⩽_{1} A$ but $A ⩽_{c} \emptyset$ , so B is not coarsely reducible to A. For part 2, let C be any noncomputable set, $B = {2^{n} : n \in C}$ , and $A = \emptyset$ . Then $B ⩽_{c} A$ , but $B ≰_{T} A$ since $B \equiv_{T} C$ . The proofs for $⩽_{g}$ are similar. □

4.2. Mod-recursive reducibility

We begin in this section with a straightforward result that shows that the implication from $⩽_{1}$ to $⩽_{mr}$ is strict.

Proposition 4.4.
There exist sets A and B such that $B ⩽_{mr} A$ but $B ≰_{1} A$ .
Proof.
Fix any set A such that $\overline{A} ≰_{1} A$ , and let $B = \overline{A}$ . Then observe that every set is mod-recursive reducible to its complement via the functional Φ defined by $Φ^{C} (n) = 1 - C (n)$ for all sets C and numbers n. Indeed, we have that ${n : Φ^{C} (n) = \overline{A} (n)} = {n : 1 - C (n) = 1 - A (n)} = {n : C (n) = A (n)}$ . □

The next proposition establishes that $⩽_{mr}$ is not implied by $⩽_{mf}$ , or in fact, any of our other reducibilities, since all of these are implied by $⩽_{mf}$ . Thus, no other implications to $⩽_{mr}$ can be added to Theorem 3.1. The argument below follows a basic outline that will be used for several others in this section. We have a definition Δ of a set B from a set A in mind that happens to be a reduction of a particular kind (below, a mod-finite reduction) but not of another (below, a mod-recursive reduction). Then, exploiting the fact that if Φ witnesses a reduction of the latter kind it must be that $Φ^{A} = B$ , we force Φ to either equal Δ or to make a mistake, and thus, in either case, to not witness the latter reduction after all.
Proposition 4.5.
There exist sets A and B such that $B ⩽_{mf} A$ but $B ≰_{mr} A$ .
Proof.
We construct a set U and define B by $B (n) = U (2 n) \cdot U (2 n + 1)$ . We then let $A = R (U)$ . Thus, $B ⩽_{mf} A$ and $A ⩽_{mr} U$ , so it suffices to show that $B ≰_{mr} U$ . To this end, we define for each $s \in ω$ the set $\begin{matrix} U_{s} = U ↾ s \cup {2 n ⩾ s : 2 n \in U} \cup {2 n + 1 ⩾ s : 2 n + 1 \notin U}, \end{matrix}$ and satisfy the following requirement for each $e \in ω$ : $\begin{array}{l} R_{e} : Φ_{e}^{U} \neq B or for some s, either Φ_{e}^{U_{s}} is not total or \\ {n \in ω : Φ_{e}^{U_{s}} (n) = B (n)} is not computable. \end{array}$ Since ${n \in ω : U_{s} (n) = U (n)}$ is obviously computable for each s, this will ensure that $Φ_{e}$ does not witness a mod-recursive reduction. Construction.
We let $U = ⋃_{s} σ_{s}$ , where $σ_{0} ⪯ σ_{1} ⪯ \dots$ are finite strings obtained as follows. Let $σ_{0} = \emptyset$ , and suppose some $σ_{e}$ is given. Step 1.
Ask if there exists a $σ ⪰ σ_{e}$ such that $Φ_{e}^{σ} (n) ↓ \neq σ (2 n) σ (2 n + 1)$ for some n with $2 n + 1 < | σ |$ . If so, fix the least such σ, and otherwise let $σ = σ_{e}$ .
Step 2.
Ask if there is an n with $2 n ⩾ | σ |$ such that $Φ_{e} (2 n) ↓$ . If so, let $σ_{e + 1}$ be the least extension of σ with $σ_{e + 1} (2 n) \neq Φ_{e} (2 n)$ , and otherwise let $σ_{e + 1} = σ$ .
End construction.
Verification.
Fix e, and suppose $Φ_{e}^{U} = B$ . Then it must be that in the construction, we could not find a $σ ⪰ σ_{e}$ satisfying the question asked at Step 1. In other words, any set S extending $σ_{e}$ satisfies $Φ_{e}^{S} (n) ≃ S (2 n) S (2 n + 1)$ . In particular, this holds for $S = U_{s}$ , where $s = | σ_{e} |$ . Assuming $Φ_{e}^{U_{s}}$ is total, this means that for all n with $2 n + 1 ⩾ s$ , $\begin{matrix} Φ_{e}^{U_{s}} (n) = U_{s} (2 n) U_{s} (2 n + 1) = U (2 n) [1 - U (2 n + 1)], \end{matrix}$ which can only equal $B (n) = U (2 n) U (2 n + 1)$ provided $U (2 n) = 0$ . Thus, ${n \in ω : Φ_{e}^{U_{s}} (n) = B (n)}$ is computable if and only if ${2 n \in ω : 2 n \in U}$ is, but we ensured that the latter set is not computable under Step 2 of the construction.
□

It remains to show that no further implications from $⩽_{mr}$ are possible either. This follows from the following result, again with a relatively straightforward proof, which completes our analysis of mod-recursive reducibility. Proposition 4.6.
There exist sets A and B such that $B ⩽_{mr} A$ but $B ≰_{cf} A$ .
Proof.
Consider any set A that is not autoreducible, meaning there is no functional Φ such that $A = Φ^{A}$ and the computation of $Φ^{A} (n)$ does not query $A (n)$ . Let $B = R (A)$ . Since A cannot be uniformly recovered from cofinitely many of its own bits, but can be recovered from cofinitely many of the bits of B, it follows that $B ≰_{cf} A$ . However, $B ⩽_{mr} A$ , as witnessed by the functional Ψ taking a set C to $R (C)$ , since then $\begin{matrix} {k : Ψ^{C} (k) = B (k)} = {2^{n} m : C (n) = A (n), m odd} ⩽_{T} {n \in ω : C (n) = A (n)} . □ \end{matrix}$

4.3. Mod-finite, uniform-bounded-from-below, and cofinite reducibilities

In this section, we focus on the remaining open implications in Theorem 3.1, which are now just the reversals of those in the chain $⩽_{1} ⟹ ⩽_{mf} ⟹ ⩽_{ubfb} ⟹ ⩽_{cf} ⟹ ⩽_{T}$ . The following sequence of propositions establishes that none of these can be reversed.

Proposition 4.7.
There exist sets A and B such that $B ⩽_{mf} A$ but $B ≰_{1} A$ .
Proof.
This can be proved identically to Proposition 4.4. Alternatively, this can be observed from the facts, proved above, that $⩽_{1} ⟹ ⩽_{mf}$ and $⩽_{mf} ⇏ ⩽_{mr}$ . □
Proposition 4.8.
There exist A and B such that $B ⩽_{ubfb} A$ but $B ≰_{mf} A$ .
Proof.
We construct a set A by finite approximation with the property that for each $k \in ω$ there is exactly one n such that $⟨ n, k ⟩ \in A$ . In other words, each column of A has exactly one element. The set B is then defined from A as the set of indices of columns containing an odd element, that is, $\begin{matrix} B = {n \in ω : ⟨ n, k ⟩ \in A for some odd k} . \end{matrix}$ Clearly, this makes $B ⩽_{ubfb} A$ . We now build A so that $B ≰_{mf} A$ . Intuitively, by removing the single element of some column of A, and hence making only a finite change, we shall be able to cause a purported computation of B to not be total. We pass to the details. Construction.
We let $A = ⋃_{e} σ_{e}$ , where $σ_{0} ⪯ σ_{1} ⪯ \dots$ are finite strings obtained as follows. Let $σ_{0} = \emptyset$ . Call a string $σ \in 2^{< ω}$ valid if for each k there is at most one n with $⟨ n, k ⟩ < | σ |$ and $σ (⟨ n, k ⟩) = 1$ . Now assume inductively that we have defined $σ_{e}$ for some e, and that it is valid.

Ask if there is a valid extension σ of $σ_{s}$ such that for some n, k with $⟨ n, k ⟩ < | σ |$ and $σ (⟨ n, k ⟩) = 1$ , either k is odd and $Φ_{e}^{σ} (n) ↓ = 0$ , or k is even and $Φ_{e}^{σ} (n) ↓ = 1$ . If so, let $σ_{e + 1}$ be the least such σ. Otherwise, define $n_{e}$ as the least number for which there is no k with $σ_{e} (⟨ n_{e}, k ⟩) = 1$ , and define $k_{e}$ as the least number with $⟨ n_{e}, k_{e} ⟩ ⩾ | σ_{e} |$ . Then let $σ_{e + 1}$ be the least valid extension of $σ_{e}$ with $σ_{e} (⟨ n_{e}, k_{e} ⟩) = 1$ .
Verification.
We now fix $e \in ω$ and verify that $Φ_{e}$ does not witness a mod-finite reduction of B to A. We may assume $B = Φ_{e}^{A}$ , since otherwise we are done. Hence, during the construction, we must not have been able to diagonalize on $Φ_{e}$ against our method of defining B from A. In other words, for any set C extending $σ_{e}$ that contains at most one element in each column, if $Φ_{e}^{C}$ is total then it equals ${n \in ω : ⟨ n, k ⟩ \in C for some odd k}$ . Furthermore, $n_{e}$ and $k_{e}$ must have been defined and $⟨ n_{e}, k_{e} ⟩$ put in A. In particular, for the set $C = A - {⟨ n_{e}, k_{e} ⟩}$ , if $Φ_{e}^{C} (⟨ n_{e}, k_{e} ⟩)$ converged it would have to equal 0. But any initial segment of C witnessing this computation could then be continued by the addition of $⟨ n_{e}, k ⟩$ for some odd k, which would be a contradiction. Hence, $Φ_{e}^{C} (⟨ n_{e}, k_{e} ⟩)$ must be undefined, and $Φ_{e}^{C}$ not total. Since $C =^{} A$ , this means $Φ_{e}$ is not a mod-finite reduction.
□

The coding techniques in our next proposition are more sophisticated than we have used so far. The argument below is similar to that used by Igusa [8, Theorem 3.1] to show that as a relation on sets, generic reducibility is $Π_{1}^{1}$ -complete.
Proposition 4.9.
There exist A and B such that* $B ⩽_{cf} A$ but $B ≰_{ubfb} A$ .
Proof.
We shall construct the set A, and define B from it. Thus, before proceeding to the construction, we describe this definition. We partition ω as $\begin{matrix} {a_{i, 0} : i \in ω} \cup {a_{i, 1} : i \in ω} \cup {a_{i, j, k, 0} : i, j, k \in ω} \cup {a_{i, j, k, 1} : i, j, k \in ω}, \end{matrix}$ and build A to ensure the following properties hold for every i:
A contains at most one of $a_{i, 0}$ and $a_{i, 1}$ ;

if $a_{i, 0} \in A$ then $a_{i, j, k, 1} \notin A$ for all j, k;

if $a_{i, 1} \in A$ then $a_{i, j, k, 0} \notin A$ for all j, k;

if $a_{i, j, k, 0} \in A$ for some j, k, then $a_{i, j, k^{'}, 1} \notin A$ for all $k^{'}$ ;

if $a_{i, j, k, 1} \in A$ for some j, k, then $a_{i, j, k^{'}, 0} \notin A$ for all $k^{'}$ ;

for almost every j there is a k with $a_{i, j, k, 0} \in A$ or $a_{i, j, k, 1} \in A$ ;

if $a_{i, 0}, a_{i, 1} \notin A$ , then for every j there is a k with $a_{i, j, k, 0} \in A$ or $a_{i, j, k, 1} \in A$ .
We regard B as a set of pairs, and define it from A by the rules below. For all i:
if $a_{i, 0} \in A$ then $⟨ i, j ⟩ \notin B$ for all j;

if $a_{i, 1} \in A$ then $⟨ i, j ⟩ \in B$ for all j;

for every j, if there is a k with $a_{i, j, k, 0} \in A$ , then $⟨ i, j ⟩ \notin B$ ;

for every j, if there is a k with $a_{i, j, k, 1} \in A$ , then $⟨ i, j ⟩ \notin B$ .
Intuitively, we think of the values of the bits of B as being deduced from the values of certain corresponding bits of A. Namely, for each i, the bits $a_{i, 0}$ and $a_{i, 1}$ represent a kind of master deduction procedure for determining the values of the collection of bits $⟨ i, 0 ⟩, ⟨ i, 1 ⟩, \dots$ , while for all i and j, each of the bits $a_{i, j, k, 0}$ and $a_{i, j, k, 1}$ represents an individual deduction procedure for determining the value of the single bit $⟨ i, j ⟩$ . Properties 1–5 above ensure that none of the deduction procedures contradict each other, and hence that the definition of B is consistent. Property 6 will ensure that the intended reduction is a cofinite reduction. Property 7 ensures that the above definition determines B completely.

In fact, we can turn this definition into a cofinite reduction. Let Φ be the functional which with (possibly partial) oracle C and input $⟨ i, j ⟩$ queries the bits $a_{i, 0}$ and $a_{i, 1}$ of C, whilst simultaneously querying the bits $a_{i, j, k, 0}$ and $a_{i, j, k, 1}$ for all k one by one. If and when it finds some such bit to be in C, it halts and outputs an answer in accordance with our definition of B above. Properties 2, 3, and 7 ensure that $Φ^{A} = B$ . The remaining properties, together with the fact that we are querying (bits representing) master and individual deduction procedures simultaneously, ensure that if $(A)$ is a partial oracle for A with cofinite domain then $Φ^{(A)} ≃ B$ with cofinite domain. Indeed, say m is such that $(A) (n) ↓ = A (n)$ for all $n > m$ . For cofinitely many triples i, j, and k, each of the numbers $a_{i, 0}$ , $a_{i, 1}$ , $a_{i, j, k, 0}$ , and $a_{i, j, k, 1}$ is greater than m, so for cofinitely many pairs i and j the reduction $Φ^{(A)}$ will halt on $⟨ i, j ⟩$ . Thus, $B ⩽_{cf} A$ .

We now turn to the construction of A. Construction.
We must ensure that for all e, the functional $Φ_{e}$ does not witness a uniform-bounded-from-below reduction of B to A. The idea is as follows. First, we reduce to the case where $Φ_{e}$ computes B from A essentially via the definition of B given above, that is, by looking for master deductions and individual deductions. Otherwise, we argue that $Φ_{e}^{A} \neq B$ . Then, we fix a number i and add one of the master deductions $a_{i, 0}$ or $a_{i, 1}$ to A. So one way for $Φ_{e}^{A}$ to correctly compute the value of $⟨ i, j ⟩$ for a given j is to query this master deduction, but of course if it does this for infinitely many j then its use will not be bounded from below. Our strategy, then, is to pick a new j every time one of the master deductions is queried, and keep all of its individual deductions $a_{i, j, k, 0}$ and $a_{i, j, k, 1}$ out of A until one of the master deductions is queried again. So if indeed $Φ_{e}^{A}$ eventually stops querying the master deductions, meaning that we settle on a permanent value of j, it will not be able to converge on $⟨ i, j ⟩$ . At the same time, we permanently restrain individual deductions for at most one j, thereby ensuring that A satisfies the properties above.

Formally, we proceed by stages. At each stage s, we shall have a finite set $I_{s}$ of numbers smaller than s, and for each $e \in I_{s}$ , unique numbers $i_{e}$ and $j_{e, s}$ . For $e \in I_{s}$ , we say the bits of the form $a_{i_{e}, j_{e, s}, k, 0}$ and $a_{i_{e}, j_{e, s}, k, 1}$ are $(e, s)$ -forbidden. Given a string $σ \in 2^{< ω}$ , we say that the range of σ is the set of n such that $σ (n) = 1$ . We will say that σvalid at stage s if:
the range of σ does not violate properties 1–5 above if σ is regarded as an initial segment of A;

if the range of σ contains an $(e, s)$ -forbidden number n for some $e \in I_{s}$ , then $Φ_{e}^{σ ↾ n} (⟨ i_{e}, j_{e, s} ⟩) ↓$ and the computation queries either $a_{i_{e}, 0}$ or $a_{i_{e}, 1}$ .
We obtain our set A as a union $⋃_{s} σ_{s}$ of valid strings.

Initially, let $σ_{0} = \emptyset$ , and suppose inductively that for some $s ⩾ 0$ , we are given $σ_{s}$ , $I_{s}$ , and for each $e \in I_{s}$ , the numbers $i_{e}$ and $j_{e, s}$ . By replacing $σ_{s}$ with a valid extension if necessary, we may assume that for each e in the finite set $I_{s}$ , either no valid extension of $σ_{s}$ has an $(e, s)$ -forbidden element in its range, or $σ_{s}$ does so already. Let $i_{s}$ be least so that for all $i ⩾ i_{s}$ and all j and k, none of the numbers $a_{i, 0}$ , $a_{i, 1}$ , $a_{i, j, k, 0}$ or $a_{i, j, k, 1}$ are smaller than $| σ_{s} |$ . In other words, we have not yet determined the values of these bits in A.

We begin by extending $σ_{s}$ to a string $\tilde{σ}$ , considering two cases. Case 1.
There is a valid $σ ⪰ σ_{s}$ such that for some j and some $b \in {0, 1}$ , we have that $Φ_{s}^{σ} (⟨ i_{s}, j ⟩) ↓ = b$ , and if the computation queries $a_{i_{s}, b}$ or $a_{i_{s}, j, k, b}$ for some k then σ forces that this bit is not in A. Let $I_{s + 1} = I_{s}$ , and fix some such σ, j, and b. Let $\tilde{σ}$ be obtained by deleting any element of the form $a_{i_{s}, b}$ or $a_{i_{s}, j, k, b}$ from the range of σ, and appending some $a_{i_{s}, j, k, 1 - b} ⩾ | σ |$ . Then $\tilde{σ}$ is a valid extension of $σ_{s}$ by choice of $i_{s}$ , and $Φ_{s}^{\tilde{σ}} (⟨ i_{s}, j ⟩)$ converges and agrees with $Φ_{s}^{σ} (⟨ i_{s}, j ⟩)$ by choice of σ. Note that by construction, $Φ_{s}^{\tilde{σ}}$ disagrees with B on $⟨ i_{s}, j ⟩$ .
Case 2.
Otherwise. Let $I_{s + 1} = I_{s} \cup {s}$ , and define $j_{s, s + 1} = 0$ . Let $\tilde{σ}$ be the least extension of $σ_{s}$ with either $a_{i_{s}, 0}$ or $a_{i_{s}, 1}$ in its range.

Next, consider any $e \in I_{s}$ such that $\tilde{σ}$ contains an $(e, s)$ -forbidden element in its range. Choose the least $j > j_{e, s}$ such that no element of the form $a_{i_{e}, j, k, 0}$ or $a_{i_{e}, j, k, 1}$ is smaller than $| \tilde{σ} |$ , and let $j_{e, s + 1} = j$ . Thus, no $(e, s)$ -forbidden element is $(e, s + 1)$ -forbidden.

Finally, let $σ_{s + 1}$ be the least valid extension of $\tilde{σ}$ such that for all $e ⩽ s$ and all $⟨ i, j ⟩ ⩽ s$ different from $⟨ i_{e}, j_{e, s + 1} ⟩$ , the range of $σ_{s + 1}$ contains $a_{i, j, k, 0}$ or $a_{i, j, k, 1}$ for some k.
Verification.
By the definition of validity, it follows that $A = ⋃_{s} σ_{s}$ satisfies properties 1–5 above. The last step at stage $s + 1$ of the construction ensures that if $⟨ i, j ⟩ ⩽ s$ and $j \neq j_{e, s}$ for any $e \in I_{s}$ then some element of the form $a_{i, j, k, 0}$ or $a_{i, j, k, 1}$ gets added to A. It follows that if $i \neq i_{e}$ for any e, or if $i = i_{e}$ and ${lim}_{s} j_{e, s}$ does not exist, then this happens for all j. But if $i = i_{e}$ then we have that either $a_{i, 0}$ or $a_{i, 1}$ is added to A, so if the $j_{e, s}$ comes to a limit $j_{e}$ then the above happens for all $j \neq j_{e}$ . Thus, properties 6 and 7 hold as well.

To finish the proof, fix any functional $Φ_{e}$ . If Case 1 of the construction applies at stage $e + 1$ of the construction, then we ensure that $Φ_{e}^{A} \neq B$ . If Case 2 applies, then $Φ_{e}^{A} (⟨ i_{e}, j ⟩)$ can only converge to some $b \in {0, 1}$ if it queries either $a_{i_{e}, b}$ or $a_{i_{e}, j, k, b}$ for some k, and finds this bit present in A. In this case, there are two possibilities. If the $j_{e, s}$ do not come to a limit during the construction, then one of $a_{i_{e}, 0}$ or $a_{i_{e}, 1}$ must be queried infinitely often, so $Φ_{e}^{A}$ is not a uniform-bounded-from-below reduction. If, on the other hand, the $j_{e, s}$ do come to some limit $j_{e}$ , then neither $a_{i_{e}, 0}$ nor $a_{i_{e}, 1}$ can be queried after $j_{e, s}$ assumes its final value, $j_{e}$ . But then the construction ensures that neither $a_{i_{e}, j_{e}, k, 0}$ nor $a_{i_{e}, j_{e}, k, 1}$ are in A, so $Φ_{e}^{A} (⟨ i_{e}, j_{e} ⟩)$ cannot converge. We conclude that in any case, $Φ_{e}^{A}$ is not a uniform-bounded-from-below computation of B.
□

We finish this section with the following straightforward result. Proposition 4.10.
There exist A and B such that $B ⩽_{T} A$ but $B ≰_{cf} A$ .
Proof.
This follows from Proposition 4.6 since $⩽_{mr}$ implies $⩽_{T}$ but not $⩽_{cf}$ . □

5. A maximal pair of infinite-information degrees

In this final section, we take a further look at $⩽_{ii}$ , which turns out to be arguably the most curious of our reducibilities. As we already saw in Proposition 3.6, the 1-degrees embed backwards into the infinite-information degrees, and the usual join operator provides a meet in the infinite-information degrees.

In fact, it turns out that unlike most reducibilities studied in the literature, $⩽_{ii}$ simply does not admit a join operator at all. In other words, the power set of ω ordered by $⩽_{ii}$ is not an upper semi-lattice.

Theorem 5.1.
There exist sets $B_{0}$ and $B_{1}$ for which there is no set A such that $B_{0} ⩽_{ii} A$ and $B_{1} ⩽_{ii} A$ .

To coin a phrase based on standard terminology, the infinite-information degrees thus admit maximal pairs. Just as in the Turing degrees there are minimal pairs, which are so simple that they have no common information content, maximal pairs here are so complex that no set possesses common infinite-information content about them.

Note that minimal pairs are not possible in the $ii$ -degrees for the same reason maximal pairs are not possible in most other degree structures: the ⊕ operator provides a non-zero common lower bound in the $ii$ -degrees as it provides an upper bound elsewhere.

The proof of Theorem 5.1 consists of two technical results, Lemmas 5.3 and 5.4 below, employing the following definition.
Definition 5.2.
For sets A and B, we write $B \leftarrow_{ii} A$ if A can infinite-information compute B, i.e., if there is a Turing functional Φ with $Φ^{A} ≃ B$ with infinite domain.

It is not difficult to show that as a relation on sets, $\leftarrow_{ii}$ need not be transitive. However, it does enjoy the following limited form of transitivity with respect to $⩽_{ii}$ : if $C ⩽_{ii} B \leftarrow_{ii} A$ then $C \leftarrow_{ii} A$ . Indeed, if Φ witnesses that $C ⩽_{ii} B$ and Ψ witnesses that $B \leftarrow_{ii} A$ , then $Φ \circ Ψ$ will witness that $C \leftarrow_{ii} A$ . We shall make use of this fact in the sequel. Beyond this, $⩽_{ii}$ and $\leftarrow_{ii}$ appear ostensibly quite similar. But in fact the two differ in another key way. Namely, if $B \leftarrow_{ii} A$ and C is any set then necessarily $B \leftarrow_{ii} A \oplus C$ . As Proposition 3.6 shows, this is not true of $⩽_{ii}$ .

The first lemma below is quite straightforward. The second, by contrast, turns out to require a substantial amount of work, and we defer its proof for the time being.
Lemma 5.3.
There exist sets $B_{0}$ and $B_{1}$ such that for every $α < ω_{1}^{CK}$ , we have that $B_{0} ↚_{ii} B_{1} \oplus \emptyset^{(α)}$ and $B_{1} ↚_{ii} B_{0} \oplus \emptyset^{(α)}$ .
Proof.
We build $B_{0}$ and $B_{1}$ with $B_{0} ↚_{ii} B_{1} \oplus O$ and $B_{1} ↚_{ii} B_{0} \oplus O$ . This will satisfy the lemma because, for every $α < ω_{1}^{CK}$ , $\emptyset^{(α)} <_{T} O$ . We use finite approximation to build $B_{0}$ and $B_{1}$ .

Let $σ_{0} = τ_{0} = \emptyset$ , and assume that for some $s ⩾ 0$ , $σ_{s}$ and $τ_{s}$ are defined. If $s = 2 e$ , we ask if there is any $n ⩾ | σ_{s} |$ and $τ ⪰ τ_{s}$ such that $\begin{matrix} Φ_{e}^{τ \oplus (O ↾ | τ |)} (n) ↓ = b \end{matrix}$ for some $b \in {0, 1}$ , and if so we let $τ_{s + 1}$ be the least such τ, and let $σ_{s + 1}$ be the least $σ ⪰ σ_{s}$ with $n < | σ |$ and $σ (n) \neq b$ . This ensures that either $Φ_{e}^{B_{1} \oplus O}$ has finite domain or it disagrees with $B_{0}$ . If $s = 2 e + 1$ , we analogously diagonalize to ensure that either $Φ_{e}^{B_{0} \oplus O}$ has finite domain or it disagrees with $B_{1}$ . □
Lemma 5.4.
For all sets A and B, if $B ⩽_{ii} A$ then either there exists an α such that $B \leftarrow_{ii} \emptyset^{(α)}$ or there exists an α such that $A \leftarrow_{ii} B \oplus \emptyset^{(α)}$ .

We now pause to indicate how Theorem 5.1 follows.
Proof of Theorem 5.1.
Fix $B_{0}$ and $B_{1}$ as in the Lemma 5.3, and let A be any set with $B_{0} ⩽_{ii} A$ . By Lemma 5.4, fix some α such that either $B_{0} \leftarrow_{ii} \emptyset^{(α)}$ or $A \leftarrow_{ii} B_{0} \oplus \emptyset^{(α)}$ . The former case cannot hold, since if it did we would have $B_{0} \leftarrow_{ii} \emptyset^{(α)} \oplus B_{1}$ by the remark after Definition 5.2, a contradiction. But by the same remark, if we had $B_{1} ⩽_{ii} A \leftarrow_{ii} B_{0} \oplus \emptyset^{(α)}$ we would have $B_{1} \leftarrow_{ii} B_{0} \oplus \emptyset^{(α)}$ , again a contradiction. Thus, $B_{1} ≰_{ii} A$ , and the theorem is proved. □

The rest of the section is now dedicated to the proof of Lemma 5.4, relying in turn, on the three technical lemmas below. Call a partial oracle finite if its domain is finite. Given finite partial oracles σ and τ, we say τ is a 1-extension of σ, and write $τ ≻_{1} σ$ , if τ extends σ and is defined on precisely one more element than σ is. Given two partial oracles σ and ν, we say that ν agrees with σ if $dom (ν) \subseteq dom (σ)$ and ν agrees with σ as a partial function on its domain. More formally, ν agrees with σ, if it is the case that for every n, x, if $\exists l (⟨ n, x, l ⟩ \in ν)$ then $\exists l (⟨ n, x, l ⟩ \in σ)$ .
Definition 5.5.
Let σ be a partial oracle, $n \in ω$ , and $i \in {0, 1}$ .
For σ a finite partial oracle, n an integer, and $i \in {0, 1}$ , we say σ 0-deduces that $Φ (n) = i$ if there exists a finite partial oracle ν that agrees with σ such that $Φ^{ν} (n) = i$ .

For α an ordinal, σ a finite partial oracle, n an integer, and $i \in {0, 1}$ , we say σ α-deduces that $Φ (n) = i$ if $Φ^{σ} (n) ↓ = i$ , or if there exist infinitely many $τ ≻_{1} σ$ , each of which β-deduces that $Φ (n) = i$ for some $β < α$ .

We say σ deduces that $Φ (n) = i$ if there is an ordinal α such that σ α-deduces that $Φ (n) = i$ .

We say that σ deduces (or α-deduces) the value of $Φ (n)$ if there is some i such that σ deduces (or α-deduces) that $Φ (n) = i$ .

Lemma 5.6.
Given any Φ, there exists an $α < ω_{1}^{CK}$ such that for all σ, n, and i, if σ deduces that $Φ (n) = i$ then σ α-deduces that $Φ (n) = i$ .
Proof.
Define an operator Γ mapping a set X of elements of the form $⟨ σ, n, i ⟩$ to another such set, defined by the property that $⟨ σ, n, i ⟩ \in Γ (X)$ if one of the following holds:
$⟨ σ, n, i ⟩ \in X$ ;

$Φ^{σ} (n) ↓ = i$ ;

there are infinitely many 1-extensions τ of σ such that $⟨ τ, n, i ⟩ \in X$ .
Then, $Γ (X)$ is arithmetic (in fact, $Π_{2}^{0}$ ) in X, and obviously monotonic (meaning that $Γ (X) \supseteq X$ ).

For all ordinals α, let $Γ_{α}$ denote the αth iteration of Γ on the empty set. (Formally, $Γ_{0} = Γ (\emptyset)$ ; $Γ_{α + 1} = Γ (Γ_{α})$ ; and for α a limit, $Γ_{α} = ⋃_{β < α} Γ_{β}$ .) Then it is easily checked that $Γ_{α}$ is precisely the set of triples $⟨ σ, n, i ⟩$ such that σ α-deduces that $Φ (n) = i$ . By Spector’s boundedness theorem (cf. [10, Corollary 5.6]), there is an $α < ω_{1}^{CK}$ such that $Γ_{α} = Γ_{α + 1}$ . Now if a partial oracle σ deduces that $Φ (n) = i$ then necessarily $⟨ σ, n, i ⟩ \in Γ_{α}$ , hence σ α-deduces that $Φ (n) = i$ , as desired. □
Lemma 5.7.
If $α < ω_{1}^{CK}$ , then $\emptyset^{(2 α + 2)}$ computes the set of $⟨ n, i ⟩$ such that σ α-deduces that $Φ (n) = i$ .
Proof.
We prove, by induction on α, the following statement. If $α < ω_{1}^{CK}$ and a is any ordinal notation for $2 α + 2$ , then whether or not σ α-deduces that $Φ (n) = i$ is uniformly computable in σ, Φ, n, i, a, and $H_{a}$ . (Recall, $H_{a}$ is the set of Turing degree $\emptyset^{(2 α + 2)}$ that can be canonically produced from a, see [10].) The uniformity and the ordinal notations will be needed for the limit stage of the proof.

If $α = 0$ , then to determine whether or not σ α-deduces that $Φ (n) = i$ , we ask whether there exists a ν that agrees with σ such that $Φ^{ν} (n)$ halts and is equal to i. This is computable in $\emptyset^{'}$ , and so also in $\emptyset^{″}$ .

Next, suppose $α = β + 1$ , and assume the result holds for β. To determine whether or not σ α-deduces that $Φ (n) = i$ , we ask whether for infinitely many k not in the domain of σ there is a $τ ≻_{1} σ$ with k in its domain that β-deduces that $Φ (n) = i$ . By induction, whether or not τ β-deduces that $Φ (n) = i$ is uniformly computable in $H_{b}$ , where b is a notation for $2 β + 2$ . Therefore, the question of whether σ α-deduces that $Φ (n) = i$ is uniformly computable in ${(H_{b})}^{″}$ , and hence in $H_{a}$ for a any notation for $| b | + 2 = 2 β + 4 = 2 α + 2$ .

If α is a limit, let $u = 3 \cdot 5^{e}$ with $| u | = α$ . To determine whether or not σ α-deduces that $Φ (n) = i$ , we ask whether for infinitely many k not in the domain of σ there is a v enumerated by $Φ_{e}$ and a $τ ≻_{1} σ$ with k in its domain that $| v |$ -deduces that $Φ (n) = i$ . For each v enumerated by $Φ_{e}$ , we have $| v | < α$ , and so $2 | v | + 2 < α$ since α is a limit. Therefore, $H_{u}$ can uniformly compute whether or not τ $| v |$ -deduces that $Φ (n) = i$ , so ${(H_{u})}^{″}$ can compute whether or not the number of such τ goes to infinity over all v enumerated by $Φ_{e}$ .

There are infinitely many $τ ≻_{1} σ$ that β-deduce that $Φ (n) = i$ for some $β < α$ , if and only if there are infinitely many $τ ≻_{1} σ$ that $| v |$ -deduce that $Φ (n) = i$ for some v enumerated by $Φ_{e}$ . Thus ${(H_{u})}^{″}$ can uniformly compute whether or not σ α-deduces that $Φ (n) = i$ . □
Lemma 5.8.
Suppose $B ⩽_{ii} A$ via Φ, and that $A ↚_{ii} \emptyset^{(α)}$ for every computable ordinal α. If a partial oracle σ for A deduces that $Φ (n) = i$ , then $B (n) = i$ .
Proof.
We prove by induction on α that if σ is a finite partial oracle for A that α-deduces that $Φ (n) = i$ then $B (n) = i$ . If $α = 0$ , then σ α-deducing that $Φ (n) = i$ means that there is a ν that agrees with σ such that $Φ^{ν} (n) ↓ = i$ . In particular, since σ is a partial oracle for A, we have that ν is a partial oracle for A, and so $Φ^{ν} (n)$ cannot be incorrect about $B (n)$ because Φ witnesses an infinite-information reduction from A to B.

Now suppose $α > 0$ , and assume the result for all $β < α$ . If σ is a partial oracle for A that α-deduces that $Φ (n) = i$ , then there are infinitely many $τ ≻_{1} σ$ that β-deduce that $Φ (n) = i$ for some $β < α$ . By assumption, if any of these τ is a partial oracle for A, it follows that $B (n) = i$ . So suppose not. Then since σ was a finite partial oracle for A, we know that any τ that β-deduces that $Φ (n) = i$ for some $β < α$ must disagree with A on the extra bit it has in its domain that σ does not. But then by Lemma 5.7, we can uniformly compute infinitely many such τ using $\emptyset^{(2 α + 2)}$ . Hence $\emptyset^{(2 α + 2)}$ can compute infinitely many incorrect bits of A and thus infinitely many correct bits of A, contradicting the fact that $A ↚_{ii} \emptyset^{(2 α + 2)}$ . □

The proof of Lemma 5.4 now follows.
Proof of Lemma 5.4.
Assume that $A ⩾_{ii} B$ via Φ, and assume that for every $α < ω_{1}^{CK}$ , we have that $B ↚_{ii} \emptyset^{(α)}$ , and $A ↚_{ii} B \oplus \emptyset^{(α)}$ . For each finite partial oracle σ, let $f_{σ}$ be the (potentially multi-valued) partial function where $f_{σ} (n) = i$ if and only if σ deduces that $Φ (n) = i$ . Note that by Lemma 5.8, if σ is a partial oracle for A, then $f_{σ}$ is not multi-valued, and, in fact, gives only outputs that are correct about B.

We claim there exists a finite partial oracle σ for A such that for every $τ ≻_{1} σ$ that is also a partial oracle for A, the domain of $f_{τ}$ is strictly larger than the domain of $f_{σ}$ . (Note that the domain of τ must contain the domain of σ because deduction is defined so that it is monotonic.) Suppose not, and define a sequence $σ_{0} ≺_{1} σ_{1} ≺_{1} \dots$ of finite partial oracles for A, as follows. Let $σ_{0}$ be the empty oracle, and given s, let $σ_{s + 1}$ be any partial oracle for A such that $σ_{s + 1} ≻_{1} σ_{s}$ and $f_{σ_{s + 1}} = f_{σ_{s}}$ . Then $⋃_{s} σ_{s}$ is a partial oracle $(A)$ for A with infinite domain such that if $Φ^{(A)} (n) ↓ = i$ then $σ_{0}$ deduces that $Φ (n) = i$ . But $σ_{0}$ cannot deduce the values of $Φ (n)$ for infinitely many n. This is because, for every $α < ω_{1}^{CK}$ , we have that $A ↚_{ii} \emptyset^{(α)}$ , so by Lemma 5.8 all the facts that $σ_{0}$ can deduce are correct for B. Also, by Lemma 5.6, there is some ordinal $α < ω_{1}^{CK}$ bounding all deductions from $σ_{0}$ . Hence, if $σ_{0}$ could deduce the values of $Φ (n)$ for infinitely many n, then by Lemma 5.7, $\emptyset^{(2 α + 2)}$ could correctly compute infinitely many bits of B. This would contradict that $B ↚_{ii} \emptyset^{(α)}$ for every $α < ω_{1}^{CK}$ .

It follows that the domain of $Φ^{(A)}$ must be finite, because $Φ^{(A)}$ cannot halt on any n such that $σ_{0}$ cannot deduce the value of $Φ (n)$ . This contradicts that Φ witnesses an infinite-information reduction from A to B. Thus the claim is proved.

So fix a σ as given by the claim. Consider the set of all $τ ≻_{1} σ$ such that $f_{τ}$ does not incorrectly compute any bits of B. (Thus, this set includes every 1-extension of σ that is a partial oracle for A, but it may include other 1-extensions.) Let X be the set of numbers that are in the domain of $f_{τ}$ for some such τ but not in the domain of $f_{σ}$ . We consider three cases, each of which leads to a contradiction. Case 1 (There are infinitely many $τ ≻_{1} σ$ such that $f_{τ}$ has an output that disagrees with B on some bit).

In this case, there must be some $α < ω_{1}^{CK}$ such that there are infinitely many $τ ≻_{1} σ$ that incorrectly α-deduce the value of $Φ (n)$ for some n. Thus, $A \leftarrow_{ii} B \oplus \emptyset^{(2 α + 2)}$ .

This is because $B \oplus \emptyset^{(2 α + 2)}$ can search for $τ ≻_{1} σ$ for which τ α-deduces a false output, and whenever it finds such a τ, it knows that the extra bit in the domain of τ disagrees with A. Thus, $B \oplus \emptyset^{(2 α + 2)}$ can compute infinitely many bits of A, and we have in particular a contradiction to the assumption that for each $α < ω_{1}^{CK}$ , $A ↚_{ii} B \oplus \emptyset^{(α)}$ .

Case 2 (There are only finitely many $τ ≻_{1} σ$ such that $f_{τ}$ has an output that disagrees with B on some bit, but X is infinite).

In this case, there must be some $α < ω_{1}^{CK}$ such that there are infinitely many n such that for some $τ ≻_{1} σ$ such that $f_{τ}$ does not incorrectly compute any bits of B τ α-deduces the value of $Φ (n)$ . Thus, $B ⩽_{ii} \emptyset^{(2 α + 2)}$ .

This is because for almost all $τ ≻_{1} σ$ , any output by $f_{τ}$ agrees with B, and by assumption, there are infinitely many n such that τ α-deduces the value of $Φ (n)$ for some such τ. If τ α-deduces that $Φ (n) = i$ , then $f_{τ} (n) = i$ , so in particular, since only finitely many τ can deduce facts that are false, $\emptyset^{(2 α + 2)}$ can search for facts that are α-deduced by $τ ≻_{1} σ$ other than those finitely many τ, and will find infinitely many true facts in this manner. Thus, we have a contradiction to the assumption that for each $α < ω_{1}^{CK}$ , $B ↚_{ii} \emptyset^{(2 α + 2)}$ .

Case 3 (Otherwise).

In this case, by the pigeonhole principle, there must be an $n \in X$ such that $f_{τ} (n) ↓$ for infinitely many $τ ≻_{1} σ$ . Furthermore, it must be that $f_{τ} (n) = B (n)$ for all such τ, since otherwise, we would be in Case 1. In other words, letting $i = B (n)$ , we have that infinitely many 1-extensions of σ deduce that $Φ (n) = i$ . But by definition, this means that σ also deduces that $Φ (n) = i$ , so n could not have been in X, a contradiction.

The proof is complete. □

Note that the uniform bound on the length of deductions given by Lemma 5.6 could actually be used to prove a uniform bound on the α needed to prove Lemma 5.4. By using this bound throughout the construction, we could actually make the sets $B_{0}$ and $B_{1}$ witnessing Theorem 5.1 hyperarithmetic. The modification is straightforward, although we suppressed it for legibility of the overall argument.

We now present a pair of questions concerning joins and maximal pairs in the infinite information degrees.

The first question concerns whether the conditions in Lemma 5.3 are required to prove Theorem 5.1.

Question 5.9.

If $B_{0}$ , $B_{1}$ are mutually 1-random, or mutually 1-generic, do they necessarily form a maximal pair for $⩽_{ii}$ ?

By the proof of Theorem 5.1, mutually $Δ_{1}^{1}$ -random, or mutually $Δ_{1}^{1}$ -generic would be sufficient, but we do not know whether the hyperarithmetic machinery of α-deduction is required for the result.

Our second question, posed by Noah Schweber (private communication), concerns whether joins ever exist in the infinite information degrees.

Question 5.10.

Do there exist reals A, B, C such that the following hold?

$A ≰_{ii} B$ , and $B ≰_{ii} A$ .

$A ⩽_{ii} C$ , and $B ⩽_{ii} C$ .

For any D, if $A ⩽_{ii} D$ , and $B ⩽_{ii} D$ , then $C ⩽_{ii} D$ .

We have shown that under certain hypotheses, joins can fail to exist in the most spectacular way possible. However, we do not know whether under other conditions, joins can exist.

It is tempting to attempt to answer Question 5.10 by letting $A = U \oplus W$ , $B = V \oplus W$ , $C = W$ . This would certainly make $A ⩽_{ii} C$ , and $B ⩽_{ii} C$ . Some finesse in choosing U, V, W can ensure that $A ≰_{ii} B$ , and $B ≰_{ii} A$ . However, the third point seems quite difficult to address.

Footnotes

Acknowledgements

The authors are grateful to Christopher Porter and Theodore Slaman for helpful insights and discussions. They thank the anonymous referees for their valuable comments. Dzhafarov was supported in part by an NSF Postdoctoral Fellowship, and Igusa was supported in part by RTG grant EMSW21-RTG-0838506.

References

P.A.

Cholak and

Igusa, Density-1-bounding and quasiminimality in the generic degrees (to appear).

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer-Verlag, New York, 2010, xxviii + 855 pp.

R.G.

Downey,

C.G.

JockuschJr. and

P.E.

Schupp, Asymptotic density and computably enumerable sets, J. Math. Log. 13(2) (2013), 1350005.

D.D.

Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143(2) (2015), 869–876.

D.R.

Hirschfeldt and

C.G.

JockuschJr., On notions of computability theoretic reduction between

Π_{2}^{1}

principles (to appear).

D.R.

Hirschfeldt,

C.G.

JockuschJr.,

Kuyper and

P.E.

Schupp, Coarse reducibility and algorithmic randomness (to appear).

Igusa, Nonexistence of minimal pairs for generic computability, J. Symbolic Logic 78(2) (2013), 511–522.

Igusa, The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals, J. Symbolic Logic (to appear).

C.G.

JockuschJr. and

P.E.

Schupp, Generic computability, Turing degrees, and asymptotic density, J. Lond. Math. Soc. (2) 85(2) (2012), 472–490.

10.

G.E.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990, xvi + 344 pp.

11.

R.I.

Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, xviii + 437 pp.

Notions of robust information coding

Abstract

Keywords

1. Introduction

4.1. Infinite-information, generic, and coarse reducibilities

Case 2 (There are only finitely many τ ≻ 1 σ such that f τ has an output that disagrees with B on some bit, but X is infinite).

Case 3 (Otherwise).

Footnotes

Acknowledgements

References

Case 2 (There are only finitely many $τ ≻_{1} σ$ such that $f_{τ}$ has an output that disagrees with B on some bit, but X is infinite).