Cardinal invariants,non-lowness classes,and Weihrauch reducibility

Abstract

We provide a survey of results using Weihrauch problems to find analogs between set theory and computability theory. In our treatment, we emphasize the role of morphisms in explaining these coincidences. We end with a discussion of the use of forcing to prove the nonexistence of morphisms.

Keywords

Cardinal invariants Weihrauch reducibility Turing degrees

1. Introduction

In light of the independence of the continuum hypothesis, set theorists searched for more nuanced ways of measuring the size of the continuum. Perhaps, for example, the number of real numbers (singletons) is large, but it doesn’t take many null sets (or meagre sets) to cover the real line? Perhaps there are many functions from ω to ω, but if we’re only interested in growth rates, we can dominate all functions with only a few? Thus are defined cardinal characteristics of the continuum, such as the dominating number $d$ , the smallest size of a family of functions dominating all functions, and $cov (M)$ , the smallest size of a collection of meagre sets whose union is $R$ . Again, the precise values of these cardinals are independent, but we can say much about the relationship between them. For example, no matter the size of the continuum, or the particular values of the two cardinals, we always have $cov (M) ⩽ d$ ; but strict inequality is consistent.

A. Miller (unpublished) and Fremlin [16] have noticed that many cardinal characteristics, including the two mentioned above, can be defined in terms of the smallest size of a set of “solutions” to “instances” of a problem, namely a binary relation. Let $Capture (M)$ be the membership relation between $R$ and $M$ , the collection of meagre sets. Then $cov (M)$ is the smallest size of a set $F \subseteq M$ such that every instance ( $x \in R$ ) has a solution (a meagre set $A ∋ x$ ) in F. The dominating number $d$ is similarly obtained from the domination relation $Dom$ between functions in $ω^{ω}$ .

Further, ZFC proofs of inequalities usually arise from morphisms between the associated problems. For the example above, we write $Capture (M) \to Dom$ to indicate that there are functions $ψ_{inst} : R \to ω^{ω}$ and $ψ_{sol} : ω^{ω} \to M$ such that for all $x \in R$ and $g \in ω^{ω}$ , if $ψ_{inst} (x) Dom g$ then $x Capture (M) ψ_{sol} (g)$ (see Definition 2.5 below). This immediately gives $cov (M) ⩽ d$ , as the $ψ_{sol}$ -image of a complete solution set for $Dom$ is a complete solution set for $Capture (M)$ . A thorough treatment of cardinal characteristics using these concepts was given by Vojtáš [46]. The morphism template gives a clearer presentation of arguments in this area; it also refines the question, because the existence of definable morphisms can be discussed even in the context of CH (see for example [4,11,37]).

At a similar time, Weihrauch and his school [6,17,47] independently developed similar concepts in their study of computable analysis. Again thinking of binary relations as “problems” with instances and solutions, in the light of computability theory, a computable morphism from a problem A to another problem B can be considered a reduction: B has at least as much information as A, because any method of solving B can effectively give us a method of solving A. Given an instance a of A, we effectively translate to an instance $ψ_{inst} (a)$ of B, solve this problem, and then translate (via $ψ_{sol}$ ) to an A-solution for a. When the maps $ψ_{inst}$ and $ψ_{sol}$ are indeed computable, this is called strong Weihrauch reducibility. This approach for classification of problems has spread beyond computable analysis to study $Π_{2}^{1}$ sentences in the context of reverse mathematics [14].

Rupprecht [39] observed similarities between several arguments in computability, especially algorithmic randomness, and set theory. A good example is Terwijn and Zambella’s [43] proof of the equivalence of computable traceability and lowness for Schnorr tests, and Bartoszynski’s [44] characterisation of $cof (N)$ in terms of slaloms (see Section 3.5 below). Rupprecht realised that the binary relations used for cardinal characteristics can be used to define some familiar notions of strength of oracles in computability. The class associated with the problem (binary relation) A, which in this paper we denote by $NL (A)$ , is the collection of oracles which compute an instance for A that has no computable solution. Thus, $NL (Dom)$ is the collection of hyperimmune degrees (not $0$ -dominated), whereas $NL (Capture (M))$ is the collection of oracles which compute weakly 1-generic reals. The morphism from $Capture (M)$ to $Dom$ , being computable, shows that every degree which computes a weakly 1-generic real is hyperimmune.

Unfortunately, Rupprechet’s main body of work was confined to his thesis, and remains otherwise unpublished. Aware of only some of his results, Brendle, Brooke-Taylor, Ng and Nies [8] extended his work and for the first time in print, exhibited how to get both cardinal characteristics and highness classes from the same binary relations (Weihrauch problems). Kihara [24] continued their work, including the morphism machinery, while Kjos-Hanssen et al. [28] answered some of the questions left open in [8].

In this paper we survey the subject and provide a unified and simplified treatment. Many arguments in the literature are opaque, and so we show how to frame them using this template. In many cases a single, simpler argument gives two, and with the aid of duality usually four, results, in set theory and computability. We also provide a way of utilising sequential composition, which has so far eluded computability theorists. This allows us to give the same unified treatment to results of Stephan and Yu [42] about lowness for weak 1-genericity and Greenberg and J. Miller [19], related to [3] about lowness for Kurtz randomness, where, for a change, the argument found in computability gives cleaner morphisms. Nonetheless, we emphasise that most results in this paper are, essentially, not original.

Consistency results in set theory and non-implication results in computability are usually obtained by related forcing notions, and so we end the paper with a brief discussion of forcing. We examine a few basic examples to show how they fit in this framework. Finally we suggest a general research programme that arises naturally from the template that we discuss in this paper.

2. Basics

2.1. Weihrauch problems and effective morphisms

Definition 2.1.
A Weihrauch problem is a triple $A = (A_{inst}, A_{sol}, A)$ where $A_{inst}, A_{sol} \subseteq ω^{ω}$ and A is a binary relation between $A_{inst}$ and $A_{sol}$ , that is, $A \subseteq A_{inst} \times A_{sol}$ . An A-instance is an element of $A_{inst}$ . A solution for an instance a of A is b such that $a A b$ .1
¹
Blass and Rupprecht use “challenges” and “responses”, or “answers”, for instances and solutions. Coskey et al. and Kihara call Weihrauch problems “Vojtáš triples”. Blass calls them “relations”; Rupprecht calls them “debates”. We adopt terminology used in reverse mathematics, which is more widespread.

The sets $A_{inst}$ and $A_{sol}$ are allowed to be complicated. However we will make one assumption:

Both $A_{inst}$ and $A_{sol}$ contain computable points.
Example 2.2.
$Dom$ is the domination problem: an instance is a function $f \in ω^{ω}$ ; a solution is a function g dominating f, denoted $g ⩾^{} f$ , that is, $(\forall^{\infty} n) g (n) ⩾ f (n)$ .
Definition 2.3.
A (total) function $F : ω^{ω} \to ω^{ω}$ is hyperarithmetic piecewise computable* if there is a countable partition $⟨ A_{n} ⟩$ of $ω^{ω}$ into uniformly $Δ_{1}^{1}$ sets such that for all n, $F ↾ A_{n}$ is the restriction to $A_{n}$ of a partial computable function, uniformly in n.

That is, uniformly in n we get a $Δ_{1}^{1}$ index for $A_{n}$ and a partial computable index (a c.e. Turing functional) for a partial computable function $G_{n}$ such that $A_{n} \subseteq dom G_{n}$ and $F ↾ A_{n} = G_{n} ↾ A_{n}$ . An important fact to note is that for all $x \in ω^{ω}$ , $F (x) ⩽_{T} x$ , albeit not quite uniformly.
Remark 2.4.
Fix an effective list $Φ_{e}$ of all partial computable maps from $ω^{ω}$ to $ω^{ω}$ . A map $F : ω^{ω} \to ω^{ω}$ is hyperarithmetic piecewise computable if and only if there is a computable ordinal α and a partial computable map $θ : ω^{ω} \to ω$ such that for all $x \in ω^{ω}$ , $θ (x^{(α)}) ↓$ and $F (x) = Φ_{θ (x^{(α)})} (x)$ . Here $x^{(α)}$ is the $α^{th}$ iteration of the Turing jump of x.
Definition 2.5.
An effective morphism φ from a problem A to a problem B is a pair $φ_{inst}$ , $φ_{sol}$ of hyperarithmetic piecewise computable functions such that:
$φ_{inst} [A_{inst}] \subseteq B_{inst}$ ;

$φ_{sol} [B_{sol}] \subseteq A_{sol}$ ; and

for all $a \in A_{inst}$ , for every B-solution b of $φ_{inst} (a)$ , $φ_{sol} (b)$ is an A-solution of a.

We write $A \to B$ if there is an effective morphism from A to B.

Figure 1.
A morphism.

The idea is that we are reducing A to B; given an A-instance a, we effectively translate it to a B-instance $φ_{inst} (a)$ ; from any B-solution b for $φ_{inst} (a)$ we get a solution $φ_{sol} (b)$ to the original instance. This is like strong Weihrauch reducibility, in that b computes $φ_{inst} (b)$ on its own, without aid of the original instance a; however unlike strong Weihrauch reductions, an effective morphism is not required to be uniform: it is almost uniform, except that we are allowed to define the reduction “by cases”.2
²
Rupprecht uses completely non-uniform maps that only require $f (x) ⩽_{T} x$ for all x, anlogous to Muchnik reductions. Weihrauch and his school use the language of multi-valued functions rather than binary relations. Thus instead of the diagram in Fig. 1 they draw a composition: $φ_{sol} \circ B \circ φ_{inst} (a) \subseteq A (a)$ . The terminology for morphisms varies; Vojtáš called them “generalised Galois–Tukey connections”; Kihara “Tukey connections”; Rupprecht and Blass simply “morphism”, but they reverse the direction.

Observation 2.6.
If $A \to B$ and $B \to C$ then $A \to C$ . Also $A \to A$ . We write $A \leftrightarrow B$ when $A \to B$ and $B \to A$ .
2.2. The associated cardinal and highness class

Definition 2.7.
Let A be a problem. A complete solution set for A is a set $Z \subseteq A_{sol}$ such that every A-instance has a solution in Z. We let
³
Blass and Rupprecht use the notation $‖ A ‖$ and call it the norm of A. Brendle et al. write $d (A)$ and call it the domination number of A.

$\begin{matrix} Card (A) = min {| Z | : Z is a complete solution set for A} .^{3} \end{matrix}$
Definition 2.8.
For a problem A we let $H (A)$ , the highness class associated with A, be the collection of oracles $x \in 2^{ω}$ which compute some $c \in A_{sol}$ that solves every computable A-instance.
Example 2.9.
A complete solution set for $Dom$ is a set of functions dominating all functions $f : ω \to ω$ . $Card (Dom)$ , denoted by $d$ and known as the dominating number, is the smallest size of a dominating family, that is, the cofinality of the pre-partial ordering $(ω^{ω}, ⩽^{*})$ .

$H (Dom)$ is the collection of high degrees (Martin [13]): those that compute functions that dominate all computable ones.
Proposition 2.10 (Vojtáš [46]; Rupprecht [39]).

Suppose that $A \to B$ . Then:

$Card (A) ⩽ Card (B)$ ; and

$H (B) \subseteq H (A)$ .

Proof.
Let $φ = (φ_{inst}, φ_{sol})$ be an effective morphism from A to B.

(a): Let Z be a complete solution set for B; let $W = φ_{sol} [Z]$ . Then $| W | ⩽ | Z |$ and W is a complete solution set for A.

(b): Let $x \in H (B)$ ; let $b ⩽_{T} x$ be a B-solution for all computable B-instances. Let a be a computable A-instance. Then $φ_{inst} (a)$ is a computable B-instance; so $φ_{inst} (a) B b$ . It follows that $φ_{sol} (b)$ is an A-solution for a. As $φ_{sol} (b) ⩽_{T} b ⩽_{T} x$ , it witnesses that $x \in H (A)$ . □
2.3. Duality

Definition 2.11.
For a problem B we define its dual $B^{⊥}$ to be $/ B$ . That is, the relation on $B_{sol} \times B_{inst}$ defined by $x B^{⊥} y ⟺ \neg (y B x)$ . We let ${(B^{⊥})}_{inst} = B_{sol}$ and ${(B^{⊥})}_{sol} = B_{inst}$ .

Hence ${(A^{⊥})}^{⊥} = A$ .
Lemma 2.12.
If $A \to B$ then $B^{⊥} \to A^{⊥}$ .
Proof.
Suppose that φ is an effective morphism from A to B. Define a morphism ψ by letting $ψ_{inst} = φ_{sol}$ and $ψ_{sol} = φ_{inst}$ . Then ψ reduces $B^{⊥}$ to $A^{⊥}$ : if $b \in B_{sol} = {(B^{⊥})}_{inst}$ and $a \in A_{inst} = {(A^{⊥})}_{sol}$ is such that $ψ_{inst} (b) A^{⊥} a$ , that is, $a / A φ_{sol} (b)$ , then it cannot be that $φ_{inst} (a) B b$ , so $b B^{⊥} ψ_{sol} (a)$ . □
Definition 2.13.
For a problem A, the non-lowness class associated with A is $NL (A) = H (A^{⊥})$ .

So $x \in NL (A)$ if and only if x computes an A-instance which has no computable A-solution.4
⁴
We used “highness” for $H (A)$ because of the analogy with high degrees and their coincidence with $H (Dom)$ . We defined it first because its definition is more straightforward. However, we will see in the rest of the paper that the operator $NL (A)$ is better behaved, in particular with respect to sequential composition, and its relationship with forcing. Rupprecht calls $NL (A)$ the Turing norm of A and denotes it by $⟨ A ⟩$ . Brendle et al. write $D (A)$ for $NL (A)$ and $B (A)$ for $H (A)$ , which they do define first; this is analogous to their notation $b (A)$ for $Card (A^{⊥})$ . They call both $D (A)$ and $B (A)$ “highness properties”. Kihara writes ${[A]}_{Δ_{1}^{0}}$ for $NL (A)$ .

Corollary 2.14.
If $A \to B$ then $NL (A) \subseteq NL (B)$ .
Example 2.15.
The dual of $Dom$ is $Esc$ : a solution for $g \in ω^{ω}$ is a function escaping g, that is, not dominated by g.

$Card (Esc) = b$ is the unbounding number: the smallest size of an unbounded family.

$H (Esc) = NL (Dom)$ is the collection of hyperimmune degrees (not $0$ -dominated): those that compute escaping functions, functions not dominated by any computable function. $NL (Esc) = H (Dom)$ is high.

The problem $Esc$ reduces to $Dom$ : map an $Esc$ -instance to itself; map a $Dom$ -solution g to $g + 1$ . Hence: $b ⩽ d$ ; and every high degree is hyperimmune.5
⁵
Our notation $NL (A)$ , as is Brendle et al.’s, is motivated by this simplest example, $Dom$ and $Esc$ : $NL (Dom)$ is a weaker property that $H (Dom)$ . However this example is misleading, as usually there is no reduction from A to $A^{⊥}$ or vice-versa. Possibly better notation would be $H^{⊥} (A)$ for $NL (A)$ ; however we find this typographically annoying.

Example 2.16.
Let $Split$ be the splitting problem: an instance is an infinite subset a of ω (viewed as an element of $2^{ω} \subset ω^{ω}$ ); a solution is an infinite subset b of ω which splits a, meaning that both $a \cap b$ and $a ∖ b = a \cap b^{∁}$ are infinite. (Note that in this example the sets of instances and solutions are not all of $ω^{ω}$ but a $Π_{2}^{0}$ subset of $ω^{ω}$ .)

$Card (Split)$ , the splitting number, denoted by $s$ , is the smallest size of a set of subsets of ω which split every infinite set. $Card ({Split}^{⊥})$ , denoted by $r$ and sometimes called the reaping number, is the smallest size of a collection of infinite subsets of ω for which no single infinite subset of ω splits them all.

$H (Split)$ is the collection of oracles which compute a bi-immune set: a set with no infinite c.e. subset of it or of its complement. This is because every infinite c.e. set contains an infinite computable set.

$NL (Split)$ is the collection of oracles which compute r-cohesive sets: infinite sets c such that for every computable set a, $c \subseteq^{} a$ or $c \subseteq^{} a^{∁}$ .
Lemma 2.17.
$Split \to Dom$ .
Proof.
We define a morphism ψ. On the instance side, map an infinite set $a \subseteq ω$ to its principal function $p_{a}$ . On the solution side, the idea is that if g dominates $p_{a}$ then from g we can get a partition of ω into intervals $⟨ I_{n} ⟩$ , each of which contains an element of a; from this we easily build a set that splits a. So formally, given $g \in ω^{ω}$ , we define $ψ_{sol} (g)$ as follows. Let $h (0) = 0$ and $h (n + 1) = g (h (n) + 1)$ ; let $I_{n} = (h (n), h (n + 1)]$ ; let $ψ_{sol} (g) = ⋃_{n} I_{2 n}$ . □

As a result, we see that $s ⩽ d$ , $b ⩽ r$ , every high degree computes a bi-immune set, and every r-cohesive set has hyperimmune degree.
3. Represented spaces, measure and category

Since we allow the collections $A_{inst}$ and $A_{sol}$ of instances and solutions of a problem to be subsets of $ω^{ω}$ , we can formulate problems whose instances or solutions, for example, are elements of Cantor space, or collections of bounded functions. However at times we will want to deal with objects that are not in Baire space, for example, real numbers, or some definable subsets of Baire space. For this, we use the terminology of represented spaces.

Definition 3.1.
A representation of a set X is a partial function from $ω^{ω}$ onto X.

If π is a representation of X then $a \in dom π$ is called a π-name for $π (a)$ . We then say that $y \in 2^{ω}$ computes $x \in X$ if x has a y-computable name. We choose representations so that this aligns with our preconceived notions of computation.

Below we will define problems whose instances or solutions are elements of represented spaces. In all cases this is shorthand for the induced problems on the names: if π is a representation of X, for example, then we will define a problem $A \subseteq X \times ω^{ω}$ , but really we will mean the problem $\hat{A} \subseteq dom π \times ω^{ω}$ defined by ${\hat{A}}_{inst} = π^{- 1} A_{inst}$ and $x \hat{A} y$ means $π (x) A y$ . We will identify A with $\hat{A}$ .
3.1. Meagre sets

The first example is the collection of $Σ_{2}^{0}$ meagre subsets of Baire space. A name for a closed, nowhere dense subset P of $ω^{ω}$ is the characteristic function of a tree $T \subseteq ω^{< ω}$ such that $P = [T]$ (we use a computable bijection between ω and $ω^{< ω}$ ). Trees are allowed to have leaves (strings with no extensions on the tree). By a canonical identification of Baire space with its power ${(ω^{ω})}^{ω}$ , we let $⟨ T_{n} ⟩$ be a name for $⋃ [T_{n}]$ .

We let $M$ be the collection of $Σ_{2}^{0}$ meagre sets. As described above, we identify a name for a meagre set with the set that it names, so we also think of $M$ as the collection of names for $Σ_{2}^{0}$ meagre sets.

Remark 3.2.
Since every effectively closed set is the set of paths through a computable tree, and this is uniform and relativises, we see that a $Σ_{2}^{0}$ meagre set is x-computable if and only if it is $Σ_{2}^{0} (x)$ .

Two problems are typically associated with ideals of small sets, in this case the meagre ones:

$Capture (M)$ : an instance is a point $y \in ω^{ω}$ ; a solution is a meagre set M such that $y \in M$ .

$Supset (M)$ : an instance is a meagre set M; a solution is a meagre set $\tilde{M}$ such that $M \subseteq \tilde{M}$ .

$Card (Capture (M))$ is known as $cov (M)$ : the smallest number of meagre sets it takes to cover $ω^{ω}$ . $H (Capture (M))$ is the class of $x \in 2^{ω}$ which compute a meagre set that contains all computable reals: the weakly meagre engulfing oracles.6
⁶
The terminology originates from [8].

The dual of $Capture (M)$ is $Pass (M)$ , the problem of finding a point outside a given meagre set. $Card (Pass (M))$ is $non (M)$ (also known as the uniformity number $unif (M)$ ), the smallest size of a non-meagre set. $H (Pass (M))$ is the class of $x \in 2^{ω}$ which compute a weakly 1-generic function.

$Card (Supset (M))$ is $cof (M)$ , the cofinality of the partial order $(M, \subseteq)$ . The class $H (Supset (M))$ consists of the (strongly) meagre englufing oracles: those which compute a meagre set covering (i.e. a superset of) all computable meagre sets.

The dual of $Supset (M)$ is $Spill (M)$ , the problem of finding a meagre set which is not covered by a given meagre set. $Card (Spill (M))$ is $add (M)$ , the additivity number for the meagre sets: the smallest number of meagre sets whose union is not meagre. $H (Spill (M))$ is the class of oracles which are not low for meagre sets.
Proposition 3.3.
$Capture (M) \to Dom$ .
Proof.
Map the instance f to itself. Map a $Dom$ -solution $g \in ω^{ω}$ to the meagre set consisting of all functions dominated by g.

More precisely, let $T_{n} (g)$ be the tree of $σ \in ω^{< ω}$ such that for all $k ⩾ n$ , if $k < | σ |$ then $σ (k) ⩽ g (k)$ ; map g to $⟨ T_{n} (g) ⟩$ . □

As a result we see:

$cov (M) ⩽ d$ and $b ⩽ non (M)$ .

Every high degree is weakly meagre engulfing; every weakly 1-generic degree is hyperimmune.
Proposition 3.4.
$Pass (M) \to Supset (M)$ .
Proof.
Uniformly, given (a name of) a meagre set M, we can find a point $x \notin M$ : since M is given as a sequence $⟨ T_{n} ⟩$ of nowhere dense trees, we construct $x \notin ⋃_{n} [T_{n}]$ by initial segments, first finding a string $σ_{0}$ off $T_{0}$ , then an extension $σ_{1}$ off $T_{1}$ , and so on.

The morphism maps an instance M of $Pass (M)$ to itself, and a solution $\tilde{M} \supseteq M$ to a real outside $\tilde{M}$ .

Note that for the map of solutions to be total, we cannot produce a partial sequence $⟨ σ_{n} ⟩$ in case we are given a tree which is somewhere dense. However the collection of names for meagre sets is arithmetic, so we are allowed to define the map of solutions in an arbitrary way outside $M$ . □
Remark 3.5.
The previous morphism exhibits the importance of allowing functions on names that do not induce maps on the named objects. Given two names $⟨ T_{n} ⟩$ and $⟨ S_{n} ⟩$ of the same meagre set M, the resulting point outside M will very likely depend on the name.
Proposition 3.6.
$Dom \to Supset (M)$ .
Proof.
On the instance side, map a function f to the meagre set $M_{f}$ consisting of all f-dominated functions. By first replacing f by $\sum_{i ⩽ n} f (i)$ , we may assume that f is non-decreasing.

On the solution side, we elaborate on the construction of a point outside a given meagre set $M = ⋃_{n} [T_{n}]$ (applying that construction would yield a morphism from $Esc$ to $Supset (M)$ , which is weaker). Given $⟨ T_{n} ⟩$ , for each n and $k < ω$ we can effectively obtain a string $σ_{n, k}$ such that for all k-bounded strings τ of length k, $τ \hat{} σ_{n, k} \notin T_{n}$ . We may assume that $T_{0} \subseteq T_{1} \subseteq T_{2} \subseteq \dots$ . By extending $σ_{n, k}$ , we may assume that $max range σ_{n, k} > k$ .

We then recursively define $g (0) = 0$ and $g (n + 1) = max range σ_{n, g (n)}$ . So g is strictly increasing. Let $J_{n} = [g (n), g (n) + | σ_{n, g (n)} |]$ . For all $y \in ω^{ω}$ , if $y ↾ g (n)$ is $g (n)$ -bounded and $y ↾ J_{n} = σ_{n, g (n)}$ , then $y \notin [T_{n}]$ .

We claim that if $M_{f} \subseteq M$ , that is, if M contains all f-dominated functions, then $f ⩽ g (n + 1)$ .

Suppose not. Then there is an infinite set X such that for all $n \in X$ , $g (n + 1) ⩽ f (n)$ . We may thin out X so that the intervals $J_{n}$ for $n \in X$ are pairwise disjoint and $m > n$ in X implies $m > g (n + 1)$ .

We can then build a function $x \in ω^{ω}$ such that for all $n \in X$ , $x ↾ J_{n} = σ_{n, g (n)}$ . Outside these intervals we set the values of x to be 0. If $n \in X$ and $i \in J_{n}$ then $x (i) = σ_{n, g (n)} (i) ⩽ g (n + 1)$ . If $m \in X$ and $m > n$ then as $m > g (n + 1)$ , this shows that $x ↾ g (m)$ is $g (m)$ -bounded. It follows that $x \notin M$ . On the other hand, for $n \in X$ , $g (n + 1) ⩽ f (n)$ and as f is non-decreasing, $f (n) ⩽ f (i)$ for all $i \in J_{n}$ , so $x ⩽ f$ . □

Combining Propositions 3.3 and 3.6 we see that $Capture (M) \to Supset (M)$ (and so also $Spill (M) \to Pass (M)$ ). This actually has a quick direct proof: on the instance side, map a function f to the singleton ${f}$ (it is easy to effectively obtain a tree T such that $[T] = {f}$ ). On the solution side we use the identity function.
3.2. Other spaces

We have looked at meagre subsets of Baire space, but we could equivalently examine either Cantor space or the real line. We show that the corresponding problems are all morphism-equivalent. For this subsection, for any one of the spaces $X \in {ω^{ω}, 2^{ω}, R}$ , denote by $M_{X}$ the collection of $Σ_{2}^{0}$ meagre subsets of X.

Let us first deal with Cantor space. Here $M_{2^{ω}}$ is a subset of $M_{ω^{ω}}$ , with the names being infinite sequences of nowhere dense subtrees of $2^{< ω}$ . Define $ρ : ω^{ω} \to 2^{ω}$ by letting $\begin{matrix} ρ (f) = 0^{f (0)} 10^{f (1)} 10^{f (2)} 1 \dots . \end{matrix}$ It is a bijection between Baire space and the collection of (characteristic functions of the) infinite subsets of ω. The map ρ is induced by a corresponding map from $ω^{< ω}$ to $2^{< ω}$ , which we also call ρ: $ρ (⟨ n_{0}, n_{1}, \dots, n_{k} ⟩) = 0^{n_{0}} 10^{n_{1}} 1 \dots 10^{n_{k}}$ .

For any meagre set $M \subset 2^{ω}$ , $ρ^{*} (M) = ρ^{- 1} [M]$ is a meagre subset of $ω^{ω}$ . Further, a name for $ρ^{*} (M)$ can be effectively obtained from a name for M: the sequence $⟨ T_{n} ⟩$ (with $T_{n} \subset 2^{< ω}$ ) is sent to $⟨ ρ^{- 1} [T_{n}] ⟩$ .

For $M \subseteq ω^{ω}$ we let $ρ_{*} (M) = ρ [M] \cup {x \in 2^{ω} : x is finite}$ . M is meagre if and only if $ρ_{*} (M)$ is meagre, and a name for $ρ_{*} (M)$ is effectively obtained from a name for M: map a sequence $⟨ S_{n} ⟩$ to $⟨ T_{n} ⟩$ where $\begin{matrix} T_{n} = {ρ (σ) \hat{} 0^{k} : σ \in S_{n} & k < ω} \cup {τ \in 2^{< ω} : τ has up to n 1’s} . \end{matrix}$

Lemma 3.7.
$Capture (M_{2^{ω}}) \leftrightarrow Capture (M_{ω^{ω}})$ and $Supset (M_{2^{ω}}) \leftrightarrow Supset (M_{ω^{ω}})$ .
Proof.
To reduce $Capture (M_{ω^{ω}})$ to $Capture (M_{2^{ω}})$ , on the instance side use ρ and on the solution side use $ρ^{}$ . In the other direction, on the instance side map an infinite set x to $ρ^{- 1} (x)$ , and a finite set x to some fixed point, say the constant function 0. On the solution side use $ρ_{}$ . In either case this will work, because $ρ_{} (M)$ will always contain all finite sets.

To reduce $Supset (M_{ω^{ω}})$ to $Supset (M_{2^{ω}})$ , use $ρ_{}$ on the instance side and $ρ^{}$ on the solution side. We just need to check that if $\tilde{M} \supseteq ρ_{} (M)$ then $M \subseteq ρ^{} (\tilde{M})$ . In the other direction, use $ρ^{}$ on the instance side and $ρ_{*}$ on the solution side; check the same thing. □

We conclude that $cov (M_{2^{ω}}) = cov (M_{ω^{ω}})$ , $cof (M_{2^{ω}}) = cof (M_{ω^{ω}})$ (and the same holds for $add (M)$ and $non (M)$ ), and that the highness classes coincide. So: computing a weakly 1-generic function in Baire space is equivalent to computing a weakly 1-generic sequence in Cantor space, lowness for meagre sets coincides, and the engulfing properties (weak and strong) coincide for Baire space and Cantor space.

For the real numbers, we need to choose representations. We use standard ones; $R$ is represented using Cauchy names (quickly converging Cauchy sequence) – although since we do not require the morphism maps to be uniform, representation using binary expansions would be equivalent. Open subsets of $R$ are represented by sequences of rational intervals (named by their endpoints) whose union is the open set; closed names are given by taking the complement; names for $Σ_{2}^{0}$ subsets of $R$ are sequences of closed names. As above, we can use Baire category-preserving maps to obtain morphism equivalence of the problems $Capture (M_{ω^{ω}})$ and $Capture (M_{R})$ , usually passing through the unit interval first. For example, we can use the binary expansion map from Cantor space onto $[0, 1]$ , or the homeomorphism of Baire space with the irrationals in $(0, 1)$ . We just need to check that these maps are $Σ_{2}^{0}$ -measurable, effectively. Remark 3.8.
The reduction $Capture (M_{2^{ω}}) \to Capture (M_{ω^{ω}})$ is an instance of a morphism ψ for which $ψ_{inst} ↾ A_{inst}$ is not computable (the restriction of a partial computable function to $A_{inst}$ ). This is because the map depends on whether x is infinite or not. This, and the reduction for $M_{R}$ , are the only such reductions in this paper.

3.3. Null sets

We use similar techniques to name null $Π_{2}^{0}$ subsets of $2^{ω}$ . An open set is named by (the characteristic function of) a subset U of $2^{< ω}$ ; we may assume it is upwards closed in $2^{< ω}$ . This means that under this naming scheme, x is a name for an open set U if and only if the complement $x^{∁}$ of x is a name for the closed set $2^{ω} ∖ U$ under the scheme of naming closed sets by trees used above. We abuse notation by using U to denote both a set of strings and the open set (sometimes denoted ${[U]}^{≺}$ ) generated by U.

As we are dealing with relatively computable names, rather than relatively c.e. names, we do not require that $[σ] \subseteq U$ implies $σ \in U$ . This is the analogue of allowing terminal nodes in our trees naming closed sets.

A name for a null $Π_{2}^{0}$ set is essentially a Schnorr test: it consists of a pair of sequences $⟨ U_{n} ⟩$ and $⟨ λ (U_{n}) ⟩$ , where $U_{n}$ is (a name for) an open set and $λ (U_{n})$ is (a name for) the real number which is the fair-coin measure of $U_{n}$ . We require that $λ (U_{n}) ⩽ 2^{- n}$ . The null set named is $⋂_{n} U_{n}$ . We do not require the test to be nested, but this can be obtained by replacing $⟨ U_{n} ⟩$ by $⟨ V_{n} ⟩$ where $V_{n} = ⋃_{m > n} U_{m}$ ; the sequence $⟨ λ (V_{n}) ⟩$ (as well as the sequence of sets of strings $⟨ V_{n} ⟩$ ) is computed from $⟨ U_{n} ⟩$ and $⟨ λ (U_{n}) ⟩$ .

We note that an alternative naming system would be omitting the sequence of measures $⟨ λ (U_{n}) ⟩$ and simply requiring that $λ (U_{n}) = 2^{- n}$ (see for example [15, Prop.7.1.6]). We also remark that unlike the naming scheme for $R$ , when naming infinite sequences of real numbers we do need to use quickly converging Cauchy sequences rather than binary expansions, as we cannot pass between them using piecewise continuous functions: for each coordinate we need to know whether the real in that coordinate is a binary rational or not, and there are continuum many possibilities.

For any oracle x, the x-computable null sets are the x-Schnorr null sets. The associated cardinals and highness classes are:

$Card (Capture (N)) = cov (N)$ is the smallest number of null sets it takes to cover the reals; the elements of $H (Capture (N))$ are the weakly null engulfing (or weakly Schnorr engulfing) oracles, those that compute a null set containing all computable points.

$Card (Supset (N)) = cof (N)$ is the cofinality of $(N, \subseteq)$ ; $H (Supset (N))$ is the class of (strongly) null engulfing oracles, those that compute a null set covering all computable Schnorr null sets.

$Card (Pass (N)) = non (N)$ is the smallest size of a non-null set; an oracle is in $H (Pass (N))$ if and only if it computes a Schnorr random real.

$Card (Spill (N)) = add (N)$ is the smallest number of null sets whose union is not null; $H (Spill (N))$ is the class of oracles which are not low for Schnorr null sets.

The two basic morphisms that apply to most σ-ideals apply to null sets as well:

Proposition 3.9.
$Capture (N) \to Supset (N)$ and $Pass (N) \to Supset (N)$ .
Proof.
The same as for meagre, noting that given a name $⟨ U_{n} ⟩$ for a null set we can effectively compute a point outside the null set $⋂_{n} U_{n}$ . Indeed we can build $x \notin U_{1}$ , defining it bit by bit, by ensuring that $λ ([x ↾ n] ∖ U_{1}) > 0$ . We use the fact that for all clopen C, $λ (C \cap U_{1})$ is uniformly computable from $U_{1}$ and $λ (U_{1})$ .

Also, it is easy, given $x \in 2^{ω}$ , to find a name for ${x}$ as a null set. □
Remark 3.10.
By forgetting the sequence $⟨ λ (U_{n}) ⟩$ , we could have easily defined the representation of null sets using Martin-Löf tests, which would make the effective notions correspond to computing ML-random reals and so on. But the most basic morphisms (as in Proposition 3.9) would not work for such a representation. Schnorr is the correct effective analogue to set-theoretic randomness, because in set theory there is no sense to “not knowing” the exact measure of an open set.

3.4. Category and measure – an easy morphism

We start by observing a relatively simple connection between category and measure. We use:

Lemma 3.11.
There are an effectively null (Schnorr null) set and an effectively meagre set which form a partition of $2^{ω}$ .
Proof.
This can be done in many ways. For example, use a pairing function to identify ω with $ω^{2}$ , and let $U_{n} = ⋃_{m} C_{n, k}$ , where $C_{n, k}$ is determined by finitely many bits on the $k^{th}$ column of ω; for example $\begin{matrix} C_{n, k} = {x \in 2^{ω} : x (k, 0) = x (k, 1) = \dots = x (k, k + n) = 0} . \end{matrix}$ □
Proposition 3.12.
$Capture (M) \to Pass (N)$ .

Dualising we get $Capture (N) \to Pass (M)$ . As a result, $cov (M) ⩽ non (N)$ and $cov (N) ⩽ non (M)$ ; and every Schnorr random is weakly meagre engulfing, whereas every weakly 1-generic is weakly null engulfing. Proof.
By Lemma 3.11, we fix a computable null set N and a computable meagre set M which partition $2^{ω}$ . We then let, for $x \in 2^{ω}$ , $\begin{matrix} ψ_{inst} (x) = x △ N = {x △ y : y \in N} \end{matrix}$ and for $y \in 2^{ω}$ we let $ψ_{sol} (y) = y △ M$ . The map $x \mapsto x △ y$ is measure and category-invariant, so indeed $x △ N$ is null and $y △ M$ is meagre. And if $y \notin x △ N$ then $x △ y \notin N$ so $x △ y \in M$ so $x \in y △ M$ . □

3.5. Tracing

The material in this section was discovered by Bartoszynski [44], by Raisonnier and Stern [38], and then independently by Terwijn and Zambella [43].

A trace is a function $T : ω \to P_{ω} (ω) = {[ω]}^{< ω}$ . An order function is a computable, non-decreasing, unbounded function.7

⁷
Terminology by Schnorr [41].

If h is an order function then an h-trace is a trace T such that for all n,

| T (n) | ⩽ h (n)

. In set theory, traces are known as slaloms. A trace T traces a function

f \in ω^{ω}

(\forall^{\infty} n) f (n) \in T (n)

. By canonically coding finite sets of natural numbers by natural numbers, we represent traces by elements of Baire space. The most basic problem involving traces is

h - Trace

: an instance is a function

f \in ω^{ω}

, a solution is an h-trace T which traces f.

Traces are used extensively in algorithmic randomness and computability. See, for example, [15,21,34].

Lemma 3.13.

For any two order functions h and $\tilde{h}$ , $h - Trace \leftrightarrow \tilde{h} - Trace$ .

We therefore simply write $Trace$ for the equivalent problems $h - Trace$ .

Proof.

Let h, $\tilde{h}$ be order functions; we reduce $h - Trace$ to $\tilde{h} - Trace$ . We say that k is responsible for n if $\tilde{h} (k) ⩽ h (n) < \tilde{h} (k + 1)$ . Then for every n with $h (n) ⩾ \tilde{h} (0)$ , a unique k is responsible for n, and every k is responsible for finitely many n.

On the instance side, map $f \in ω^{ω}$ to $\tilde{f}$ defined by $\tilde{f} (k) = f ↾ (n + 1)$ , where n is the greatest such that k is responsible for n. If k is responsible for no n (for example if $\tilde{h} (k) = \tilde{h} (k + 1)$ ) then it doesn’t matter what $\tilde{f} (k)$ is.

On the solution side, we map a $\tilde{h}$ -trace T to the h-trace S defined by $\begin{matrix} S (n) = {σ (n) : σ \in T (k), where k is responsible for n}, \end{matrix}$ letting $S (n)$ be empty if $h (n) < \tilde{h} (0)$ . □

$NL (Trace)$ is the collection of oracles which are not computably traceable. An oracle x is computably traceable if every x-computable function has a computable h-trace, for some fixed (or all) order functions h. It is not difficult to see that $Dom \to Trace$ (an instance is mapped to itself, a trace S is mapped to $n \mapsto max S (n)$ ); the resulting containment $NL (Dom) \subseteq NL (Trace)$ says (in contrapositive) that every computably traceable degree is $0$ -dominated (hyperimmune-free). The containment $H (Trace) \subseteq H (Dom)$ says that if there is an x-computable h-trace that traces all computable functions, then x is high. In fact, it is not difficult to see that $H (Trace) = H (Dom)$ , that is, $H (Trace)$ is the collection of high degrees: suppose that x is high. The set of indices of computable functions is $Δ_{2}^{0} (x)$ . Approximating this set, we let $T (n)$ be the set of values $φ_{e, s} (s)$ for all $e < s$ which are believed to be total at stage s. This is an identity-bounded, x-computable trace that traces all computable functions. Note how this proof relies on special properties of high degrees (and the enumeration of partial computable functions) that go beyond merely using a dominating function. This proof has no analogue in set theory, and indeed, the associated cardinals can be distinct.

Our next goal is the following combinatorial characterisation of the cofinality of the null ideal.

Theorem 3.14.

$Trace \leftrightarrow Supset (N)$ .

Proof of

Supset (N) \to Trace

Define an order function h so that for large enough n, $2^{- 2 n} \sum_{k < ω} h (2 n, k) \cdot 2^{- k} ⩽ 2^{- n}$ , and that this sum is computable, uniformly in n.

On the instance side: given a null set $N = ⋂ U_{n}$ , let, for $n, k < ω$ , $s (n, k)$ be a stage s such that $λ (U_{n, s}) ⩾ λ (U_{n}) \cdot (1 - 2^{- k})$ , where $U_{n, s} = U_{n} \cap {0, 1}^{⩽ s}$ . Let $s (n, - 1) = 0$ . We map N to the function $(n, k) \mapsto U_{n, s (n, k)} - U_{n, s (n, k - 1)}$ . A value of this function is a clopen set, so is coded by a finite subset of $2^{< ω}$ , and hence by a natural number.

On the solution side, given an h-trace T, we may assume that for all $n, k$ , every element of $T (n, k)$ is a clopen set of measure at most $2^{- n - k}$ . We then map T to a name $⟨ V_{n} ⟩$ for a null set, defined by letting, for sufficiently large n, $V_{n} = ⋃_{k < ω} ⋃ T (2 n, k)$ . The properties of h ensure that $λ (V_{n}) ⩽ 2^{- n}$ . The uniform computability of the sums above implies that the sequence $⟨ λ (V_{n}) ⟩$ can be obtained from T.

For all n, $U_{2 n} \subseteq V_{n}$ , so $⋂ U_{n} \subseteq ⋂ V_{n}$ . □

Proof of

Trace \to Supset (N)

We define an array of clopen sets $B_{m, k}$ : $\begin{matrix} B_{m, k} = {x \in 2^{ω} : x (k, 0) = x (k, 1) = \dots = x (k, m - 1) = 0} . \end{matrix}$ For each m, the family of sets $⟨ B_{m, k} ⟩$ is independent (in the sense of probability theory), and $λ (B_{m, k}) = 2^{- m}$ . Further, for any clopen set C and m, for some k, the family ${C, B_{m, k}, B_{m, k + 1}, B_{m, k + 2}, \dots}$ is independent.

We also fix a computable map $D \mapsto q_{D}$ from clopen sets to positive binary rational numbers, such that $\sum_{D} q_{D} ⩽ 1 / 8$ . For each clopen set D, we let $h_{D} (n) = ⌈ 1 / {log}_{q_{D}} (1 - 2^{- n}) ⌉$ . This is an order function. The granularity of a clopen set D is the least k such that D is the union of clopen sets $[σ]$ for binary strings σ of length k. We let $\begin{matrix} h (n) = \sum {h_{D} (n) : D is a clopen set of granularity ⩽ n} . \end{matrix}$ We reduce $h - Trace$ to $Supset (N)$ .

On the instance side, the map is relatively simple: we map $f \in ω^{ω}$ to $⟨ U_{n} ⟩$ , where $U_{n} = ⋃_{m > n} B_{m, f (m)}$ . The sequence $⟨ λ (U_{n}) ⟩$ is obtained effectively from f.

On the solution side, we work a bit. Given a name $⟨ V_{n} ⟩, ⟨ λ (V_{n}) ⟩$ of a null set, we will actually only use $V_{2}$ and $λ (V_{2})$ . We first define an open set $W \supseteq V_{2}$ such that $λ (W) ⩽ 1 / 2$ , W and $λ (W)$ are computable given $V_{2}$ and $λ (V_{2})$ , and for every clopen set D, if $λ (D ∖ W) < q_{D}$ then $D \subseteq W$ . The idea is to copy $V_{2}$ . For each D, we calculate $λ (D ∖ W_{2})$ sufficiently precisely so that if it is close to $q_{D}$ (say significantly smaller that $2 q_{D}$ ), then we add all of D to W.

We then let, for every clopen set D such that $D ⊈ W$ and $n < ω$ , $\begin{matrix} T_{D} (n) = {k : B_{n, k} \cap D \subseteq W}; \end{matrix}$ if $D \subseteq W$ then $T_{D} (n) = \emptyset$ . We let $\begin{matrix} T (n) = ⋃ {T_{D} (n) : D is a clopen set of granularity ⩽ n} . \end{matrix}$ We first observe that T is an h-trace, which amounts to showing, for all clopen D, that $T_{D}$ is an $h_{D}$ -trace. Suppose that $D ⊈ W$ . For all $k \in T_{D} (n)$ , $D ∖ W \subseteq B_{n, k}^{∁}$ ; as the sets $B_{n, k}$ are independent, $\begin{matrix} q_{D} ⩽ λ (D ∖ W) ⩽ {(1 - 2^{- n})}^{| T_{D} (n) |}, \end{matrix}$ so $\begin{matrix} | T_{D} (n) | ⩽ {log}_{(1 - 2^{- n})} (q_{D}) = 1 / {log}_{q_{D}} (1 - 2^{- n}) ⩽ h_{D} (n) . \end{matrix}$

Our task now is to show that T is computable, given W and $λ (W)$ . To do this we show that using W and $λ (W)$ , the sets $T_{D} (n)$ are computable, uniformly in D and n; and that we can, again uniformly in D and n, compute an upper bound for the elements of $T_{D} (n)$ .

For the former, we observe that the collection of clopen subsets of W is computable from W and $λ (W)$ . For $C \subseteq W$ if and only if $λ (C ∖ W) < q_{C}$ if and only if $λ (C ∖ W) = 0$ , and $λ (C ∖ W)$ is computable, uniformly in C. So we can tell if $D \subseteq W$ , and if not, then for all k, whether $B_{n, k} \cap D \subseteq W$ or not.

For the latter, suppose that D is clopen and $D ⊈ W$ . So $λ (W | D) < 1$ , where $λ (X | D)$ is the conditional probability. Given n, we find some large s so that $\begin{matrix} λ (W | D) - λ (W_{s} | D) < 2^{- n} (1 - λ (W | D)) . \end{matrix}$ We also assume that s is greater than the granularity of D. We claim that $T_{D} (n) \subseteq s$ . Suppose that $k ⩾ s$ . Then $B_{n, k}$ and $W_{s} \cap D$ are independent, and also $B_{n, k}$ and D are independent; this implies that $B_{n, k}$ and $W_{s}$ are independent modulo D, that is, $\begin{matrix} λ (W_{s} \cap B_{n, k} | D) = λ (W_{s} | D) \cdot λ (B_{n, k} | D) = 2^{- n} λ (W_{s} | D) . \end{matrix}$ Then $\begin{array}{l} λ (W_{s} \cup B_{n, k} | D) & = λ (W_{s} | D) + λ (B_{n, k} | D) - λ (W_{s} | D) \cdot λ (B_{n, k} | D) \\ > λ (W | D) - 2^{- n} (1 - λ (W | D)) + 2^{- n} - 2^{- n} λ (W | D) ⩾ λ (W | D), \end{array}$ so it is impossible that $B_{n, k} \cap D \subseteq W$ . Hence $k \notin T_{D} (n)$ .

Finally, we need to show that if $⋂ U_{n} \subseteq ⋂ V_{n}$ then T traces f (where f is mapped to $⟨ U_{n} ⟩$ and $⟨ V_{n} ⟩$ is mapped to T). We show that there is some D such that $T_{D}$ traces f.

We seek some clopen D such that $D ⊈ W$ but for all but finitely many m, $D \cap B_{m, f (m)} \subseteq W$ ; that is, $D \cap U_{n} \subseteq W$ for some n. If there is no such D then we build some $x \in (⋂_{n} U_{n}) ∖ W$ (but $⋂_{n} U_{n} \subseteq ⋂_{n} V_{n} \subseteq V_{2} \subseteq W$ ). This is done by initial segments; given $σ_{n}$ such that $[σ_{n}] ⊈ W$ , by assumption, $U_{n} \cap [σ_{n}] ⊈ W$ , so we can find an extension $σ_{n + 1} ≽ σ_{n}$ such that $[σ_{n + 1}] \subseteq U_{n}$ but $[σ_{n + 1}] ⊈ W$ .8

⁸

A quicker way to state this last argument is the following: the space $W^{∁} = 2^{ω} ∖ W$ is a Baire space. Restricted to this space, $⋂ U_{n} = \emptyset$ ; so there is some n such that $U_{n} ∖ W$ is not dense in $W^{∁}$ . Thus there is some clopen D such that $D \cap W^{∁}$ is nonempty but disjoint from $U_{n}$ . The initial segment construction above reproves the Baire category theorem in the space $W^{∁}$ .

□

Corollary 3.15 (Bartoszynski [44]).

Let h be an order function.

$cof (N)$ is the smallest size of a family of h-traces that trace every function.

$add (N)$ is the smallest size of a family of functions in $ω^{ω}$ which are not all traced by a single h-trace.

Corollary 3.16 (Rupprecht [39,40]).

An oracle is (strongly) null engulfing if and only if it is high.

Corollary 3.17 (Terwijn and Zambella [43]).

An oracle is low for Schnorr tests if and only if it is computably traceable.

Kjos-Hanssen, Nies and Stephan [26] showed that lowness for Schnorr randomness is also equivalent to being computably traceable. The framework discussed here does not appear to give tools for proving this equivalence. This is in contrast with lowness for genericity or Kurtz randomness, which we will discuss below.

3.6. Reducing category to measure

We prove:

Theorem 3.18.
$Supset (M) \to Supset (N)$ .

We take a slightly roundabout way because below we will use the concepts that we introduce now. For a problem $A \subseteq A_{inst} \times A_{sol}$ , we define a problem $A^{ω}$ by letting ${(A^{ω})}_{inst} = {(A_{inst})}^{ω}$ , ${(A^{ω})}_{sol} = {(A_{sol})}^{ω}$ and $(a_{0}, a_{1}, a_{2}, \dots) A^{ω} (b_{0}, b_{1}, b_{2}, \dots)$ if and only if $a_{0} A b_{0}$ , $a_{1} A b_{1}, \dots$ . Note that we can think of $A_{inst}^{ω}$ and $A_{sol}^{ω}$ as subsets of $ω^{ω}$ by the natural computable isomorphism between $ω^{ω}$ and ${(ω^{ω})}^{ω}$ .

It would be tempting to think that $A \to B$ implies $A^{ω} \to B^{ω}$ ; apply the maps $ψ_{inst}$ and $ψ_{sol}$ coordinate-wise. The problem is that these maps may fail to be hyperarithmetic piecewise computable; if $ψ_{inst} ↾ A_{n}$ is computable for a partition $⟨ A_{n} ⟩$ , then ${(ψ_{inst})}^{ω}$ is continuous on the sets $\prod_{k} A_{n_{k}}$ , of which there are uncountably many. In the language of Remark 2.4, if we need α jumps to determine which computable map to apply to x, then $ψ^{ω} (x)$ will be $x^{(α)}$ -computable rather than x-computable.

However, if $ψ_{inst}$ and $ψ_{sol}$ are (total) computable functions, then this construction will work. In fact, slightly less is sufficient:
Lemma 3.19.
Suppose that ψ is a morphism from A to B, that the sets $A_{inst}$ and $B_{sol}$ are hyperarithmetic, and that $ψ_{inst} ↾ A_{inst}$ and $ψ_{sol} ↾ B_{sol}$ are computable (i.e., restrictions of partial computable functions). Then $A^{ω} \to B^{ω}$ .
Proof.
${(A_{inst})}^{ω}$ and ${(B_{sol})}^{ω}$ are hyperarithmetic, and the maps ${(ψ_{inst})}^{ω} ↾ {(A_{inst})}^{ω}$ and ${(ψ_{sol})}^{ω} ↾ {(B_{sol})}^{ω}$ are computable. Outside ${(A_{inst})}^{ω}$ and ${(B_{sol})}^{ω}$ , we can use any constant computable function. □
Lemma 3.20.
For all order functions h and $\tilde{h}$ , ${(h - Trace)}^{ω} \leftrightarrow {(\tilde{h} - Trace)}^{ω}$ .
Proof.
The maps in the morphism from $h - Trace$ to $\tilde{h} - Trace$ are computable. □

We therefore write ${Trace}^{ω}$ . However,
Lemma 3.21.
$Trace \leftrightarrow {Trace}^{ω}$ .
Proof.
For every problem A, $A \to A^{ω}$ : map $a \in A_{inst}$ to $(a, a, a \dots)$ ; on the solution side map $(b_{0}, b_{1}, \dots)$ to $b_{0}$ .

Let $h (n, k) = max {n, k}$ . For this proof we choose a computable pairing function $(x, y) \mapsto ⟨ x, y ⟩$ which makes h non-decreasing (the value of the pair $⟨ n, k ⟩$ is its location in a computable ordering of pairs which firsts orders by the maximum).

We reduce ${(id - Trace)}^{ω}$ to $h - Trace$ . On the instance side, map $⟨ f_{k} ⟩$ to the function f defined by $f (k, n) = f_{k} (n)$ . On the solution side, we map the h-trace T to the sequence of id-traces $(T_{0}, T_{1}, \dots)$ , with $T_{k} (n) = \emptyset$ for $n < k$ , and $T_{k} (n) = T (k, n)$ for $n ⩾ k$ . □

Let $C N D$ denote the collection of closed, nowhere dense subsets of Cantor space, each named by a nowhere dense binary tree. $Supset (C N D, M)$ is the problem of finding a meagre superset of a given closed, nowhere dense set.
Proposition 3.22.
$Supset (C N D, M) \to Trace$ .

To prove Proposition 3.22 we need the following. Call a collection $O$ of clopen subsets of Cantor space dense if for every dense open set $U \subseteq 2^{ω}$ there is some $C \in O$ such that $C \subseteq U$ .
Lemma 3.23.
There are uniformly computable dense families of clopen sets $O_{n}$ such that for all n, the intersection of any n sets in $O_{n}$ is nonempty.
Proof.
For every pair $n < m < ω$ , let $A_{n, m}$ be the collection of functions g whose domain is $2^{n}$ , the set of binary strings of length n, such that for all $σ \in 2^{n}$ , $g (σ)$ is a binary string of length m extending σ. Each such g represents a step toward defining a dense open set, by mapping strings of length n to extensions in the dense set we are building. Thus, for such g we let $C_{g} = ⋃ {[τ] : τ \in range g}$ . An open set $U \subseteq 2^{ω}$ is dense if and only if for every n there is some $m > n$ and some $g \in A_{n, m}$ such that $C_{g} \subseteq U$ .

We let $O_{n}$ be the collection of unions $C_{g_{1}} \cup C_{g_{2}} \cup \dots \cup C_{g_{n}}$ , where for some $0 = k_{0} < k_{1} < k_{2} < \dots < k_{n}$ we have $g_{i} \in A_{k_{i - 1}, k_{i}}$ . That is: the elements of $O_{n}$ are obtained by choosing a string $[σ]$ of some length $k_{1}$ , and enumerating it into the clopen set being build; then for each string of length $k_{1}$ , we choose some extension of length $k_{2}$ , and enumerating all such extensions; and so on, n times.

Suppose that $U \subseteq 2^{ω}$ is dense and open. As described, for all n there is some $m > n$ and some $g \in A_{m, n}$ such that $C_{g} \subseteq U$ . Thus, we can define by induction a sequence $k_{1} < k_{2} < \dots < k_{n}$ and find $g_{i} \in A_{k_{i - 1}, k_{i}}$ such that $C_{g_{i}} \subseteq U$ . Thus, each $O$ is a dense collection of clopen sets.

Let $n < ω$ and let $D_{1}, D_{2}, \dots, D_{n}$ be elements of $O_{n}$ . For each $i ⩽ n$ there are $k_{1}^{i} < k_{2}^{i} < \dots < k_{n}^{i}$ and $g_{j}^{i} \in A_{k_{j - 1}^{i}, k_{j}^{i}}$ such that $D_{i} = ⋃_{j ⩽ n} C_{g_{j}^{i}}$ . We order these sets so that $k_{1}^{1} ⩽ k_{1}^{i}$ for all $i ⩾ 1$ ; then $k_{2}^{2} ⩽ k_{2}^{i}$ for all $i ⩾ 2$ , and so on. Then $⋂_{i} C_{g_{i}^{i}} \subseteq ⋂_{i} D_{i}$ and is nonempty: we define $σ_{i} \in range g_{i}^{i}$ recursively, with $σ_{1} ≺ σ_{2} ≺ \dots ≺ σ_{n}$ , as $k_{i - 1}^{i - 1} ⩽ k_{i - 1}^{i}$ . □
Proof of Proposition 3.22.
$Supset (C N D, M)$ is of course the same as the problem of finding a dense $Π_{2}^{0}$ subset of a given dense open set; for this reduction it is easier to think about dense sets. Fix families $O_{n}$ given by Lemma 3.23. We order all finite binary strings in a computable list $⟨ σ_{n} ⟩$ . We reduce $Supset (C N D, M)$ to $id - Trace$ .

On the instance side, we map a dense open set U to the function f defined as follows: $f (n)$ is some element C of $O_{n}$ such that $σ_{n} \hat{} C = {σ_{n} \hat{} x : x \in C}$ is a subset of U. Such a clopen set exists because U is dense in $[σ_{n}]$ .

On the solution side, let T be an id-bounded trace. We may assume that for all n, $T (n) \subseteq O_{n}$ . We map T to $⋂_{k} V_{k}$ , where for $k < ω$ , $V_{k}$ is the dense open set $⋃_{m > k} σ_{m} \hat{} ⋂ T (m)$ . Since $| T (m) | ⩽ m$ , $⋂ T (m)$ is nonempty, and so $V_{n}$ is dense open. If $g (m) \in T (m)$ for all $m > k$ , then $V_{k} \subseteq U$ , and so $⋂_{k} V_{k} \subseteq U$ . □

The maps given in the proof above are computable on their arithmetic domains, and so by Lemma 3.19, ${(Supset (C N D, M))}^{ω} \to {(Trace)}^{ω}$ .
Proof of Theorem 3.18.
By Theorem 3.14 and Lemma 3.21, and the morphism ${(Supset (C N D, M))}^{ω} \to {(Trace)}^{ω}$ , it suffices to show that $Supset (M)$ reduces to ${(Supset (C N D, M))}^{ω}$ . But this is not difficult: on the instance side, a meagre set is given by a sequence $⟨ T_{n} ⟩$ of nowhere dense sets, so we essentially take the identity map; on the solution side, we are given a sequence $⟨ M_{n} ⟩$ of meagre sets; we can combine their presentations and map this sequence to $⋃_{n} M_{n}$ . □
Corollary 3.24 (Bartoszynski [44]; Raisonnier, Stern [38]).

$cof (M) ⩽ cof (N)$ and $add (N) ⩽ add (M)$ .

Corollary 3.25.
Every computably traceable degree is low for meagre sets.
Proof.
By Corollary 3.16; Theorem 3.18 implies that every degree which is low for Schnorr tests is also low for meagre sets. □

For highness classes, the implication $Supset (M) \to Supset (N)$ does not add computable information, as $\begin{matrix} Dom \to Supset (M) \to Supset (N) \end{matrix}$ and we have already ascertained that $H (Supset (N)) = H (Dom)$ , as the former is $H (Trace)$ .
3.7. The Cichoń diagram

The following diagram (Fig. 2) displays all the morphisms for the problems associated with measure and category, as well as the domination problems. The analogous diagram for cardinal characteristics was named (by Fremlin) after Cichoń.

Figure 2.

The Cichoń diagram for Weihrauch problems.

4. IOE reals and sequential composition

4.1. Sequential composition

A (total) function $F : ω^{ω} \to ω^{ω}$ is Borel piecewise continuous if there is a countable partition $⟨ A_{n} ⟩$ of $ω^{ω}$ into Borel sets such that for all n, $F ↾ A_{n}$ is continuous. We let $F$ be the collection of these functions.

A name for such a function is an element of Baire space coding:

The sets $A_{n}$ : for each n, some oracle $z_{n}$ and a $Δ_{1}^{1} (z_{n})$ -definition of $A_{n}$ ;

The functions $F ↾ A_{n}$ : a name for a partial continuous function $ψ_{n}$ which agrees with F on $A_{n}$ .

Note that the collection of names is quite complicated (d- $Π_{1}^{1}$ ). For $x \in 2^{ω}$ , a Borel piecewise continuous function is x-computable if it has an x-computable name. If $F \in F$ is x-computable then for all $a \in ω^{ω}$ , $F (a) ⩽_{T} (x, a)$ . The naming system is chosen so that the Borel piecewise continuous maps with computable names are precisely the hyperarithmetic piecewise computable ones.

Lemma 4.1.
$F$ has effective composition: there is a computable map $θ : {(ω^{ω})}^{2} \to ω^{ω}$ such that if f, g are names for $F, G \in F$ then $θ (f, g)$ is a name for $F \circ G$ .
Proof.
Let $⟨ A_{n} ⟩$ , $⟨ B_{n} ⟩$ be the partitions. We let $C_{n, m} = A_{n} \cap F^{- 1} [B_{m}] = {(F ↾ A_{n})}^{- 1} [B_{m}]$ ; otherwise, we compose partial continuous functions. □

Every constant function is in $F$ ; the constant function $y \mapsto a$ has an a-computable name.

For problems A and B we define the problem $A ⋆ B$ . The instances are pairs $(a, F) \in A_{inst} \times F$ (as usual we mean a name for $F \in F$ ) such that $F [A_{sol}] \subseteq B_{inst}$ ; the solutions are pairs in $A_{sol} \times B_{sol}$ . The relation is: $(c, d)$ is an $(A ⋆ B)$ -solution of $(a, F)$ if c is an A-solution for a and d is a B-solution for $F (c)$ . The idea is to take a two-step iteration: first solve an A-instance a; use the solution to generate a new B-instance, and then solve that one.9
⁹
Blass [5] defines $A ⋆ B$ using the collection of all functions from $A_{sol}$ to $B_{inst}$ . As this collection cannot be represented, Rupprecht did not try to find a computable analogue. A similar yet non-identical sequential composition was discovered by Brattka et al. [7], who only used computable maps. Our formulation, and choice of functions for morphisms, are designed to obtain Lemma 4.3.

The collection of instances of $A ⋆ B$ can be quite complicated. However it does contain computable points: use a constant function that maps to a computable instance of B.

We now verify that sequential operation induces a well-defined operation on the morphism equivalence classes of Weihrauch problems.
Lemma 4.2.
$A, B \to A ⋆ B$
Proof.
To reduce A to $A ⋆ B$ we use the idea just mentioned: fix a computable $b_{} \in B_{inst}$ ; let $F_{b }$ be the constant function $y \mapsto b_{}$ . We map an A-instance a to $(a, F_{b })$ and map an $(A ⋆ B)$ -solution $(c, d)$ to c.

To reduce B to $A ⋆ B$ , fix a computable A-instance $a_{}$ . We map a B-instance b to the pair $(a_{}, F_{b})$ (where again $F_{b}$ is the constant function $y \mapsto b$ ); we map an $(A ⋆ B)$ -solution $(c, d)$ to d. □
Lemma 4.3.
If $A \to \hat{A}$ and $B \to \hat{B}$ then $(A ⋆ B) \to (\hat{A} ⋆ \hat{B})$ .
Proof.
Let ψ be a morphism from A to $\hat{A}$ and let φ be a morphism from B to $\hat{B}$ . Let $(a, F)$ be an $(A ⋆ B)$ -instance. Let $\hat{a} = ψ_{inst} (a)$ and let $\hat{F}$ be the translation of F under the relevant morphisms: $\hat{F} = φ_{inst} \circ F \circ ψ_{sol}$ (see Figure 3). As $F : A_{sol} \to B_{inst}$ , it follows that $\hat{F} : {\hat{A}}_{sol} \to {\hat{B}}_{inst}$ . We send $(a, F)$ to $(\hat{a}, \hat{F})$ , using Lemma 4.1 to see that this map is hyperarithmetic piecewise computable. Let $(\hat{c}, \hat{d})$ be an $\hat{A} ⋆ \hat{B}$ -solution. We map it to $(c, d) = (ψ_{sol} (\hat{c}), φ_{sol} (\hat{d}))$ . □

Figure 3.
Reducing $A ⋆ B$ to $\hat{A} ⋆ \hat{B}$ .
Lemma 4.4.
$(A ⋆ B) ⋆ C \leftrightarrow A ⋆ (B ⋆ C)$ .
Proof.
This goes as expected. Abusing notation, we write $X^{Y}$ for the collection of maps from Y to X that are in $F$ . So ${(A ⋆ B)}_{inst} = A_{inst} \times {(B_{inst})}^{A_{sol}}$ . The proof of the lemma relies on the natural identification of $\begin{matrix} {((A ⋆ B) ⋆ C)}_{inst} = A_{inst} \times {(B_{inst})}^{A_{sol}} \times {(C_{inst})}^{A_{sol} \times B_{sol}} \end{matrix}$ with $\begin{matrix} {(A ⋆ (B ⋆ C))}_{inst} = A_{inst} \times {(B_{inst} \times {(C_{inst})}^{B_{sol}})}^{A_{sol}} . \end{matrix}$ □

When describing a map $φ_{inst} : C_{inst} \to {(A ⋆ B)}_{inst}$ , we must send $c \in C_{inst}$ to some $(a, F) \in {(A ⋆ B)}_{inst}$ , where a Borel piecewise continuous name for F is obtained in some hyperarithmetic piecewise computable fashion from a. Our description of F can thus make use of a. If the Weihrauch problem A is hyperarithmetic, that is, if ${y \in A_{sol} : x A y}$ is uniformly hyperarithmetic in x, then it suffices to describe $F (y)$ under the assumption that $a A y$ ; we can then define F to some computable value for all other y while still obtaining an a-computable Borel piecewise continuous name.
Proposition 4.5.

If $Card (A)$ and $Card (B)$ are infinite, then $Card (A ⋆ B) = max {Card (A), Card (B)}$ .

$NL (A ⋆ B) = NL (A) \cup NL (B)$ .

Proof.
(a): Let Z be a complete solution set for A and W be a complete solution set for B. Then $Z \times W$ is a complete solution set for $A ⋆ B$ . On the other hand, since $A, B \to A ⋆ B$ , $max {Card (A), Card (B)} ⩽ Card (A ⋆ B)$ .

(b): Again by Lemma 4.2, $NL (A), NL (B) \subseteq NL (A ⋆ B)$ . Suppose that $x \in NL (A ⋆ B)$ . Let $(a, F)$ be an x-computable $(A ⋆ B)$ -problem with no computable solution. If a has no computable A-solution then we are done. Otherwise let c be a computable A-solution for a. Let $b = F (c)$ . Since F is x-computable, so is b. And it has no computable B-solution. □
Proposition 4.6.
$Card ({(A ⋆ B)}^{⊥}) = min {Card (A^{⊥}), Card (B^{⊥})}$ .
Proof.
We know that ${(A ⋆ B)}^{⊥} \to A^{⊥}, B^{⊥}$ . So it remains to show that $\begin{matrix} Card ({(A ⋆ B)}^{⊥}) ⩾ min {Card (A^{⊥}), Card (B^{⊥})} . \end{matrix}$ Let R be a complete set of solutions for ${(A ⋆ B)}^{⊥}$ of size $Card ({(A ⋆ B)}^{⊥})$ . Let $P = π_{0} [R] = {c : (\exists G) (c, G) \in R}$ . Then $| P | ⩽ | R |$ . If P is a complete solution set for $A^{⊥}$ then $Card (A^{⊥}) ⩽ Card ({(A ⋆ B)}^{⊥})$ . Suppose not. Then there is some $a^{} \in A_{sol}$ such that for all $c \in P$ , $c A a^{}$ . We let $Q = {G (a^{}) : (\exists c) (c, G) \in R}$ . Then $| Q | ⩽ | R |$ . We claim that Q is a complete solution set for $B^{⊥}$ , so $Card (B^{⊥}) ⩽ Card ({(A ⋆ B)}^{⊥})$ . For suppose that $b \in B_{sol}$ . Then $(a^{}, b)$ is an instance of ${(A ⋆ B)}^{⊥}$ , so there is some $(c, G) \in R$ which solves it. This means that either $c / A a^{}$ , or that $G (a^{}) / B b$ , that is, $b B^{⊥} G (a^{})$ . The former is not true, so $G (a^{}) \in Q$ is a $B^{⊥}$ -solution of b. □

For the following lemma, we generalise notation: for $x \in 2^{ω}$ and a problem A, $H^{x} (A)$ is the set of $y \in 2^{ω}$ which compute $c \in A_{sol}$ which solves every x-computable A-instance.
Lemma 4.7.
$y \in H (A ⋆ B)$ if and only if $y \in H^{x} (B)$ for some $x \in H (A)$ such that $x ⩽_{T} y$ .
Proof.
The point is that for all $z, w \in ω^{ω}$ , $z ⩽_{T} w$ if and only if there is some computable $F \in F$ such that $F (w) = z$ . This is because every partial computable function can be extended to a computable $F \in F$ . □
4.2. A weakening of morphism reduction

For a Weihrauch problem A and $n < ω$ , let $\begin{matrix} A^{⋆ n} = \underset{n times}{\underset{︸}{A ⋆ A ⋆ \dots ⋆ A}} \end{matrix}$ (we implicitly use the associativity of sequential composition, Lemma 4.4). For Weihrauch problems A and B we write $\begin{matrix} A ⇢ B \end{matrix}$ if $A \to B^{⋆ n}$ for some $n < ω$ . We also write if $A ⇢ B$ and $B ⇢ A$ . Lemma 4.2 and Propositions 4.5 and 4.6 imply:

Lemma 4.8.

⇢ is transitive, andis an equivalence relation.

If $A ⇢ B$ then $Card (A) ⩽ Card (B)$ and $Card (A^{⊥}) ⩾ Card (B^{⊥})$ .

If $A ⇢ B$ then $NL (A) \subseteq NL (B)$ .

4.3. An example: $Supset (M)$

Proposition 4.9.
$Supset (M) \to Pass (M) ⋆ Dom$ .
Proof.
The first step is to replace $Pass (M)$ with a fractal version: $FractalPass (M)$ is the problem of finding, given a meagre set A, a point $z \in ω^{ω}$ such that for all $w =^{} z$ , $w \notin A$ . Clearly $Pass (M) \to FractalPass (M)$ . To show the reverse morphism, we map the meagre set A (an instance of $FractalPass (M)$ ) to $⋃_{σ \in ω^{< ω}} (σ^{↷} A)$ . Here, for $x \in ω^{ω}$ , $σ^{↷} x$ is the result of replacing the first $| σ |$ values of x by σ, and $σ^{↷} X = {σ^{↷} x : x \in X}$ . On the solution side, we map a real to itself.

Now we show $Supset (M) \to FractalPass (M) ⋆ Dom$ . On the instance side, we map $A = ⋃_{n} [T_{n}]$ to the pair $(A, F)$ , where $F (z)$ is defined as follows. Suppose that $w \notin A$ for all $w =^{} z$ . Then $F (z)$ is the function f mapping $(τ, n)$ to $k ⩾ | τ |$ such that $(τ^{↷} z) ↾ k \notin T_{m}$ for all $m ⩽ n$ .

On the solution side, we map $(z, g)$ to the meagre set $⋃ B_{n}$ , where for each τ, $[(τ^{↷} z) ↾ g (τ, n)]$ is thrown out of $B_{n}$ . If $g (-, n)$ majorises $f (-, n)$ then $[T_{m}] \subseteq B_{n}$ for all $m ⩽ n$ . □

We already know that $Pass (M), Dom \to Supset (M)$ . It follows that $\begin{matrix} Pass (M) ⋆ Dom \to Supset (M) ⋆ Supset (M), \end{matrix}$ whence $Pass (M) ⋆ Dom ⇢ Supset (M)$ , which with Proposition 4.9 gives As a result:
Corollary 4.10.

$cof (M) = max {d, non (M)}$ (A. Miller and Truss);

$add (M) = min {b, cov (M)}$ (Fremlin);

A degree is not low for meagre sets if and only if it is either hyperimmune or weakly meagre engulfing.

Examining the morphisms, we also get that if a degree d is high relative to a weakly 1-generic below it then it is strongly meagre engulfing. However we already know that highness suffices, indeed is equivalent.
4.4. Infinitely often equal reals

$AEDiff$ is the problem of finding a function g which is different from a given f on all but finitely many inputs. Its dual is $IOE$ , the problem of finding a function f which agrees with a given g on infinitely many inputs.

$H (IOE) = NL (AEDiff)$ is the class of degrees computing functions f, which agree with every computable function on infinitely many inputs. Similarly, the dual class $NL (IOE) = H (AEDiff)$ is that of degrees computing functions which are different from every computable function on all but finitely many inputs.

Kjos-Hanssen, Merkle and Stephan [25] showed:

Proposition 4.11.
$NL (IOE)$ is the class of degrees which are either high or DNR.

We consider other known morphisms and equivalences.
Proposition 4.12.
$IOE \to Pass (M)$ .
Proof.
We prove the equivalent $Capture (M) \to AEDiff$ . On the instance side, we start with a point $f \in ω^{ω}$ ; we map it to itself. On the solution side, we map $g \in ω^{ω}$ to the meagre set of $h \in ω^{ω}$ which are almost always different from g. □
Proposition 4.13.
$AEDiff \to Dom$ .
Proof.
If $f ⩽^{} g$ then $g + 1$ is almost always different from f. □

Note how the morphism from $Capture (M)$ to $Dom$ (Proposition 3.3) is close to the composition of the morphisms from $Capture (M)$ to $AEDiff$ and $AEDiff$ to $Dom$ given by Propositions 4.12 and 4.13.
Proposition 4.14.
$Pass (M) \to IOE ⋆ IOE$ .
Proof.
We prove that $Pass (M) \to Esc ⋆ IOE$ ; since $Esc \to IOE$ (the dual of Proposition 4.13), Lemma 4.3 says that $Esc ⋆ IOE \to IOE ⋆ IOE$ .

We work in Cantor space. On the instance side, we are given a meagre set A with name $⟨ T_{n} ⟩$ . As usual we may assume that $T_{n} \subseteq T_{n + 1}$ . In this proof, a partial string* is a finite function to ${0, 1}$ . We say that a partial string τ witnesses the meagreness of A if the domain of τ is an interval $[n, m)$ and for every $σ \in 2^{< ω}$ of length n, $σ \cup τ \notin T_{n}$ . Effectively from $⟨ T_{n} ⟩$ we obtain a function $h : ω \to ω$ such that for all n, there is some partial string $τ : [n, h (n)) \to {0, 1}$ which witnesses the meagreness of A. Note that if $x \in 2^{ω}$ and for infinitely many n there is some $m ⩾ n$ such that $x ↾ [n, m)$ witnesses the meagreness of A, then $x \notin A$ .

Given a function $g \in ω^{ω}$ , consider the sequence of intervals $⟨ I_{n} ⟩$ given by $I_{n} = [g^{(n)} (0), g^{(n + 2)} (0))$ ; note that this is not a partition of ω: these intervals overlap. If g escapes h then there are infinitely many n for which there are partial strings τ such that $dom τ \subseteq I_{n}$ and τ witnesses the meagreness of A.

Let $σ, τ$ be two partial strings. We say that σ and τ are strongly compatible (relative to g) if for some n and m, $dom σ \subseteq I_{n}$ , $dom τ \subseteq I_{m}$ and the intervals $I_{n}$ and $I_{m}$ are disjoint. We now define $F (g)$ : assuming g escapes h, $F (g)$ is a function f such that for all k, $f (k)$ is a set of $3 k + 1$ many finite functions τ, pairwise strongly compatible (relative to g), each of which witnesses the meagreness of A, such that $min dom τ ⩾ k$ . On the instance side, we map A to the pair $(h, F)$ .

On the solution side, we are given a pair $(g, p)$ of functions. Given g we can compute $⟨ I_{n} ⟩$ , and so the notion of strong compatibility of partial strings relative to g.10
¹⁰
Of course, in the absence of A, we do not know which partial strings witness the meagreness of A.

We define a sequence $⟨ σ_{k} ⟩$ of pairwise strongly compatible partial strings. Given $σ_{0}, \dots, σ_{k + 1}$ , we examine $p (k)$ . We may assume that this is a set of $3 k + 1$ many pairwise strongly compatible partial strings τ such that $min dom τ ⩾ k$ (if not, we pick $σ_{k}$ to be empty). One of these partial strings is strongly compatible with each $σ_{i}$ for $i < k$ , and so can be chosen as $σ_{k}$ . We then map the pair $(g, p)$ to $x \in 2^{ω}$ defined by extending $⋃_{k} σ_{k}$ ; we fill the undetermined locations arbitrarily. The condition $min dom σ_{k} ⩾ k$ implies that x can be computed from $(g, p)$ , uniformly.

If indeed A is mapped to $(f, H)$ and $(g, p)$ solves $(f, H)$ , then g escapes f and for infinitely many k, $p (k) = F (g) (k)$ , in which case $σ_{k}$ witnesses the meagreness of A. It then follows that $x \notin A$ , as required. □

Propositions 4.12 and 4.14 give: which yields some characterisations of cardinals and non-lowness classes, due to Rupprecht [39] and Bartoszynski [45].
Corollary 4.15.

A degree is weakly meagre engulfing if and only if it is high or DNR.

A degree is not low for meagre sets if and only if it is hyperimmune or DNR.

$Card (IOE) = non (M)$ and $Card (AEDiff) = cov (M)$ .

Proof.
(a) follows from $NL (IOE) = NL (Pass (M))$ , and Proposition 4.11.

(b) follows from (a) and Corollary 4.10(b). □

As for $NL (AEDiff)$ , the string of morphisms $\begin{matrix} Capture (M) \to AEDiff \to Dom \end{matrix}$ and the equivalence of hyperimmune with computing a weakly 1-generic sandwich the class in the middle, yielding $NL (AEDiff)$ being hyperimmune as well.
4.5. Lowness for closed nowhere dense sets, and weak 1-genericity

Corollary 4.15(b) is very close to a result of Stephan and Yu’s [42]. Rather than lowness for meagre sets, they consider the related notion of lowness for closed nowhere dense sets. That is, $NL (Supset (C N D))$ rather than $NL (Supset (M))$ . They show that this class is also equivalent to being hyperimmune or DNR; that is, $NL (Supset (C N D)) = NL (Supset (M))$ . They further show that this class coincides with non-lowness for weak 1-genericity, a property which doesn’t seem to be expressed as the highness class of a Weihrauch problem.

We note that we cannot get a morphism equivalence between $Supset (M)$ and $Supset (C N D)$ ; the corresponding non-lowness classes coincide, but their highness classes do not: indeed, $H (Supset (C N D))$ is empty, as the union of all computable closed, nowhere dense sets is dense. Nonetheless, we have the means to deduce the Stephan-Yu results. We now work in Cantor space, though the results can be extended to Baire space as well.

In one direction we do get a morphism:

Proposition 4.16.
$Supset (M) \to Supset (C N D)$ .
Proof.
Recall the problems $A^{ω}$ mentioned above. First, we show that $Supset (M) \to {(Supset (C N D))}^{ω}$ . This is not hard: on both sides, map a sequence $⟨ T_{n} ⟩$ to itself; we just consider them differently, as a name for a meagre set or an ω-sequence of names for closed, nowhere dense sets. If $⟨ S_{n} ⟩$ is a ${(Supset (C N D))}^{ω}$ -solution for $⟨ T_{n} ⟩$ , that is, if $[T_{n}] \subseteq [S_{n}]$ for all n, then certainly $⋃_{n} [T_{n}] \subseteq ⋃_{n} [S_{n}]$ .

Next, we show that $Supset (C N D) \leftrightarrow {(Supset (C N D))}^{ω}$ . As observed above, we always have $A \mapsto A^{ω}$ . We reduce ${(Supset (C N D))}^{ω}$ to $Supset (C N D)$ . On the instance side, map $⟨ T_{n} ⟩$ to the tree $S = ⋃_{n} ({0^{n}} \cup 0^{n} 1 \hat{} T_{n})$ . That is, paste $T_{n}$ on the $n^{th}$ level of a fishbone. On the solution side undo this operation. □

We now obtain:
Proposition 4.17.
$NL (Supset (M)) = NL (Supset (C N D))$ .
Proof.
Proposition 4.16 shows that $NL (Supset (M)) \subseteq NL (Supset (C N D))$ . In the other direction, the proof of Proposition 4.9 shows that $Supset (C N D) \to Pass (M) ⋆ Maj$ , where $Maj$ is the problem of finding a function g that majorises a given function f, that is, $(\forall n) f (n) ⩽ g (n)$ . While $H (Maj)$ is empty, $NL (Maj) = NL (Dom)$ is the collection of hyperimmune degrees. It follows that $\begin{matrix} NL (Supset (C N D)) \subseteq NL (Pass (M)) \cup NL (Maj) = NL (Supset (M)) . \end{matrix}$ □

What about lowness for weak genericity? Here we can use a technique utilised by Greenberg and Monin [20]. We dualise and define the Weihrauch problem:

$FractalSpill (C N D)$ : an instance is a closed, nowhere dense set P; a solution is a closed, nonempty, nowhere dense set Q and an infinite set $I \subseteq ω$ such that $0 \in I$ and for all $n \in I$ , for all $σ \in 2^{< ω}$ of length n such that $[σ] \cap Q \neq \emptyset$ , $Q \cap [σ] ⊈ σ \hat{} P$ . (Recall that $σ \hat{} P = {σ \hat{} x : x \in P}$ .)
Lemma 4.18.
$Spill (C N D) \leftrightarrow FractalSpill (C N D)$ .
Proof.
$Spill (C N D) \to FractalSpill (C N D)$ is immediate, via identity maps, forgetting the set I. For the other direction, we use the construction from [20]. On the instance side we use the identity map. On the solution side, given a nowhere dense tree T, we define a nowhere dense tree S and an infinite set I. We start with $0 \in I$ and $⟨ ⟩ \in S$ . Suppose that we have declared that $n \in I$ and for every string ρ of length at most n, whether $ρ \in S$ or not. For each string $σ \in S$ of length n, the tree $⋃_{k ⩽ | σ |} (σ ↾ k) \hat{} T$ is nowhere dense, so we can find some $τ ≽ σ$ off that tree. We declare that $τ \notin S$ . We let the next element of I be bigger than all these τ’s.

By construction, for every string $σ \in S$ such that $| σ | \in I$ , $σ \hat{} T \subseteq S$ . Suppose that $| σ | \in I$ , $σ \in S$ and $[σ] \cap [S] \subseteq σ \hat{} P$ . Then $σ \hat{} [T] \subseteq σ \hat{} P$ , whence $[T] \subseteq P$ . □
Lemma 4.19.
Suppose that Γ is a countable collection of closed, nowhere dense sets, which is closed under the shift operator: for all σ and $P \in Γ$ , $P - σ = {x : σ \hat{} x \in P}$ is also in Γ. Suppose that $(Q, I)$ is a $FractalSpill (C N D)$ -solution for every $P \in Γ$ . Then $Q ⊈ ⋃ Γ$ . Thus, an oracle computing such Q is not low for Γ-genericity.
Proof.
The cloure property of Γ means that for every $P \in Γ$ and every σ such that $| σ | \in I$ and $[σ] \cap Q \neq \emptyset$ , $[σ] \cap Q ⊈ P$ . This is because $P - σ \in Γ$ and $[σ] \cap Q ⊈ σ \hat{} (P - σ) = P \cap [σ]$ .

We can therefore build a point in $Q ∖ ⋃ Γ$ by finite extension. At stage k we have a string $σ_{k}$ such that $[σ_{k}] \cap Q \neq \emptyset$ and $| σ_{k} | \in I$ . Let $P_{k}$ be the $k^{th}$ element of Γ in some ω-enumeration of Γ. Since $[σ_{k}] \cap Q ⊈ P_{k}$ , we can find an extension $σ_{k + 1}$ of $σ_{k}$ such that $[σ_{k + 1}] \cap Q \neq \emptyset$ , $| σ_{k + 1} | \in I$ and $[σ_{k + 1}] \cap P_{k} = \emptyset$ . □

We now get the full result of Stephan and Yu, which is also another proof of Proposition 4.17. Corollary 4.20.
$\begin{matrix} NL (Supset (M)) = NL (Supset (C N D)) = {x : x is not low for weak 1-genericity} . \end{matrix}$
Proof.
By Proposition 4.16, $NL (Supset (M)) \subseteq NL (Supset (C N D))$ . By Lemma 4.18 and Lemma 4.19, applied to $Γ = Δ_{1}^{0} \cap C N D$ , we see that every oracle in $NL (Supset (C N D))$ is not low for weak 1-genericity. Finally, suppose that x is not low for weak 1-genericity; say g is weakly 1-generic, $M \in M$ is x-computable and $g \in M$ ; then M shows that $x \in NL (Supset (M))$ . □

4.6. A non-morphism

The implications $\begin{matrix} Supset (M) \to Pass (M) ⋆ Dom \end{matrix}$ and $\begin{matrix} IOE \to Pass (M) \to IOE ⋆ IOE \end{matrix}$ leave the question open whether we can get morphism reverals, that is, if we really needed the weakening of morphism equivalence. For computable morphisms, we can use highness classes.

Lemma 4.21.
$Pass (M) ⋆ Dom ↛ Supset (M)$ .
Proof.
There is a high degree which is not high relative to a weakly 1-generic below it, e.g. a minimal high degree. □
Lemma 4.22.
$IOE ⋆ IOE ↛ IOE$ .
Proof.
We show that $H (IOE) \neq H (IOE ⋆ IOE)$ . By Lemma 4.7, $y \in H (IOE ⋆ IOE)$ if and only if there is some $x ⩽_{T} y$ in $H (IOE)$ such that $y \in H^{x} (IOE)$ . We observed that $H (IOE) = NL (AEDiff)$ is the collection of oracles of hyperimmune degree. Relativising, $y \in H (IOE ⋆ IOE)$ if and only if y has hyperimmune degree relative to a hyperimmune $x ⩽_{T} y$ . We cannot have $x \equiv_{T} y$ , in particular, y cannot have minimal degree. On the other hand, there is a hyperimmune x of minimal degree. □

These fine distinctions do not help if we change the question to the existence of a definable (say, Borel) morphism. We shall get back to this question in Section 8.
5. Other reducibilities

We can modify the definition of the highness class (and thus the non-lowness class) associated with a Weihrauch problem. The most obvious one is changing the reducibility from Turing to weaker ones. If $⩽_{r}$ is any reducibility, implied by Turing, then for a Weihrauch problem A we define $H^{r} (A)$ to be the collection of oracles x such that there is some $c \in A_{sol}$ , $c ⩽_{r} x$ which is an A-solution for every $a \in A_{inst}$ such that $a ⩽_{r} \emptyset$ .

Morphisms give implications for these variants of highness and non-lowness classes.

Lemma 5.1.
Suppose that $⩽_{r}$ is a transitive relation implied by Turing reducibility. Let A and B be Weihrauch problems. Then:
If $A \to B$ then ${NL}^{r} (A) \subseteq {NL}^{r} (B)$ .

${NL}^{r} (A ⋆ B) = {NL}^{r} (A) \cup {NL}^{r} (B)$ .
As a result, if $A ⇢ B$ then ${NL}^{r} (A) \subseteq {NL}^{r} (B)$ .

The most commonly used in this area is hyperarithmetic reducibility, equivalent to relatively $Δ_{1}^{1}$ reducibility. Thus ${NL}^{Δ_{1}^{1}} (A)$ is the collection of $x \in 2^{ω}$ such that there is some $c \in A_{inst} \cap Δ_{1}^{1} (x)$ which has no $Δ_{1}^{1}$ A-solution. The relationships between problems studied above give analogous results in this context:
Theorem 5.2 (Chong, Nies, Yu [10]).

An oracle is low for $Δ_{1}^{1}$ null sets if and only if it is $Δ_{1}^{1}$ -traceable.

Theorem 5.3 (Greenberg, Monin [20]).

An oracle x is low for $Δ_{1}^{1}$ genericity if and only if it is low for $Δ_{1}^{1}$ closed nowhere dense sets if and only if it is $Δ_{1}^{1}$ -dominated and every $f \in Δ_{1}^{1} (x)$ is infinitely often equal to some $Δ_{1}^{1}$ function.

We also obtain results that we believe have not been stated yet, for example:

Proposition 5.4.
There is a meagre set in $Δ_{1}^{1} (x)$ containing all $Δ_{1}^{1}$ points if and only if there is a function $f \in Δ_{1}^{1} (x)$ which is eventually different from every $Δ_{1}^{1}$ function.

In Section 8 below we discuss another family of weak reducibilities $⩽_{r}$ , namely Turing modulo an ideal.
5.1. Total reductions

In the other direction, we can ask what happens when we strengthen, rather than weaken, Turing reducibility. This has been investigated, for example, by Miyabe [23]. We make the following definition.

Definition 5.5.
Let $X \subseteq ω^{ω}$ . We say that $a \in X$ is X- $t t$ reducible to $x \in 2^{ω}$ if there is a (total) computable function $I : 2^{ω} \to X$ such that $a = I (x)$ . We write $a ⩽_{X - tt} x$ .

Let A be a Weihrauch problem. We let ${NL}^{tt} (A)$ be the collection of oracles $x \in 2^{ω}$ such that there is some $a ⩽_{A_{inst} - tt} x$ which has no computable A-solution.

Sometimes this notion trivialises, for example ${NL}^{tt} (Dom) = \emptyset$ . In other cases, we get something meaningful. Miyabe, in particular, examines what he calles uniform Schnorr randomness, where a uniform oracle test is an operator which gives a Schnorr test relative to every oracle. That is, a uniform Schnorr test relative to x is an element $N \in N$ which is $N - tt$ -reducible to x.

To use reducibilities in this context, we need to maintain totality.
Lemma 5.6.
Suppose that $A \to B$ by a morphism ψ such that $ψ_{inst} ↾ A_{inst}$ is computable. As usual, this means it is the restriction to $A_{inst}$ of a partial computable function. Then ${NL}^{tt} (A) \subseteq {NL}^{tt} (B)$ .

We observe that all the morphisms we have considered so far except for one (Remark 3.8) are uniform on their instances. We thus get:
Theorem 5.7 (Miyabe [23]).

An oracle x is low for uniform Schnorr tests if and only if for some (all) order function(s) h, every $f ⩽_{tt} x$ has a computable h-trace.

Unfortunately, the usefulness of this approach is limited, because it is not the case that ${NL}^{tt} (A ⋆ B) = {NL}^{tt} (A) \cup {NL}^{tt} (B)$ . For suppose that $(a, F) \in {(A ⋆ B)}_{inst}$ is $tt$ -reducible to x, and has no computable $A ⋆ B$ -solution. Suppose further that $x \notin {NL}^{tt} (A)$ ; so a has a computable A-solution c. It is not necessarily the case that $F (c)$ is $tt$ -reducible to x. That is, we have a total computable function $I : 2^{ω} \to F$ such that $F = I (x)$ . The function I gives us a name for F. But F itself is not continuous, only piecewise continuous, and the map taking $y \in 2^{ω}$ to $I (y) (c)$ is not necessarily computable. When reducing to $A ⋆ B$ , we often describe non-continuous functions F, as they assume that the input is in fact a solution for the computed A-instance.

It would be interesting to find an extension of our methods that would allow us to characterise classes such as ${NL}^{tt} (Pass (M))$ .

6. Addition, multiplication, and the Γ question

In this section we introduce another weakening of morphism reducibility (Definition 6.9) that still implies cardinal inequality and containment of highness classes (Lemma 6.10). This weakening is based on the dual operations of sum and product of Weihrauch problems, which have been used in both set theory and computable analysis.

We then use the new reducibility to present results from [33] in the language of morphisms (Theorem 6.15). This result is closely related to Monin’s resolution [31] of the Γ question which was stated in [1].

6.1. Addition and multiplication

Definition 6.1.
Let A and B be Weihrauch problems.
The problem $A \times B$ is defined by letting ${(A \times B)}_{inst} = A_{inst} \times B_{inst}$ , ${(A \times B)}_{sol} = A_{sol} \times B_{sol}$ , and $(a, b) (A \times B) (\hat{a}, \hat{b})$ if and only if $a A \hat{a}$ and $b B \hat{b}$ .

The problem $A + B$ is defined by letting ${(A + B)}_{inst} = A_{inst} \times B_{inst}$ , ${(A + B)}_{sol} = A_{sol} \times B_{sol}$ , and $(a, b) (A + B) (\hat{a}, \hat{b})$ if and only if $a A \hat{a}$ or $b B \hat{b}$ .

Lemma 6.2.
$A, B \to A \times B$ .
Proof.
To reduce A to $A \times B$ , fix some computable $b^{} \in B_{inst}$ . On the instance side map a to $(a, b^{})$ ; on the solution side map $(\hat{a}, \hat{b})$ to $\hat{a}$ . Of course $B \to A \times B$ is identical. □
Remark 6.3.
$A \times B \to A ⋆ B$ , but not always the other way round.

The following requires only running through the definitions:
Lemma 6.4.

${(A \times B)}^{⊥} = A^{⊥} + B^{⊥}$ .

${(A + B)}^{⊥} = A^{⊥} \times B^{⊥}$ .

As a result:
Lemma 6.5.
$A + B \to A, B$ .

It is also clear that the sum and product induce well-defined and nice operations on morphism classes, namely:
Lemma 6.6.

If $A \to \hat{A}$ and $B \to \hat{B}$ then $A \times B \to \hat{A} \times \hat{B}$ and $A + B \to \hat{A} + \hat{B}$ .

$(A \times B) \times C \leftrightarrow A \times (B \times C)$ , and $(A + B) + C \leftrightarrow A + (B + C)$ .

$A \times B \leftrightarrow B \times A$ and $A + B \leftrightarrow B + A$ .

Lemma 6.7.
Suppose that $Card (A)$ and $Card (B)$ are infinite. Then:
$Card (A \times B) = max {Card (A), Card (B)}$ ; and

$Card (A + B) = min {Card (A), Card (B)}$ .

Proof.
(a): By Lemma 6.2, $max {Card (A), Card (B)} ⩽ Card (A \times B)$ . To show equality, let Z be a complete solution set for A and let W be a complete solution set for B; then $Z \times W$ is a complete solution set for $A \times B$ .

(b): By Lemma 6.5, $Card (A + B) ⩽ min {Card (A), Card (B)}$ . To show equality, let R be a complete solution set for $A + B$ ; then either the projection $π_{0} [R]$ is a complete solution set for A, or $π_{1} [R]$ is a complete solution set for B. □

Note how the proofs of Lemma 6.7 are a simplification of the proofs of Proposition 4.5(a) and Proposition 4.6. Indeed we could deduce Lemma 6.7 from these propositions, using the reduction $A \times B \to A ⋆ B$ .
Lemma 6.8.

$H (A \times B) = H (A) \cap H (B)$ .

$H (A + B) = H (A) \cup H (B)$ .

Proof.
(a): By Lemma 6.2, $H (A \times B) \subseteq H (A) \cap H (B)$ . For equality, let $x \in H (A) \times H (B)$ ; let $c \in A_{sol}$ and $d \in B_{sol}$ be both x-computable and solve every computable A-instance and every computable B-instance, respectively. Then $(c, d)$ is x-computable and solves every computable $(A \times B)$ -instance.

(b): By Lemma 6.5, $H (A) \cup H (B) \subseteq H (A + B)$ . For equality, let $x \in H (A + B)$ ; let $(c, d)$ be x-computable and solve every computable $(A + B)$ -instance. If c doesn’t solve every computable A-instance, then d solves every computable B-instance. □

Using duality (Lemma 6.4), we get the analogous results for the non-lowness classes: $NL (A \times B) = NL (A) \cup NL (B)$ and $NL (A + B) = NL (A) \cap NL (B)$ .

These characterisations of cardinals and classes related to sums and products invite a weakening of morphism reduction. A positive Boolean combination of a problem A is a problem obtained from copies of A by repeatedly using addition and multiplication, for example $(A + A) \times (A + (A \times A))$ . We can use these concepts to define yet another weakening of morphism implication by declaring all positive Boolean combinations of a problem to be equivalent:
Definition 6.9.
Let R be the set of pairs $(A, B)$ of Weihrauch problems such that $\hat{A} \to \hat{B}$ for some positive Boolean combination $\hat{A}$ of A and $\hat{B}$ of B. We write $A ⇝ B$ if $(A, B)$ lies in the transitive closure of R.

The analysis so far yields the following:
Lemma 6.10.
Suppose that $A ⇝ B$ . Then:
$Card (A) ⩽ Card (B)$ .

$H (B) \subseteq H (A)$ .

$B^{⊥} ⇝ A^{⊥}$ .

Part (c) uses the fact that the dual of a positive Boolean combination of A is a positive Boolean combination of $A^{⊥}$ . It follows that if $A ⇝ B$ then $NL (A) \subseteq NL (B)$ .
6.2. Bounded IOE problems

Bounded IOE problems were investigated in set theory by Kamo and Osuga [36] (this followed work on other cardinals indexed by growth rates of functions, for example [18,22]). The associated highness classes in computability were introduced by Brendle and Nies [9].

For a function $h : ω \to ω$ we let $Bdd (h) = h^{ω} = \prod_{n} h (n)$ be the collection of functions $f : ω \to ω$ such that for all n, $f (n) < h (n)$ . We let $IOE (h)$ be the restriction of $IOE$ to instances and solutions in $Bdd (h)$ . Throughout this section we assume that the bounding functions h are computable.

Lemma 6.11.
If $\tilde{h} ⩽ h$ then $IOE (\tilde{h}) \to IOE (h)$ .
Proof.
Map an instance to itself; map a solution f to $λ n . min {f (n), \tilde{h} (n) - 1}$ . □

For functions $h_{0}$ , $h_{1}$ we use the usual join operation: $(h_{0} \oplus h_{1}) (2 n + i) = h_{i} (n)$ . For a function h, the splitting of h into the two standard columns is the pair $(h_{0}, h_{1})$ such that $h = h_{0} \oplus h_{1}$ .
Lemma 6.12.
$IOE (h_{0}) + IOE (h_{1}) \to IOE (h_{0} \oplus h_{1})$ .
Proof.
Map a problem $(f_{0}, f_{1})$ to the join $f_{0} \oplus f_{1}$ ; map a solution $g = g_{0} \oplus g_{1}$ to its splitting $(g_{0}, g_{1})$ . If $(f_{0} \oplus f_{1}) IOE g$ then either $f_{0} IOE g_{0}$ or $f_{1} IOE g_{1}$ . □

As a result, for every h, $IOE (h) ⇝ IOE (h \oplus h)$ .

For a computable real number $a > 1$ we let $\begin{matrix} ℓ_{a} (n) = ⌊ a^{n} ⌋ . \end{matrix}$ Lemma 6.13.
Let $j (n)$ be a non-decreasing function. Then for all computable $a, b > 1$ , $\begin{matrix} IOE (j \circ ℓ_{b}) ↭ IOE (j \circ ℓ_{a}) . \end{matrix}$
Proof.
Let $b > 1$ . Since j is non-decreasing, $(j \circ ℓ_{b^{2}}) \oplus (j \circ ℓ_{b^{2}}) ⩽ j \circ ℓ_{b}$ , and so by Lemma 6.12 and Lemma 6.11, $\begin{matrix} IOE (j \circ ℓ_{b^{2}}) ⇝ IOE ((j \circ ℓ_{b^{2}}) \oplus (j \circ ℓ_{b^{2}})) \to IOE (j \circ ℓ_{b}) . \end{matrix}$ Iterating, for all $b > 1$ and $k \in N$ , $\begin{matrix} IOE (j \circ ℓ_{b^{2^{k}}}) ⇝ IOE (j \circ ℓ_{b}) . \end{matrix}$ To prove the lemma, let $a, b > 1$ . Without loss of generality $b < a$ . For some k, $b^{2^{k}} > a$ ; by Lemma 6.11, $\begin{matrix} IOE (j \circ ℓ_{b}) \to IOE (j \circ ℓ_{a}) \to IOE (j \circ ℓ_{b^{2^{k}}}) ⇝ IOE (j \circ ℓ_{b}) . \end{matrix}$ □
Corollary 6.14.
For all computable $a > 1$ , $IOE (2^{2^{n}}) ↭ IOE (2^{ℓ_{a}})$ .

6.3. Besicovitch distance and the Γ question

Recall that for finite binary strings $σ, τ$ of the same length n, the normalised Hamming distance between σ and τ is $\begin{matrix} d (σ, τ) = \frac{# {k < n : σ (k) \neq τ (k)}}{n} . \end{matrix}$ For $x, y \in 2^{ω}$ , the Besicovitch distance between x and y is $\begin{matrix} d (x, y) = \underset{n}{lim sup} d (x ↾ n, y ↾ n) . \end{matrix}$ Brendle and Nies [9], motivated by [12], introduced the following Weihrauch problems, for each computable $p \in [0, 1]$ :

$Close (p)$ : an instance is $x \in 2^{ω}$ ; a solution is $y \in 2^{ω}$ such that $d (x, y) < p$ .

The dual of $Close (p)$ is $Far (p)$ : an instance is $x \in 2^{ω}$ ; a solution is $y \in 2^{ω}$ such that $d (x, y) ⩾ p$ .

Thus, $H (Close (p))$ is the set of oracles that compute a point which has distance $< p$ to any computable point; this is clearly nonempty only if $p > 1 / 2$ . On the other hand, $NL (Close (p)) = H (Far (p))$ is the set of oracles that compute a point which has distance at least p from any computable point. See [35] for a formalisation using Hausdorff distance.

Hirschfeldt et al. [12] showed that for positive $p ⩽ 1 / 2$ , $NL (Close (p))$ consists of all of the nonzero degrees, so again we are interested in the case $p > 1 / 2$ . Brendle and Nies [9] examined relationships between the associated cardinals and highness classes, and their relationship with the Cichoń diagram. Monin and Nies [32,33] then showed that the highness classes and cardinals associated with the problems $Close (p)$ and $IOE (2^{2^{n}})$ are related. In morphism form, their results give:

Theorem 6.15.
For all computable $p \in (1 / 2, 1)$ , $\begin{matrix} Far (p) ↭ IOE (2^{2^{n}}) . \end{matrix}$

It follows, of course, that for all computable $p, q \in (1 / 2, 1)$ , $Far (p) ↭ Far (q)$ (and so also that $Close (p) ↭ Close (q)$ ). As a result $H (Close (p)) = H (Close (q))$ and $H (Far (p)) = H (Far (q))$ , and $Card (Close (p)) = Card (Close (q))$ , which is how the result is stated in [33] (which also investigated the amount of uniformity of the reductions). Monin and Nies’s work was partly motiveated by the so-called Γ question.

For $x \in 2^{ω}$ , consider $\begin{matrix} d (x, R) = inf {d (x, y) : y is computable} . \end{matrix}$ Andrews et al. [1] define $\begin{matrix} Γ (d) = 1 - sup_{x \in d} d (x, R) . \end{matrix}$ So $1 - Γ (d)$ says how far we can get from computable points among the d-computable points. The values 0, 1, and $1 / 2$ are possible; their observation above shows that values strictly between $1 / 2$ and 1 are not. Andrews et al. [1] asked whether values between 0 and $1 / 2$ are possible. Monin showed:
Theorem 6.16 (Monin).

If $Γ (d) < 1 / 2$ then $Γ (d) = 0$ .

Theorem 6.15 gives a quick proof of Monin’s result:

Proof.
Let $y \in d$ and suppose that $d (y, R) = p > 1 / 2$ . Let $q \in (1 / 2, 1)$ be computable; we need to show that there is some $x ⩽_{T} y$ such that $d (x, R) ⩾ q$ ; this follows from $H (Far (\tilde{p})) = H (Far (q))$ , where $\tilde{p} \in (1 / 2, p)$ is computable. □

This is a-historical: In [32], Monin and Nies first showed that $Close (p)$ and $IOE (2^{2^{n}})$ are related; they essentially proved one direction of Theorem 6.15 (which was later stated in morphism form by Kihara [24]). Monin [31] then used the list decoding theorem, discussed below, to prove Theorem 6.16; this technique was then used by Monin and Nies in [33] to prove the other direction of Theorem 6.15. We now present the proof of Theorem 6.15 in morphism form.

The main map

For a function $ℓ : ω \to ω$ we let $StrLth (ℓ) = \prod_{n} {0, 1}^{ℓ (n)}$ be the collection of functions $f : ω \to 2^{< ω}$ such that for all n, $| f (n) | = ℓ (n)$ . This collection is naturally identified with $Bdd (2^{ℓ})$ .

For a function $ℓ : ω \to ω$ we define a bijection $Φ_{ℓ} : 2^{ω} \to StrLth (ℓ)$ : Let $⟨ J_{n}^{ℓ} ⟩$ be the partition of ω into an increasing sequence of intervals, with $| J_{n} | = ℓ (n)$ . Then $Φ_{ℓ} (x) (n) = x ↾ J_{n}$ . The inverse of $Φ_{ℓ}$ is obtained by concatenating the values of a function in $StrLth (ℓ)$ . In this section, all the functions ℓ are computable.

For the following lemma, and below, for $x, y \in 2^{ω}$ , we let $\begin{matrix} \underline{d} (x, y) = \underset{n}{lim inf} d (x ↾ n, y ↾ n) . \end{matrix}$
Lemma 6.17.
Let $a > 1$ , and let $x, y \in 2^{ω}$ ; let $r \in [0, 1]$ .
Suppose that $d (Φ_{ℓ_{a}} (x) (n), Φ_{ℓ_{a}} (y) (n)) ⩽ r$ for infinitely many n. Then $\underline{d} (x, y) ⩽ 1 / a + r (1 - 1 / a)$ .

Suppose that $d (Φ_{ℓ_{a}} (x) (n), Φ_{ℓ_{a}} (y) (n)) ⩽ r$ for all but finitely many n. Then $d (x, y) ⩽ r + (a - 1)$ .

Proof.
Let $⟨ J_{n} ⟩ = ⟨ J_{n}^{ℓ_{a}} ⟩$ be the increasing sequence of intervals with $| J_{n} | = ℓ_{a} (n)$ , and let $b_{n} = max J_{n} = \sum_{m ⩽ n} ℓ_{a} (m)$ . For brevity, let $x_{n} = x ↾ J_{n} = Φ_{ℓ_{a}} (x) (n)$ and similarly let $y_{n} = y ↾ J_{n}$ .

Suppose that $d (x_{n}, y_{n}) ⩽ r$ . Then $\begin{matrix} d (x ↾ b_{n}, y ↾ b_{n}) ⩽ \frac{b_{n - 1}}{b_{n}} + r \frac{ℓ_{a} (n)}{b_{n}} . \end{matrix}$ For (a), we then use the fact that ${lim}_{n} b_{n - 1} / b_{n} = 1 / a$ and ${lim}_{n} ℓ_{a} (n) / b_{n} = 1 - 1 / a$ .

For (b), as distance is invariant under finite changes, we may assume that for all n, $d (x_{n}, y_{n}) ⩽ r$ . Let $n < ω$ and let $m \in J_{n}$ . Then $\begin{matrix} d (x ↾ m, y ↾ m) ⩽ \frac{r b_{n - 1} + (m - b_{n - 1})}{m} ⩽ \frac{r b_{n - 1} + ℓ_{a} (n)}{b_{n - 1}} = r + \frac{ℓ_{a} (n)}{b_{n - 1}}, \end{matrix}$ and note that ${lim}_{n} ℓ_{a} (n) / b_{n - 1} = a - 1$ . □
Proof of one direction of Theorem 6.15: $Far (p) ⇝ IOE (2^{2^{n}})$ .
This of course will work for all $p \in (0, 1)$ . Even though $\underline{d}$ defined above is not a pseudo-metric, we define, for $q \in [0, 1]$ , the analogous Weihrauch problem, $\underline{Close} (q)$ : an instance is $x \in 2^{ω}$ ; a solution is $y \in 2^{ω}$ such that $\underline{d} (x, y) ⩽ q$ . Note that we use a non-strict inequality. This is so that $\begin{matrix} Far (p) \leftrightarrow \underline{Close} (1 - p) . \end{matrix}$ To see this, we observe that for strings σ and τ of the same length, $d (σ^{∁}, τ) = 1 - d (σ, τ)$ and so for $x, y \in 2^{ω}$ , $d (x^{∁}, y) = 1 - \underline{d} (x, y)$ . The morphisms take a complement on the instance side and use the identity for solutions.

It remains, therefore, to show that $\underline{Close} (q) ⇝ IOE (2^{2^{n}})$ for all computable $q \in (0, 1)$ . Given such q, let $a = 1 / q$ , so $a > 1$ . Using $Φ_{ℓ_{a}}$ on the instance side, and $Φ_{ℓ_{a}}^{- 1}$ on the solution side, we get $\begin{matrix} \underline{Close} (q) \to IOE (2^{ℓ_{a}}) . \end{matrix}$ This follows from Lemma 6.17(a), with $r = 0$ . The proof then ends by quoting Corollary 6.14. □

As discussed above, this direction was proved in [32]; the morphism $\underline{Close} (q) \to IOE (2^{ℓ_{1 / q}})$ was explicitly stated by Kihara [24, Prop.3.8(1)].

Infinitely often closeness

Toward the other direction, we introduce along the way a few intermediate problems. Again $ℓ : ω \to ω$ is a function and $p \in [0, 1]$ is a real number. We consider the following Weihrauch problem:
$IOClose (ℓ, p)$ : an instance is $f \in StrLth (ℓ)$ ; a solution is $g \in StrLth (ℓ)$ such that for infinitely many n, $d (f (n), g (n)) ⩽ p$ .
Lemma 6.18.
Let $r \in [0, 1]$ , let $a > 1$ , and let $p \in [0, 1]$ such that $p > r + (a - 1)$ . Then $\begin{matrix} IOClose (ℓ_{a}, 1 - r) \to Far (p) . \end{matrix}$
Proof.
We verify the dual: $Close (p) \to AEFar (ℓ_{a}, 1 - r)$ , where $g \in Bdd (ℓ)$ is a $AEFar (ℓ, q)$ -solution for f if for all but finitely many n, $d (f (n), g (n)) ⩾ q$ . By mapping, on the instance side, a function $f \in StrLth (ℓ)$ to $λ n . f {(n)}^{∁}$ , we see that $AEFar (ℓ, 1 - r)$ is equivalent to $AEClose (ℓ, r)$ , where as expected a solution g now staisfies, for all but finitely many n, $d (f (n), g (n)) < r$ .

To reduce $Close (p) \to AEFar (ℓ_{a}, r)$ we use $Φ_{ℓ_{a}}$ on the instance side and $Φ_{ℓ_{a}}^{- 1}$ on the solution side, appealing to Lemma 6.17(b). □

Bounded traces

Onwards to tracing. We look at bounded traces. Again fix ℓ; the functions to be traced are still elements of $StrLth (ℓ)$ . As in Section 2, we name traces by effectively coding finite sets by natural numbers. We now deal with traces that are bounded by a constant function. The Weihrauch problem is:

$IOTrace (ℓ, L)$ : an instance is a function $f \in StrLth (ℓ)$ . A solution is an L-trace T which infinitely often traces f.

The list decoding theorem says: for all $q \in (0, 1 / 2)$ there are $L = L (q)$ and $ε = ε (q)$ such that for all m, there is a set $C_{m} \subseteq {0, 1}^{m}$ of size $2^{⌊ ε m ⌋}$ which is sparse in the sense that every string $σ \in {0, 1}^{m}$ is within distance $< q$ to at most L elements of $C_{m}$ .

We now fix $q \in (0, 1 / 2)$ and obtain the resulting ε and L.
Lemma 6.19.
For all $ℓ : ω \to ω$ , $\begin{matrix} IOTrace (⌊ ε ℓ ⌋, L) \to IOClose (ℓ, q) . \end{matrix}$
Proof.
Fix $⟨ C_{m} ⟩$ as promised. Since $| C_{m} | = 2^{⌊ ε m ⌋}$ , we identify $StrLth (⌊ ε ℓ ⌋)$ with $\prod_{n} C_{ℓ (n)}$ , which is a subset of $StrLth (ℓ)$ .

So now on the instance side we can take the identity function. Given a solution $g \in StrLth (ℓ)$ , let $T (n) = {σ \in C_{ℓ (n)} : d (σ, g (n)) < q}$ . The properties of $C_{m}$ mean that $| T (n) | ⩽ L$ . If g is an $IOClose (ℓ, q)$ -solution for f then T is an $IOTrace (⌊ ε ℓ ⌋, L)$ -solution for f. □
Lemma 6.20.
For all non-decreasing ℓ and L, $\begin{matrix} IOTrace (ℓ, L) ↭ IOTrace (ℓ \oplus ℓ, L) . \end{matrix}$
Proof.
Similar to the proof of Lemma 6.12. If $\tilde{ℓ} ⩽ ℓ$ then as in Lemma 6.11, $IOTrace (\tilde{ℓ}, L) \to IOTrace (ℓ, L)$ . On the instance side, map f to the function g obtained by extending each string $f (n)$ (of length $\tilde{ℓ} (n)$ ) to a string of length $ℓ (n)$ , say by adding zeros; map a solution T to $λ n . {σ ↾ \tilde{ℓ} (n) : σ \in T (n)}$ .

Next we see that $IOTrace (ℓ_{0}, L) + IOTrace (ℓ_{1}, L) \to IOTrace (ℓ_{0} \oplus ℓ_{1}, L)$ . On the instance side, we map $(f, g)$ to $f \oplus g$ ; on the solution side, we map T to the pair $(T_{0}, T_{1})$ , where $T_{i} (n) = T (2 n + i)$ . □
Corollary 6.21.
For all $a > 1$ , $ε > 0$ and L, $\begin{matrix} IOTrace (L \cdot 2^{n}, L) ↭ IOTrace (⌊ ε ℓ_{a} ⌋, L) . \end{matrix}$
Proof.
This is an elaboration on the proof of Lemma 6.13, this time adding multiplicative constants. The proof of Lemma 6.13, this time using Lemma 6.20, shows that for all computable $a, b > 1$ , $IOTrace (ℓ_{a}, L) ↭ IOTrace (ℓ_{b}, L)$ . For any computable $α > 0$ and $b > 1$ , $α ℓ_{b}$ is dominated by $ℓ_{a}$ for all $a > b$ and dominates $ℓ_{a}$ for all $a < b$ . Since we only need to correctly trace infinitely often, the morphisms can ignore finitely many “wrong” n’s. □

The last step is: Lemma 6.22.
For all ℓ and L, $IOE (2^{ℓ}) ⇝ IOTrace (L \cdot ℓ, L)$ .
Proof.
We prove that $\sum_{L} IOE (2^{ℓ}) \to IOTrace (L \cdot ℓ, L)$ . We think of $Bdd (2^{ℓ})$ as $StrLth (ℓ)$ . Map $f \in StrLth (ℓ)$ to the function mapping n to the conctenation of $f (n)$ with itself L times. Now let T be a trace; we may assume each $T (n)$ contains exactly L elements. for $i < L$ let $g_{i} (n)$ be the $i^{th}$ block of the $i^{th}$ element of $T (n)$ . For some i, for infinitely many n, $f (σ) \hat{} \dots \hat{} f (σ)$ equals the $i^{th}$ element of $T (n)$ ; for that i, $f IOE g_{i}$ . □
Proof of Theorem 6.15.
Let $p \in (1 / 2, 1)$ ; it remains to show that $IOE (2^{2^{n}}) ⇝ Far (p)$ . Pick some $r \in (1 / 2, p)$ ; pick some $a > 1$ such that $a - 1 < p - r$ . So $p > r + (a - 1)$ . Let $q = 1 - r$ and let $ε = ε (q)$ and $L = L (q)$ be obtained from the list decoding theorem.

By Lemma 6.22, $IOE (2^{2^{n}}) ⇝ IOTrace (L \cdot 2^{n}, L)$ . By Corollary 6.21, $IOTrace (L \cdot 2^{n}, L) ⇝ IOTrace (⌊ ε ℓ_{a} ⌋, L)$ . By Lemma 6.19, $IOTrace (⌊ ε ℓ_{a} ⌋, L) \to IOClose (ℓ_{a}, q)$ . By Lemma 6.18, $IOClose (ℓ_{a}, q) \to Far (p)$ . □

7. On Kurtz

The σ-ideal $E$ generated by compact null sets was studied by Bartozysnki and Shelah, who characterised, among others, the cardinals $add (E)$ and $cof (E)$ . In computability, the associated notion of randomness / genericity is that of Kurtz randomness: avoiding all null, effectively closed subsets of Cantor space. The relevant Weihrauch problem is $Supset (E)$ : an instance is a null $Σ_{2}^{0}$ set P; a solution is a null $Σ_{2}^{0}$ set Q such that $P \subseteq Q$ .

Our goal in this section is:

Theorem 7.1.
.

As a result we get:
Theorem 7.2 (Bartoszynski, Shelah [3]).

$add (E) = add (M)$ and $cof (E) = cof (M)$ .

Together with Corollary 4.15, we obtain:

Theorem 7.3.
A degree is low for $Σ_{2}^{0}$ null sets if and only if it is hyperimmune-free and not DNR.

7.1. Lowness for Kurtz tests and randomness

As with the analogus problem $Supset (M)$ , in computability, the notions which have been studied are not lowness for $Σ_{2}^{0}$ null sets, but rather, lowness for closed null sets (lowness for Kurtz test), and lowness for Kurtz randomness: computing a closed, null set Q which contains a Kurtz random point. The method we used above of proving equivalence of all three notions can be modified to the Kurtz context as well.

Let $K N$ be the collection of closed, null sets. First, we obtain the analogue of Proposition 4.16:

Proposition 7.4.
$Supset (E) \to Supset (K N)$ .

The proof is identical. We then define the problem $FractalSpill (K N)$ as above.
Proposition 7.5.
$Spill (K N) \leftrightarrow FractalSpill (K N)$ .
Proof.
The construction is identical to that proving Lemma 4.18, except that having determined that $n \in I$ , for $σ \in S$ of length n, we observe that under the assumption that $[T]$ is null, the tree $⋃_{k ⩽ | σ |} (σ ↾ k) \hat{} T$ is null as well, and so we can find a clopen set $D \subseteq [σ]$ disjoint from that tree such that $λ (D | σ) ⩾ 1 - 2^{- n}$ ; we remove D from S. The next element of I is bigger than the granularity of all such D’s. □

The rest is identical: if Γ is a countable collection of closed, null sets, closed under the shift operator, and $(Q, I)$ is a $FractalSpill (K N)$ -solution for all $P \in Γ$ , then we build a point in Q avoiding all $P \in Γ$ . We thus obtain:
Theorem 7.6 (Greenberg, J. Miller [19]).

The following are equivalent for $x \in 2^{ω}$ :

x is low for Kurtz tests.

x is low for Kurtz randomness.

x is hyperimmune-free and not DNR.

We also obtain the analogous result in the $Δ_{1}^{1}$ context:

Theorem 7.7 (Kjos-Hanssen, Nies, Stephan, Yu [27]).

An oracle is low for $Δ_{1}^{1}$ Kurtz randomness if and only if it is $Δ_{1}^{1}$ -dominated and every $f \in Δ_{1}^{1} (x)$ is infinitely often equal to some $Δ_{1}^{1}$ function.

7.2. Revising the problem

Our goal, as stated, is Theorem 7.1. It turns out, though, that the bulk of our analysis concerns the following Weihrauch problem:

$Supset (E, N)$ : an instance is a null $Σ_{2}^{0}$ set P; a solution is a null set R such that $P \subseteq R$ .

The identity map in both directions shows that $Supset (E, N) \to Supset (E)$ . We will show:

Proposition 7.8.
.

As a result, we obtain:
Theorem 7.9 (Greenberg, J. Miller [19]).

Let $x \in 2^{ω}$ . There is an x-computable $Σ_{2}^{0}$ null set not contained in any Schnorr null set if and only if x is high or DNR.

Before we prove Proposition 7.8, we show how it implies the main theorem. We use the following two reductions.

Proposition 7.10.
$Dom \to Supset (E)$ .
Proof.
On the instance side, given $f \in ω^{ω}$ , we assume that f is strictly increasing, and map it to $\begin{matrix} Q^{f} = {x \in 2^{ω} : (\forall n) x (f (n)) = 0} . \end{matrix}$

On the solution side, we are given a sequence $⟨ T_{n} ⟩$ of closed null sets. Let $h (n, k)$ be the least s such that every string σ of length k has an extension of length s which is off $T_{n}$ . Let $g (0) = 0$ and $g (n + 1) = h (g (n), g (n))$ ; we map $⟨ T_{n} ⟩$ to $n \mapsto g (2 n)$ .

To show that this works, suppose that $f \in ω^{ω}$ , and that for some $⟨ T_{n} ⟩$ , the function $n \mapsto g (2 n)$ does not dominate f. We claim that there are infinitely many n for which for some m, $f (n) ⩽ g (m) ⩽ g (m + 1) < f (n + 1)$ . Otherwise, for some k, for large enough n, $f (n) ⩽ g (n + k) ⩽ g (2 n)$ . We use this to construct a point $x \in Q^{f} ∖ ⋃_{n} [T_{n}]$ . As usual, we assume that $⟨ T_{n} ⟩$ is nested, so it suffices to avoid infinitely many trees $T_{n}$ . To do this, suppose that we have already determined some finite $σ ≺ x$ such that $[σ] \cap Q^{f} \neq \emptyset$ of length some $f (n)$ such that $f (n) ⩽ g (m) ⩽ g (m + 1) < f (n + 1)$ . Then for every extension τ of σ of length $g (m + 1)$ , $[τ] \cap Q^{f} \neq \emptyset$ . On the other hand, we can find such an extension of σ which is off $T_{g (m)}$ . □
Remark 7.11.
The proof actually shows that $Dom \to Supset (E, M)$ .
Proposition 7.12.
$Supset (E) \to Supset (E, N) ⋆ Dom$ .
Proof.
This resembles the proof of Proposition 4.9, with a dose of compactness.

On the instance side, map a $Σ_{2}^{0}$ null set $P = ⋃_{n} P_{n}$ to the pair $(P, F)$ where for a null set V (given as $⋂_{m} V_{m}$ ) such that $P \subseteq V$ , we let $F (V)$ be the function $h \in ω^{ω}$ defined as follows: $h (n, m)$ is the least s such that $P_{n, s} \subseteq V_{m, s}$ . (The closed sets $P_{n}$ are given as trees $T_{n}$ , and we let $P_{n, s}$ be the clopen set determined by the $s^{th}$ level of T; we similarly treat each $V_{m}$ .) By compactness, h is well-defined, and in fact is uniformly computable given P and V.

On the solution side, we map a pair $(V, g)$ to the $Σ_{2}^{0}$ null set $⋃_{n} ⋂_{m} V_{m, g (n, m)}$ . To show that this works: if $g (n, -)$ majorises $h (n, -)$ (where $h = F (V)$ ) then $P_{n} \subseteq ⋂_{m} V_{m, g (n, m)}$ ; as usual we may assume that $P_{n} \subseteq P_{n + 1}$ . □
Proof of Theorem 7.1, assuming Proposition 7.8.
In one direction, we first observe that $Pass (M) ⇢ Supset (E)$ ; this is because $\begin{matrix} Pass (M) ⇢ IOE ⇢ Supset (E, M) \to Supset (E) . \end{matrix}$ Together with Proposition 7.10 (and using the fact that $A ⇢ C$ , $B ⇢ C$ implies $A ⋆ B ⇢ C$ ) we get $\begin{matrix} Supset (M) \to Pass (M) ⋆ Dom ⇢ Supset (E) . \end{matrix}$

In the other direction, if $Supset (E, N) \to Pass {(M)}^{⋆ k}$ , then using Proposition 7.12, $\begin{matrix} Supset (E) \to Pass {(M)}^{⋆ k} ⋆ Dom \to Supset {(M)}^{⋆ (k + 1)} . \end{matrix}$ □

7.3. Analysis of $Supset (E, N)$

We work toward a proof of Proposition 7.8.

Proposition 7.13.
$Supset (E, N) \to IOE$ .
Proof.
On the instance side, we are given a $Σ_{2}^{0}$ null set $P = ⋃ P_{n}$ . We map it to a sequence $⟨ C_{n} ⟩$ of (codes of) clopen sets such that for all n, $P_{n} \subseteq C_{n}$ and $λ (C_{n}) = 2^{- n}$ . (For each n, find a late enough $s (n)$ and let $C_{n} = T_{n, s (n)}$ .)

On the solution side, we are given a sequence $⟨ D_{n} ⟩$ of clopen sets, and we may assume that for all n, $λ (D_{n}) = 2^{- n}$ . We map this sequence to the null set $⋂_{k} U_{k}$ given by $U_{k} = ⋃_{n > k} D_{n}$ . The measure of each $U_{k}$ is computable from $⟨ D_{n} ⟩$ , uniformly. If $⟨ P_{n} ⟩$ maps to $⟨ C_{n} ⟩$ and for infinitely many n, $D_{n} = C_{n}$ then for each n and k, $P_{n} \subseteq U_{k}$ . □
Proposition 7.14.
$Esc \to Supset (E, N)$ .
Proof.
The following argument resembles the proof of [30, Thm.2.2]; the argument of the corresponding cardinal inequality in [2] (Lemma 2.6.13) is non-constructive.

As above, given $f \in ω^{ω}$ , assuming it is increasing, define $\begin{matrix} Q^{f} = {x \in 2^{ω} : (\forall n) x (f (n)) = 0} . \end{matrix}$ The map $f \mapsto Q^{f}$ is our map on instances.

Toward defining our map on solutions, let, for $k < ω$ , $q_{k} = (3 / 4) 2^{- 2 k}$ . What we use11
¹¹
Also of course we use the fact that $⟨ q_{k} ⟩$ is computable and consists of binary rationals. Below we will also assume that $f (k)$ is at least the granularity of $q_{k}$ , i.e. $f (k) ⩾ 2 k + 2$ .

is: $\begin{matrix} \sum_{k = 0}^{\infty} q_{k} = 1, \end{matrix}$ and $\begin{matrix} \sum_{k = 0}^{\infty} q_{k} 2^{k} < 2 . \end{matrix}$

We are given a null set $V = ⋂_{m} V_{m}$ . As mentioned above, by [15, Prop.7.1.6], we assume that for each m, $λ (V_{m}) = 2^{- m}$ . As above we use the clopen approximations $Q_{s}^{f}$ and $V_{m, s}$ , determined by sets of strings of length s.

For each $m ⩾ 1$ , define a function $h_{m} : [m - 1, ω) \to ω$ by letting, for $n ⩾ m - 1$ , $\begin{matrix} h_{m} (n) = (μ s) λ (V_{m, s} | V_{m}) ⩾ \sum_{k ⩽ n} q_{k - (m - 1)} . \end{matrix}$ On the solution side, we map V to the function $\begin{matrix} h (n) = max_{m ⩽ n + 1} h_{m} (n) . \end{matrix}$ Thus for all $m ⩾ 1$ and $n ⩾ m - 1$ , $h_{m} (n) ⩽ h (n)$ .

To show that this works, we need to show that if $Q^{f} \subseteq V$ then h escapes f.

The rough idea is that if h is majorised by f beyond $m - 1$ , then $V_{m}$ is spending its measure before $Q^{f}$ has thinned itself (by committing to the bit at position $f (n)$ being 0). Since the later thinnings will happen independently of this preemptively spent measure, most of this measure is wasted, and so $V_{m}$ will not have enough measure to cover $Q^{f}$ .

The following claim is the combinatorial heart of this proof. Claim 7.14.1.
Fix $m ⩾ 1$ and $d ⩾ m - 1$ . Suppose that for all $n \in [m - 1, d]$ , $h_{m} (n) ⩽ f (n)$ . Then $Q_{f (d)}^{f} ⊈ V_{m, f (d)}$ .

The claim gives the proposition. To see this, suppose that $Q^{f} \subseteq V$ . Then $Q^{f} \subset V_{m}$ for every m. By compactness, for every m there is some d such that $Q^{f} \subset V_{m, f (d)}$ . Because every string of length $f (d)$ on (the tree defining) $Q^{f}$ is extendible, we in fact have $Q_{f (d)}^{f} \subseteq V_{m, f (d)}$ . The claim then ensures that for every m there is some $n ⩾ m - 1$ such that $h_{m} (n) > f (n)$ . So $h (n) ⩾ h_{m} (n) > f (n)$ .

It thus remains to prove the claim.

By definition of $h_{m}$ , and under the assumption of the claim, for all $n \in [m - 1, d]$ we have $\begin{matrix} λ (V_{m, f (n)} | V_{m}) ⩾ \sum_{k = 0}^{n - (m - 1)} q_{k} . \end{matrix}$ By removing short strings from the set of strings defining $V_{m}$ , but leaving their extensions, we may, without decreasing $V_{m, f (d)}$ , assume that we have equality: $\begin{matrix} λ (V_{m, f (n)} | V_{m}) = \sum_{k = 0}^{n - (m - 1)} q_{k} . \end{matrix}$ Define $U_{m - 1} = V_{m, f (m - 1)}$ and for $n \in [m, d]$ let $\begin{matrix} U_{n} = V_{m, f (n)} - V_{m, f (n - 1)} . \end{matrix}$ So for all $n ⩽ d$ , $λ (U_{n}) = q_{n - (m - 1)} λ (V_{m}) = q_{n - (m - 1)} 2^{- m}$ .

Fix $n \in [m - 1, d]$ . The set $U_{n}$ can only have “opinions” about the bits $f (r)$ for $r < n$ , while those bits $f (r)$ with $r \in [n, d)$ are independent of $U_{n}$ . So $\begin{matrix} λ (U_{n} \cap Q_{f (d)}^{f}) = λ (U_{n} \cap Q_{f (n)}^{f}) \cdot 2^{- (d - n)} ⩽ λ (U_{n}) \cdot 2^{- (d - n)} = q_{n - (m - 1)} 2^{- m} 2^{- (d - n)} . \end{matrix}$ It follows that $\begin{array}{l} λ (V_{m, f (d)} \cap Q_{f (d)}^{f}) & = \sum_{n = m - 1}^{d} λ (U_{n} \cap Q_{f (d)}^{f}) \\ ⩽ 2^{- d} \sum_{n = m - 1}^{d} q_{n - (m - 1)} 2^{n - m} < 2^{- d} \cdot \frac{1}{2} \sum_{k = 0}^{\infty} q_{k} 2^{k} < 2^{- d}, \end{array}$ whereas $λ (Q_{f (d)}^{f}) = 2^{- d}$ . Hence it is impossible that $Q_{f (d)}^{f} \subseteq V_{m, f (d)}$ . □
Proposition 7.15.
$IOE \to Supset (E, N) ⋆ Esc$ .
Proof.
We use the “Svelte tree” machinery from [19]. Let $0 = n_{0} < n_{1} < n_{2} \dots$ be a computable increasing sequence such that $n_{k} - n_{k - 1} = 2^{2 k}$ . Fix a computable bijection $I : ω^{< ω} \to ω$ . For $f \in ω^{ω}$ we define $\begin{matrix} P^{f} = {x \in 2^{ω} : (\forall k) x (I (f ↾ n_{k})) = 0} . \end{matrix}$ Let $k < ω$ . A finite tree $T \subset ω^{< ω}$ is k-svelte if there are finite sets of sequences $⟨ S_{k + 1}, S_{k + 2}, S_{k + 3}, \dots ⟩$ such that:
for all $m ⩾ k + 1$ , $S_{m} \subseteq T$ and every $σ \in S_{m}$ has length $n_{m}$ ;

$| S_{m} | ⩽ 2^{m}$ ;

Every leaf of T extends a sequence in $⋃_{m ⩾ k + 1} S_{m}$ .
In fact, we can get $| S_{m} | ⩽ 2^{m - (k + 1)}$ , but we don’t need this. The main combinatorial result of [19] is: Theorem 7.16 (Thm. 3.3 of [19]).

Let $C \subset 2^{ω}$ be clopen, and suppose that $λ (C) ⩽ 2^{- (k + 1)}$ . Then there is a k-Svelte tree T such that for all $f \in ω^{ω}$ , if $P^{f} \subset C$ then f extends some leaf of T. The tree T can be obtained computably from C.

The map on instances is as follows. We map $f \in ω^{ω}$ to the pair $(P^{f}, F)$ , where for a null set $V = ⋂_{k} V_{k}$ such that $P^{f} \subseteq V$ , $F (V)$ is the function h mapping $k < ω$ to a stage s such that $P_{s}^{f} \subseteq V_{k, s}$ .

On the solution side, we map a pair $(V, \hat{h}) \in N \times ω^{ω}$ to a point $g \in ω^{ω}$ defined as follows. For each $k ⩾ 1$ we compute a $(k - 1)$ -Svelte tree $T_{k}$ such that for every $\tilde{f} \in ω^{ω}$ , if $Q^{\tilde{f}} \subset V_{k, \hat{h} (k)}$ then $\tilde{f}$ extends a leaf of $T_{k}$ . Let $S_{k}^{k}, S_{k + 1}^{k}, S_{k + 2}^{k}, \dots$ witness that $T_{k}$ is $(k - 1)$ -svelte. For each $m ⩾ 1$ let $S_{m} = ⋃_{k ⩽ m} S_{m}^{k}$ . So $| S_{m} | ⩽ 2^{2 m}$ . Since $I_{m} = [n_{m - 1}, n_{m})$ has size $2^{2 m}$ , we can pick injectively, for each $σ \in S_{m}$ , a value $l = l (σ) \in I_{m}$ . We define g so that $g (l) = σ (l)$ . So we have arranged that for every k, for every leaf τ of $T_{k}$ , τ agrees with g on some value $l ⩾ n_{k - 1}$ .

Suppose that $P^{f} \subseteq V$ and that $\hat{h} (k) ⩾ h (k)$ . Then $P^{f} \subset V_{k, \hat{h} (k)}$ . It follows that f extends some leaf of $T_{k}$ , and therefore that g agrees with f at some value $l ⩾ n_{k - 1}$ . Therefore, if $\hat{h}$ escapes h, then $f IOE g$ . □

Proof of Proposition 7.8.
By Proposition 7.13, $Supset (E, N) \to IOE$ . In the other direction, we have $IOE \to Supset (E, N) ⋆ Esc$ and $Esc \to Supset (E, N)$ , so $IOE \to Supset {(E, N)}^{⋆ 2}$ . □

7.4. A self-contained argument

The drawback of the proof given above of $IOE ⇢ Supset (E, N)$ is its reliance on the Svelte tree technology of [19], which takes some work. The original argument is essentially due to Baroszynski and Shelah. We use their argument (simplified at a few places) to give a self-contained proof of this implication. This proof uses techniques which may be of independent interest. We start with a fact which we will use twice. We define the Weihrauch problem:

$Esc \neg Dom$ : an instance is a function $f \in ω^{ω}$ such that $f (n) > n$ ; a solution is a non-decreasing function $g \in ω^{ω}$ , which escapes f but does not dominate it (and $g (n) ⩾ n$ ).

Lemma 7.17 (With Harrison-Trainor).

$Esc \leftrightarrow Esc \neg Dom$ .

Proof.
To reduce $Esc \to Esc \neg Dom$ , we map an instance f to $n \mapsto max {f (n), n + 1}$ , and use the identity on the solutions.

We reduce $Esc \neg Dom$ to $Esc$ . We first define h by $h (0) = f (0)$ and $h (n + 1) = max {f (n + 1), h (n) + 1}$ ; the relevant point is that h is strictly increasing and dominates f. We map f to $\tilde{f}$ defined by $\tilde{f} (0) = h (1)$ and $\tilde{f} (n + 1) = h (\tilde{f} (n) + 1)$ . Note that $\tilde{f}$ is strictly increasing, and that $\tilde{f} (n) ⩾ f (n + 1)$ .

On the solution side, we map a function g, which we assume is strictly increasing, to the “step function” $\tilde{g}$ which on the interval $(g^{(n)} (0), g^{(n + 1)} (0)]$ returns $g^{(n + 1)} (0)$ . So for $k = g^{(n + 1)} (0)$ we have $\tilde{g} (k) = k < f (k)$ , and so $\tilde{g}$ does not dominate f.

To show $\tilde{g}$ escapes f, we show that if $\tilde{g}$ is dominated by f, then g is dominated by $\tilde{f}$ . For typographical clarity, let $a_{n} = g^{(n)} (0)$ . Suppose that $\tilde{g} (k) ⩽ f (k)$ for all $k > a_{m}$ . In particular, for $n ⩾ m$ , $\begin{matrix} g (a_{n}) = a_{n + 1} = \tilde{g} (a_{n} + 1) ⩽ f (a_{n} + 1) ⩽ \tilde{f} (a_{n}) . \end{matrix}$ Now suppose that $n ⩾ m$ and $k \in (a_{n}, a_{n + 1})$ . Then $\begin{array}{l} g (k) & ⩽ g (a_{n + 1}) = a_{n + 2} = \tilde{g} (a_{n + 1} + 1) ⩽ f (a_{n + 1} + 1) \\ ⩽ h (a_{n + 1} + 1) = h (g (a_{n}) + 1) ⩽ h (\tilde{f} (a_{n}) + 1) = \tilde{f} (a_{n} + 1) ⩽ \tilde{f} (k), \end{array}$ using the fact that $g (a_{n}) ⩽ \tilde{f} (a_{n})$ and that $\tilde{f}$ and h are increasing. □
Remark 7.18.
The proof can be modifed to produce a strictly increasing $\tilde{g}$ which does not dominate $n \mapsto n^{2}$ .

On our way, we define a strong variant of covering by a null set. For a set $A \subset ω$ and a clopen set $C \subseteq 2^{ω}$ , we say that the support of C is contained in A ( $supp (C) \subseteq A$ ) if membership in C is determined by examining the locations in A. Formally, C is the union of clopen sets $[p]$ where $p \in 2^{A}$ and $[p] = {x \in 2^{ω} : p ≺ x}$ , where we extend the symbol ≺ to indicate extension of functions, not necessarily initial segment extension. We define the Weihrauch problem

$IndepCover$ : an instance is a closed, null set $P \subset 2^{ω}$ ; a solution is a partition $⟨ I_{n} ⟩$ of ω into intervals and a sequence $⟨ C_{n} ⟩$ of clopen sets such that $λ (C_{n}) ⩽ 2^{- n}$ , $supp (C_{n}) \subseteq I_{n}$ and for infinitely many n, $P \subseteq C_{n}$ .
Lemma 7.19 (Bartozysnki,Shelah [3]).

$IndepCover \to Supset (E, N) ⋆ Esc$ .

Proof.
By Lemma 7.17, we reduce $IndepCover$ to $Supset (E, N) ⋆ Esc \neg Dom$ .

Recall the notation $σ ↷ x$ and $σ ↷ X$ (see the proof of Proposition 4.9). For a set P let $P^{} = ⋃_{σ \in 2^{< ω}} σ ↷ P$ . If P is closed null then $P^{}$ is null $Σ_{2}^{0}$ . We map such a set P to the pair $(P^{}, F)$ , where $F : N \to ω^{ω}$ is defined as follows. We are given a null set $V = ⋂ V_{m}$ , and we assume that $P^{} \subseteq V$ . For $n < ω$ let $P^{n} = ⋃_{σ \in 2^{n}} σ ↷ P$ . It is closed and null. First define $h (n, m)$ to be the least $s > n$ such that $P_{s}^{n} \subseteq V_{m, s}$ .12
¹²
Recall that the granularity of $P_{s}^{n}$ and $V_{m, s}$ is at most s.

Then define inductively $f (0) = 0$ and $f (n + 1) = h (f (n), f (n))$ . We define $F (V) = f$ .

For a null set $V = ⋂ V_{m}$ , and $m < s < ω$ we let $\begin{matrix} Q_{m, s} = ⋃ {[p] : p \in 2^{[m, s)} & [p] \subseteq V_{m, s}} . \end{matrix}$ This is clopen, $λ (Q_{m, s}) ⩽ λ (V_{m}) ⩽ 2^{- m}$ and $supp (Q_{m, s}) \subseteq [m, s)$ .

On the solution side, we are given a null set $V = ⋂ V_{m}$ and a non-decreasing function $g \in ω^{ω}$ such that $g (n) ⩾ n$ . Define $I_{n} = (g (n), g (n + 1)]$ and $\begin{matrix} C_{n} = ⋃_{k \in I_{n}} Q_{k, g (n + 1)} . \end{matrix}$ Then $supp (C_{n}) \subseteq I_{n}$ and $\begin{matrix} λ (C_{n}) ⩽ \sum_{k \in I_{n}} λ (Q_{k, g (n + 1)}) ⩽ \sum_{k \in I_{n}} 2^{- k} < 2^{- g (n)} ⩽ 2^{- n} . \end{matrix}$ We map $(V, g)$ to $⟨ I_{n}, C_{n} ⟩$ .

To show that this works, suppose that $P^{} \subseteq V$ , let $f = F (V)$ (where P maps to $(P^{}, F)$ ), and suppose that g is non-decreasing, escapes f but does not dominate f. Then there are infinitely many n for which $\begin{matrix} g (n) < f (n) < f (n + 1) ⩽ g (n + 1) . \end{matrix}$ Fix such n; we claim that $P \subseteq C_{n}$ . Now $P_{f (n + 1)}^{f (n)} \subseteq V_{f (n), f (n + 1)}$ . We claim that $P \subseteq Q_{f (n), f (n + 1)}$ . Indeed, $P_{f (n + 1)} \subseteq Q_{f (n), f (n + 1)}$ . For let $ρ \in 2^{f (n + 1)}$ such that $[ρ] \subseteq P_{f (n + 1)}$ . Let $p = ρ ↾ [f (n), f (n + 1))$ . For all $σ \in 2^{f (n)}$ , $[σ \hat{} p] = [σ ↷ ρ] \subseteq V_{f (n), f (n + 1)}$ . Thus $[p] \subseteq V_{f (n), f (n + 1)}$ and so $[p] \subseteq Q_{f (n), f (n + 1)}$ .

We then observe that as $f (n + 1) ⩽ g (n + 1)$ , $Q_{f (n), f (n + 1)} \subseteq Q_{f (n), g (n + 1)}$ ; this is because $V_{f (n), f (n + 1)} \subseteq V_{f (n), g (n + 1)}$ . Since $g (n) < f (n)$ , we see that $Q_{f (n), g (n + 1)} \subseteq C_{n}$ . □
Remark 7.20.
In Lemma 7.17, by increasing values, we could require the range of g, and hence of $\tilde{g}$ , to be a subset of any given infinite subset X of ω. That is, $Esc \leftrightarrow Esc \neg {Dom}_{Coarse}$ , where $Esc \neg {Dom}_{Coarse}$ is the Weihrauch problem whose instances are pairs $(f, X)$ where $f \in ω^{ω}$ , $f > id$ , and $X \subseteq ω$ is infinite; a solution is a non-decreasing function g which escapes f, does not dominate f, and $range g \subseteq X$ .

Applying this to the proof of the previous proposition, we see that $\begin{matrix} {IndepCover}_{Coarse} \to Supset (E, N) ⋆ Esc, \end{matrix}$ where ${IndepCover}_{Coarse}$ is the problem whose instances are pairs $(P, X)$ where P is closed null and $X \subseteq ω$ is infinite, and the solutions consist of a partition $⟨ I_{n} ⟩$ of ω into intervals and a sequence $⟨ C_{n} ⟩$ of clopen sets such that $λ (C_{n}) ⩽ 2^{- n}$ , $supp (C_{n}) \subseteq I_{n}$ , for infinitely many n, $P \subseteq C_{n}$ , and the endpoints of the intervals $I_{n}$ are in X.

Another way to say this is that the instances are pairs $(P, ⟨ {\tilde{I}}_{n} ⟩)$ where the latter is a partition of ω into intervals, and for a solution $⟨ I_{n}, C_{n} ⟩$ , $⟨ I_{n} ⟩$ is coarser than $⟨ {\tilde{I}}_{n} ⟩$ : every $I_{k}$ is a union of ${\tilde{I}}_{n}$ ’s.

We need one last Weihrauch problem:

$GapEsc$ : an instance is a function $f \in ω^{ω}$ ; a solution is a non-decreasing function $g \in ω^{ω}$ such that for infinitely many n, $g (n + 1) > f (g (n))$ .
Lemma 7.21.
$Esc \leftrightarrow GapEsc$ .
Proof.
To reduce $Esc$ to $GapEsc$ , we map an instance f to itself. We map a solution g to a function h satisfying $h (g (n)) ⩾ g (n + 1)$ for all n.

In the other direction, naively, it would seem that we could only reduce $GapEsc + GapEsc$ to $Esc$ ; there are two cases, depending on whether the escaping function also dominates or not. We can eliminate the dominating case using Lemma 7.17: we reduce $GapEsc$ to $Esc \neg Dom$ . On the instance side, we map a function f, which we may assume is increasing, to $\tilde{f} (n) = f^{(n)} (0)$ . On the solution side we use the identity map. Suppose that $\tilde{f} Esc \neg Dom g$ . For infinitely many n, $g (n) < \tilde{f} (n) < \tilde{f} (n + 1) < g (n + 1)$ . Then $\begin{matrix} g (n + 1) > \tilde{f} (n + 1) = f (\tilde{f} (n)) > f (g (n)) . \end{matrix}$ □
Lemma 7.22.
There is a computable function $U : ω \to ω$ such that for every sequence ${⟨ I_{k} ⟩}_{k ⩽ m}$ of consecutive (nonempty) intervals, for every clopen set C such that $λ (C) ⩽ 1 / 2$ , there are sets $S_{k} \subseteq I_{k}$ (computably obtained from $⟨ I_{k} ⟩$ and C) such that $| S_{k} | ⩽ U (min I_{k})$ with the property that for every partial choice function $c : [0, m] \to I = ⋃_{k ⩽ m} I_{k}$ such that $c (k) \in I_{k}$ for all $k \in dom c$ , if $\begin{matrix} E_{c} = {x \in 2^{ω} : (\forall k \in dom c) x (c (k)) = 0} \subseteq C, \end{matrix}$ then there is some $k \in dom c$ such that $c (k) \in S_{k}$ .

The point is that $| S_{k} |$ only depends on $min I_{k}$ , while $| I_{k} |$ may be large.
Proof.
Fix a computable decreasing sequence $α_{0} > α_{1} > α_{2} > \dots > 1$ of rational numbers such that $\prod_{k} α_{k} < 2$ . We then let $\begin{matrix} U (m) = 2^{m} \cdot ⌈ - {log}_{2} (1 - α_{m}^{- 1}) ⌉ . \end{matrix}$

Suppose that $⟨ I_{k} ⟩$ and C are given as in the lemma. We may assume that $min I_{0} = 0$ , as U is increasing. Let $k ⩽ m$ ; let $n_{k} = min I_{k}$ . Let $σ \in 2^{n_{k}}$ such that $C \cap [σ] \neq \emptyset$ . We then let $\begin{matrix} S_{k, σ} = {ℓ \in I_{k} : \forall q \in 2^{I_{k}} (q (ℓ) = 0 \to λ (C | σ \hat{} q) > α_{k} λ (C | σ))}, \end{matrix}$ and let $\begin{matrix} S_{k} = ⋃ {S_{σ, k} : σ \in 2^{n_{k}} & C \cap [σ] \neq \emptyset} . \end{matrix}$

We first verify that for each σ, $| S_{k, σ} | ⩽ - {log}_{2} (1 - α_{k}^{- 1})$ . It then follows that $| S_{k} | ⩽ U (n_{k})$ , as $n_{k} ⩾ k$ and so $α_{n_{k}} ⩽ α_{k}$ . Fix σ such that $C \cap [σ] \neq \emptyset$ ; since C is clopen, $λ (C | σ) > 0$ . For brevity, in this argument let $S = S_{k, σ}$ . For every $ℓ < ω$ let $D_{ℓ} = {x \in 2^{ω} : x (ℓ) = 0}$ . Note that $λ (⋃_{ℓ \in S} D_{ℓ}) = 1 - 2^{- | S |}$ . It follows that there are at least $(1 - 2^{- | S |}) 2^{| I_{k} |}$ many $q \in 2^{I_{k}}$ such that $λ (C | σ \hat{} q) > α_{k} λ (C | σ)$ , that is, $λ (C \cap [q] | σ) ⩾ 2^{- | I_{k} |} α_{k} λ (C | σ)$ . Taking the union of $C \cap [q]$ for all such q, we see that $\begin{matrix} λ (C | σ) ⩾ (1 - 2^{- | S |}) \cdot 2^{| I_{k} |} \cdot 2^{- | I_{k} |} \cdot α_{k} \cdot λ (C | σ) \end{matrix}$ and since $λ (C | σ) > 0$ , we get $(1 - 2^{- | S |}) α_{k} ⩽ 1$ , and so the desired bound on $| S |$ .

Now we are given a partial choice function c as in the statement of the lemma. Suppose that for all $k \in dom c$ , $c (k) \notin S_{k}$ . We show that $E_{c} ⊈ C$ .

We define recursively a sequence of strings $σ_{k} \in 2^{n_{k}}$ , with the property that $\begin{matrix} λ (C | σ_{k}) ⩽ \frac{1}{2} \prod_{i < k} α_{i} . \end{matrix}$ We start of course with $σ_{0} = ⟨ ⟩$ , with the measure bound given by the assumption that $λ (C) ⩽ 1 / 2$ . Given $σ_{k}$ for some $k ⩽ m$ , there are three cases. If $k \notin dom c$ then we let $q_{k}$ be any $q \in 2^{I_{k}}$ satisfying $λ (C | σ_{k \hat{} q}) ⩽ λ (C | σ_{k})$ . Otherwise, if $C \cap [σ_{k}] = \emptyset$ then we let $q_{k}$ be any $q \in 2^{I_{k}}$ such that $q (c (k)) = 0$ . Otherwise, since $c (k) \notin S_{k, σ_{k}}$ , and $C \cap [σ_{k}] \neq \emptyset$ , we choose $q_{k}$ to be some $q \in 2^{I_{k}}$ such that $q (c (k)) = 0$ and $λ (C | σ_{k} \hat{} q_{k}) ⩽ α_{k} λ (C | σ_{k})$ . In all three cases we let $σ_{k + 1} = σ_{k} \hat{} q_{k}$ , and the measure bound holds. Then $λ (C | σ_{m + 1}) ⩽ (1 / 2) \prod_{i ⩽ m} α_{i} < 1$ , so $[σ_{m + 1}]$ witnesses that $E_{c} ⊈ C$ as required. □

Finally, the following proposition finishes the proof of $IOE ⇢ Supset (E, N)$ ; with our other results, we get $\begin{matrix} IOE \to Esc ⋆ {IndepCover}_{Coarse} \to Esc ⋆ Supset (E, N) ⋆ Esc \to Supset {(E, N)}^{⋆ 3} . \end{matrix}$ Proposition 7.23.
$IOE \to Esc ⋆ {IndepCover}_{Coarse}$ .
Proof.
We show that $IOE \to GapEsc ⋆ {IndepCover}_{Coarse}$ . We use the computable function U given by Lemma 7.22. Let $h (m) = m + m^{U (m)}$ . Given a function $f \in ω^{ω}$ define $b_{f} : ω \to ω$ by letting $b_{f} (m) = max range f ↾ (h^{(m + 2)} (m))$ .

Given a non-decreasing function g, we assume that $g (0) ⩾ 2$ , and define intervals $J_{k} = [ℓ_{k}, ℓ_{k + 1})$ and $I_{k} = [m_{k}, m_{k + 1})$ (both partitioning ω) as follows: $| J_{k} | = U (m_{k})$ ; $| I_{k} | = g {(k)}^{| J_{k} |}$ . That is, $m_{0} = ℓ_{0} = 0$ ; $ℓ_{k + 1} = ℓ_{k} + U (m_{k})$ and $m_{k + 1} = m_{k} + g {(k)}^{U (m_{k})}$ . Note that $ℓ_{k} ⩽ m_{k}$ . Now by induction on k we can see that $m_{k + 1} ⩽ h^{(k + 1)} (g (k))$ , and so that $ℓ_{k + 2} ⩽ h^{(k + 2)} (g (k))$ . It follows that if $g (n + 1) > b_{f} (g (n))$ then $range f ↾ J_{n + 1} \subseteq g (n + 1)$ . Thus, if $b_{f} GapEsc g$ , then for infinitely many k we have $f ↾ J_{k} \in g {(k)}^{J_{k}}$ . Identifying $I_{n}$ with $g {(n)}^{J_{n}}$ , and writing $f (n) = f ↾ J_{n}$ , we see that for infinitely many n, $f (n) \in I_{n}$ . It follows that $P^{f} = {x \in 2^{ω} : (\forall n) f (n) \in I_{n} \to x (f (n)) = 0}$ is null.

Thus, on the solution side, we map $f \in ω^{ω}$ to the pair $(b_{f}, F)$ , where $F (g) = (P^{f}, ⟨ I_{n} ⟩)$ when $b_{f} GapEsc g$ .

Keeping with g and $⟨ I_{n} ⟩$ , suppose that $⟨ K_{n}, C_{n} ⟩ \in {IndepCover}_{sol}$ and that $⟨ K_{n} ⟩$ is coarser than $⟨ I_{n} ⟩$ . Fix $m > 0$ ; say $K_{m} = I_{a} \cup I_{a + 1} \cup \dots \cup I_{b}$ . We define the sets $S_{k} \subseteq I_{k}$ for $k \in [a, b]$ as given by Lemma 7.22 where we take $C = C_{m}$ . Again thinking of $I_{k}$ as $g {(k)}^{J_{k}}$ , we think of every element of $S_{k}$ as a function from $J_{k}$ to $g (k)$ . As $| S_{k} | ⩽ U (min I_{k}) = U (m_{k}) = | J_{k} |$ , we see that we can find a function $p_{k} \in g {(k)}^{J_{k}}$ which agrees with each element of $S_{k}$ on some input.

On the solution side, we map $(g, ⟨ K_{n}, C_{n} ⟩)$ to the concatenation of the $p_{k}$ ’s, that is to $p \in ω^{ω}$ defined by $p ↾ J_{k} = p_{k}$ .

To see that this works, suppose that indeed $b_{f} GapEsc g$ and, using the notation above, that $⟨ K_{m}, C_{m} ⟩$ solves the problem $(P^{f}, ⟨ I_{n} ⟩)$ . For infinitely many m, $P^{f} \subset C_{m}$ . Define c to be the partial function which is the restriction of f to ${k : f (k) \in I_{k}}$ . For m such that $P^{f} \subset C_{m}$ , if $K_{m} = I_{a} \cup \dots \cup I_{b}$ , let $c_{m} = c ↾ [a, b]$ . The set $E_{c_{m}}$ is the collection of $q \in 2^{K_{m}}$ which are compatible with elements of $P^{f}$ ; since $supp (C_{m}) \subseteq K_{m}$ , we see that $E_{c_{m}} \subseteq C_{m}$ . It follows that there is some $k \in [a, b]$ such that $f (k) \in S_{k}$ , and so that $f ↾ J_{k}$ agrees with $p_{k}$ on some input. As this happens for infinitely many m, we see that $f IOE p$ , as required. □

8. Forcing

The most common way to prove the consistency of a strict inequality $\begin{matrix} Card (A) < Card (B) \end{matrix}$ is to start with a model of CH, and iterate ( $ω_{2}$ many steps) a notion of forcing $P$ that adds a real in ${NL}^{V} (B)$ but no real in ${NL}^{V} (A)$ . That is, it adds some $b \in B_{inst}$ which is solved by no $\hat{b} \in V$ ; but every $a \in A_{inst} \cap V^{P}$ is solved by some $\hat{a} \in V$ . The standard argument is as follows. Let $⟨ P_{α} ⟩$ be the iteration. In $V^{P_{ω_{2}}}$ , $Card (A) = ℵ_{1}$ , because $V \cap A_{sol}$ solves all A-instances in $A_{inst} \cap V^{P_{ω_{2}}}$ ; no elements of ${NL}^{V} (A)$ were added during the iteration. On the other hand, in $V^{P_{ω_{2}}}$ , $Card (B) = ℵ_{2}$ . For suppose that $F \subset B_{sol}$ , $F \in V_{P_{ω_{2}}}$ , and $| F | < ℵ_{2}$ . Then there will be some $α < ω_{2}$ such that $F \subseteq V^{P_{α}}$ . At step $α + 1$ , then, we add a B-instance which has no solution in F.

Remark 8.1.
There are several reasons for using represented spaces (Definition 3.1). Here we see another one: the interpretation of a name may change between different models of set theory. Take for example the collection of names $M$ for $Σ_{2}^{0}$ meagre sets. If $V \subset W$ are transitive models of set theory, then $M$ is absolute: $M^{V} = M^{W} \cap V$ . However, likely for most $y \in M$ , the meagre set $M^{W} (y)$ named by y in W is strictly larger than the meagre set $M^{V} (y)$ named by y in V. When thinking of a problem such as $Pass (M)$ , we really mean the problem induced on the names rather than the meagre sets themselves: a $Pass (M)$ solution (in W) for all instances in V (a Cohen generic over V) is a $y \in ω^{ω}$ such that for all $x \in M^{V}$ , $y \notin M^{W} (x)$ , rather than $y \notin M^{V} (x)$ (which trivially holds for all $y \in W ∖ V$ ). It is also important that relations such as $Pass (M)$ and $Supset (M)$ are absolute.

The relationship between computability and set theory here is imprecise. In many cases, the notion of forcing $P$ itself is a represented space, and we can force with the computable elements of $P$ , and hope to get a real in $NL (B) ∖ NL (A)$ . In these cases, the failure of the implication $B \to A$ is witnessed at the computable level as well.
8.1. Basic examples

Cohen forcing is unusual in that it is the unique countable notion of forcing; all conditions are computable. A Cohen real does not make the collection of reals in the ground model meagre. And indeed, the argument is effective.

Lemma 8.2 (Rupprecht [39]).

A sufficiently Cohen generic real is not weakly meagre engulfing.

So a Cohen generic gives an oracle in $NL (Capture (M)) ∖ NL (Pass (M))$ , showing that $Capture (M) ↛ Pass (M)$ , effectively.

Proof.
Suppose that p is a condition that forces that $⟨ T_{n} ⟩$ is a sequence of uniformly partial computable functions from $2^{ω}$ to $2^{ω}$ , and that for each n, $T_{n} (g)$ is a nowhere dense tree. Thus, for each n and $σ \in 2^{< ω}$ , densely below p we can find conditions q and extensions $τ ≽ σ$ such that $T_{n} (q)$ declares that $τ \notin T_{n} (g)$ . Further, such pairs $(q, τ)$ can be found effectively. We can thus construct a computable point $x \in 2^{ω}$ by initial segments; at step $(r, n)$ , for some condition r extending p, we find q extending r and τ extending the initial segment of x we have so far such that $τ \notin T_{n} (r)$ . □
Remark 8.3.
The argument above is identical to the argument showing that the ground model reals in a Cohen extension are not meagre. In that argument we need to first prove a continuous reading of names, which tells us that every real in the extension is the image of the generic by a continuous function with code in the ground model. On the other hand, unlike the computability proof, in set theory we don’t need to worry about how effective is the search for $(q, τ)$ .

Proving that an $ω_{2}$ -iteration of Cohen over a model of CH gives a model of $non (M) < cov (M)$ requires an iteration theorem, which states that reals in ${NL}^{V} (Pass (M))$ are not added at limit steps of the iteration. In the Cohen case this is not too difficult, but with notions of forcing that are proper rather than c.c.c., such an iteration theorem may take some work. As we see, the corresponding argument in computability theory does not require such a result.

Figure 4 gives the dividing line for Cohen forcing in the Cichoń diagram.

Figure 4.
Cohen forcing and the Cichoń diagram. Cohen forcing adds a real in $NL (A)$ for all problems A on the right of the dividing line, but not for problems on its left. Similarly, an iteration of Cohen forcing will make the associated cardinals on the right large, and keep the cardinals on the left small.
Remark 8.4.
In the Cohen extension, the ground model reals are null. This is an immediate corollary of the morphism $Capture (M) \to Pass (N)$ , as it gives ${NL}^{V} (Capture (M)) \subseteq {NL}^{V} (Pass (N))$ .

The next simplest notion of forcing is perhaps random real forcing, one version of which is forcing with closed sets of positive measure. The conditions with computable names are the $Π_{1}^{0}$ classes with positive measure. Forcing with these does not give a generic for full random forcing; a sufficiently generic real will be weakly 2-random, but not 2-random. We do get a Schnorr random, i.e., an oracle in $NL (Capture (N))$ . A generic will also be computably dominated and will not be weakly null engulfing (Rupprecht [39, VI.35], based on the argument by Kunen [29] showing that in the random model, the ground model reals are not null.) This gives the diagram in Fig. 5.

Figure 5.
Random forcing and the Cichoń diagram; the forcing adds solutions (and increases cardinals) for problems above the dividing line.
8.2. Two step iterations

Before we proceed, we make a side remark on two step iterations.

Lemma 8.5.
Let A and B be absolute Weihrauch problems, and let $V \subseteq W \subseteq U$ be transitive models of set theory. If $x \in W \cap H^{V} (A)$ and $y \in U \cap H^{W} (B)$ , then $(x, y) \in H^{V} (A ⋆ B)$ .
Proof.
Let $(a, F)$ be an instance of $A ⋆ B$ . Then $a A x$ . Since F is coded in V, $F (x) \in W$ , and so $F (x) B y$ . □

So from the morphism $Pass (M) \to IOE ⋆ IOE$ we see that if we add an $IOE$ function g relative to V, and then an $IOE$ function relative to $V [g]$ , then in the second extension there must be a real Cohen over V.

Zapletal [48] showed that the iteration was necessary: he found a notion of forcing that adds an $IOE$ function without adding a Cohen real. His notion of forcing shows that $Pass (M) ↛ IOE$ , even when we consider non-computable definable morphisms, say Borel morphisms, for which the delicate argument of Lemma 4.22 does not apply.
8.3. Working relative to ideals

Sometimes, however, computability does not reveal the full picture. The most familiar example is the morphism $\begin{matrix} Capture (M) \to Dom, \end{matrix}$ which cannot be reversed. However, $NL (Capture (M)) = NL (Dom)$ : in the unusual direction, every hyperimmune degree computes a weakly 1-generic. This relies on a “time trick”, special to computability. Indeed, in set theory, it is possible to get an extension with a real in ${NL}^{V} (Dom)$ but none in ${NL}^{V} (Capture (M))$ , which after iterating gives the consistency of $cov (M) < d$ . One of the most straightforward notions is Miller forcing, also called rational perfect tree forcing. The conditions are trees $T \subseteq ω^{< ω}$ with no dead ends, no isolated paths, and in which every split is an infinite split: if $σ \in T$ and there is more than one $k < ω$ such that $σ \hat{} k \in T$ , then there are infinitely many such k. Extension is as is usual with most tree forcings: subset.

Denote this notion of forcing by $P$ . On one hand, it is not difficult to see that $P$ adds an escaping function: for every function f, for every condition $T \in P$ , we can refine the condtion by removing, for every splitting node $τ \in T$ , all extensions $τ \hat{} k$ for $k ⩽ f (| τ |)$ .

On the other hand, Miller forcing has the Laver tracing property, and so does not add a Cohen generic. Namely, for every order function h, for every function $f \in ω^{ω} \cap V^{P}$ which is bounded by some function in V, there is some h-Trace in V which traces f. Once one has continuous reading of names, we take a continuous function $Φ \in V$ and a condition T and perform a kind of fusion argument. First, by thinning, we may assume that if τ is a $n^{th}$ splitting node (it extends $k - 1$ many splitting nodes) then for every immediate extension $τ \hat{} k$ of τ on T, $Φ (τ \hat{} k, n) ↓$ . Next, we thin one splitting node at a time to obtain a trace. For example, if τ is the shortest splitting node (the stem of the tree) then we can force a single value for $Φ (g, 0)$ (g being the generic path): because $Φ (g)$ is V-bounded, say by some function $\tilde{h} \in V$ , we may assume that for every extension $τ \hat{} k$ of τ, the value $Φ (τ \hat{} k, 0)$ is smaller than $\tilde{h} (0)$ , in particular, only finitely many values appear; so one value appears infinitely often. We take one such value $a_{0}$ and remove all extensions $τ \hat{} k$ for which $Φ (τ \hat{} k, 0) \neq a_{0}$ . The $0^{th}$ element of our trace will be ${a_{0}}$ .

Next, consider the next level. Let $τ_{k}$ be the next splitting extension above $τ \hat{} k$ . For each k, some value $a_{k}$ appears as $Φ (τ_{k} \hat{} l, 1)$ for infinitely many l. Among the various k, one value a appears infinitely often. We remove from T all $τ \hat{} k$ such that $a_{k} \neq a$ , except possibly for the least such k – we will be “protecting” more and more successors of τ, so that after ω-many steps, infinitely many successors will remain. The next element of the trace is ${a, a_{k}}$ .

We see that the reason that this argument does not work computably is that even if T is computable, the construction of the thinned tree is not computable: it requires answers to the requests “give us a value that occurs infinitely often.” This can be done with the Turing jump of T. This shows that if we force with all arithmetic conditions, we will obtain a function escaping all arithmetic functions, which computes no arithmetically generic real. Indeed, even with the help of any arithmetic oracle, no such generic can be computed. Recall from Section 5 that we defined ${NL}^{r} (A)$ for reducibilities $⩽_{r}$ implied by Turing. If I is an ideal of Turing degrees then the reducibility $⩽_{I}$ (Turing modulo I) is defined by $x ⩽_{I} y$ if there is some $z \in I$ such that $x ⩽_{T} z \oplus y$ . We write ${NL}^{I} (A)$ for the corresponding non-lowness class. The argument above sketched the proof of the following:

Proposition 8.6.

If I is a jump ideal then ${NL}^{I} (Capture (M)) \neq {NL}^{I} (Dom)$ .

We remark that in [24], Kihara showed that Miller forcing has a sufficiently effective continuous reading of names, so that this inequality holds for relative hyperarithmetic reducibility as well. In contrast with Proposition 8.6, the argument that $NL (Capture (M)) = NL (Dom)$ applies to any ideal I which has a maximal degree of lowness for weak genericity reducibility. By relativising lowness for weak genericity, we see that these are the ideals in which both the DNR principle and the ESC principle (also named the HI principle) fail. That is, ideals I which contain a real z relative to which in I there is no DNR function, nor a function escaping all z-computable functions. On the other hand, Proposition 8.6 can be strengthened to apply to ideals I satisfying the $DNR (x^{'})$ principle: for every $x \in I$ there is $f \in I$ which is DNR relative to $x^{'}$ , even if $x^{'} \notin I$ . The reason is that if we are given a value $Φ (τ \hat{} k, n)$ which does not occur cofinitely often, we can thin to ensure that the generic does not compute an IOE function, that is, that the generic is in ${NL}^{I} (Dom) ∖ {NL}^{I} (AEDiff)$ ; and recall that $Capture (M) \to AEDiff \to Dom$ . The following question though remains open:

Question 8.7.

For which Turing ideals I is it the case that ${NL}^{I} (Capture (M)) \neq {NL}^{I} (Dom)$ ?

The same kind of question can be asked about the two other “collapses” in the computable Cichoń diagram: $\begin{matrix} NL (Spill (N)) = NL (Spill (M)) = NL (Esc), \end{matrix}$ namely: the high degrees coincide with the meagre engulfing and null engulfing degrees. Unlike the previous example, here it is known that the coincidences hold for relative hyperarithmetic reducibility. This is not the same though as Turing modulo $Δ_{1}^{1}$ , for which the question is still open. Hechler forcing and Laver forcing give separations in set theory. The associated constructions can be pushed in ideals which are models of arithmetic transfinite recursion ( ${ATR}_{0}$ ). Not much is known otherwise.

References

Andrews,

Cai,

Diamondstone,

Jockusch and

Lempp, Asymptotic density, computable traceability, and 1-randomness, Fund. Math.234(1) (2016), 41–53.

Bartoszyński and

Judah, Set Theory: On the Structure of the Real Line, A K Peters Ltd., Wellesley, MA, 1995.

Bartoszyński and

Shelah, Closed measure zero sets, Ann. Pure Appl. Logic58(2) (1992), 93–110. doi:10.1016/0168-0072(92)90001-G.

Blass, Reductions between cardinal characteristics of the continuum, in: Set Theory, Boise, ID, 1992–1994, Contemp. Math., Vol. 192, Amer. Math. Soc., Providence, RI, 1996, pp. 31–49. doi:10.1090/conm/192/02347.

Blass, Combinatorial cardinal characteristics of the continuum, in: Handbook of Set Theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 395–489. doi:10.1007/978-1-4020-5764-9_7.

Brattka, Computability and analysis, a historical approach, in: Pursuit of the Universal, Lecture Notes in Comput. Sci., Vol. 9709, Springer, Cham, 2016, pp. 45–57. doi:10.1007/978-3-319-40189-8_5.

Brattka,

Gherardi and

Marcone, The Bolzano–Weierstrass theorem is the jump of weak König’s lemma, Ann. Pure Appl. Logic163(6) (2012), 623–655. doi:10.1016/j.apal.2011.10.006.

Brendle,

Brooke-Taylor,

K.M.

Ng and

Nies, An analogy between cardinal characteristics and highness properties of oracles, in: Proceedings of the 13th Asian Logic Conference, World Sci. Publ., Hackensack, NJ, 2015, pp. 1–28.

Brendle and

Nies, Up to 2 · 2 · 2^ℵ₀ cardinal invariants, and their counterparts in computability theory, in: Logic Blog 2015, 2015, available at:http://arxiv.org/abs/1602.04432.

10.

C.T.

Chong,

Nies and

Yu, Lowness of higher randomness notions, Israel J. Math.166 (2008), 39–60. doi:10.1007/s11856-008-1019-9.

11.

Coskey,

Mátrai and

Steprāns, Borel Tukey morphisms and combinatorial cardinal invariants of the continuum, Fund. Math.223(1) (2013), 29–48. doi:10.4064/fm223-1-2.

12.

Denis ,

Hirschfeldt,

C.G.

JockuschJr.,

T.H.

McNicholl and

P.E.

Schupp, Asymptotic density and the coarse computability bound, Computability5(1) (2016), 13–27. doi:10.3233/COM-150035.

13.

A.M.

Donald, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math.12 (1966), 295–310. doi:10.1002/malq.19660120125.

14.

F.G.

Dorais,

D.D.

Dzhafarov,

J.L.

Hirst,

J.R.

Mileti and

Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc.368(2) (2016), 1321–1359. doi:10.1090/tran/6465.

15.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.

16.

D.H.

Fremlin, Real-valued-measurable cardinals, in: Set Theory of the Reals, Ramat Gan, 1991, Israel Math. Conf. Proc., Vol. 6, Bar-Ilan Univ., Ramat Gan, 1993, pp. 151–304.

17.

Gherardi and

Marcone, How incomputable is the separable Hahn–Banach theorem?, Notre Dame J. Form. Log.50(4) (2009), 393–425. doi:10.1215/00294527-2009-018.

18.

Goldstern and

Shelah, Many simple cardinal invariants, Arch. Math. Logic32(3) (1993), 203–221. doi:10.1007/BF01375552.

19.

Greenberg and

J.S.

Miller, Lowness for Kurtz randomness, J. Symbolic Logic74(2) (2009), 665–678. doi:10.2178/jsl/1243948333.

20.

Greenberg and

Monin, Higher randomness and genericity, Forum Math. Sigma5 (2017), e31, 41 pp.

21.

Greenberg and

Turetsky, Strong jump-traceability, Bulletin of Symbolic Logic, to appear.

22.

Kellner, Even more simple cardinal invariants, Arch. Math. Logic47(5) (2008), 503–515. doi:10.1007/s00153-008-0094-2.

23.

Kenshi, Truth-table Schnorr randomness and truth-table reducible randomness, MLQ Math. Log. Q.57(3) (2011), 323–338. doi:10.1002/malq.200910128.

24.

Kihara, Higher randomness and lim–sup forcing within and beyond hyperarithmetic, in: Sets and Computations, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., Vol. 33, World Sci. Publ., Hackensack, NJ, 2018, pp. 117–155. doi:10.1142/9789813223523_0006.

25.

Kjos-Hanssen,

Merkle and

Stephan, Kolmogorov complexity and the recursion theorem, in: STACS 2006, Lecture Notes in Comput. Sci., Vol. 3884, Springer, Berlin, 2006, pp. 149–161. doi:10.1007/11672142_11.

26.

Kjos-Hanssen,

Nies and

Stephan, Lowness for the class of Schnorr random reals, SIAM J. Comput.35(3) (2005), 647–657, (electronic). doi:10.1137/S0097539704446323.

27.

Kjos-Hanssen,

Nies,

Stephan and

Yu, Higher Kurtz randomness, Ann. Pure Appl. Logic161(10) (2010), 1280–1290. doi:10.1016/j.apal.2010.04.001.

28.

Kjos-Hanssen,

Stephan and

S.A.

Terwijn, Covering the recursive sets, Ann. Pure Appl. Logic168(4) (2017), 804–823. doi:10.1016/j.apal.2016.10.017.

29.

Kunen, Random and Cohen reals, in: Handbook of Set-Theoretic Topology, North-Holland, Amsterdam, 1984, pp. 887–911. doi:10.1016/B978-0-444-86580-9.50023-9.

30.

A.W.

Miller, Some properties of measure and category, Trans. Amer. Math. Soc.266(1) (1981), 93–114. doi:10.1090/S0002-9947-1981-0613787-2.

31.

Monin, An answer to the gamma question, in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, ACM, 2018, pp. 730–738.

32.

Monin and

Nies, A unifying approach to the Gamma question, in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 585–596. doi:10.1109/LICS.2015.60.

33.

Monin and

Nies, Muchnik degrees and cardinal characteristics, arXiv:1712.00864.

34.

Nies, Computability and Randomness, Oxford Logic Guides, Vol. 51, Oxford University Press, Oxford, 2009.

35.

Nies, Lowness, randomness, and computable analysis, in: Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday,

Dayet al., eds, Lecture Notes in Comput. Sci., Vol. 10010, Springer, 2017, pp. 738–754. doi:10.1007/978-3-319-50062-1_42.

36.

Osuga and

Kamo, Many different covering numbers of Yorioka’s ideals, Arch. Math. Logic53(1–2) (2014), 43–56. doi:10.1007/s00153-013-0354-7.

37.

Pawlikowski and

Recław, Parametrized Cichoń’s diagram and small sets, Fund. Math.147(2) (1995), 135–155.

38.

Raisonnier and

Stern, The strength of measurability hypotheses, Israel J. Math.50(4) (1985), 337–349. doi:10.1007/BF02759764.

39.

Rupprecht, Effective correspondents to cardinal characteristics in Cichoń’s diagram, PhD thesis, University of Michigan, 2010.

40.

Rupprecht, Relativized Schnorr tests with universal behavior, Arch. Math. Logic49(5) (2010), 555–570. doi:10.1007/s00153-010-0187-6.

41.

C.-P.

Schnorr, A unified approach to the definition of random sequences, Math. Systems Theory5 (1971), 246–258. doi:10.1007/BF01694181.

42.

Stephan and

Yu, Lowness for weakly 1-generic and Kurtz-random, in: Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci., Vol. 3959, Springer, Berlin, 2006, pp. 756–764. doi:10.1007/11750321_72.

43.

S.A.

Terwijn and

Zambella, Computational randomness and lowness, J. Symbolic Logic66(3) (2001), 1199–1205. doi:10.2307/2695101.

44.

Tomek, Additivity of measure implies additivity of category, Trans. Amer. Math. Soc.281(1) (1984), 209–213. doi:10.1090/S0002-9947-1984-0719666-7.

45.

Tomek, Combinatorial aspects of measure and category, Fund. Math.127(3) (1987), 225–239. doi:10.4064/fm-127-3-225-239.

46.

Vojtáš, Topological cardinal invariants and the Galois–Tukey category, in: Recent Developments of General Topology and Its Applications, Berlin, 1992, Math. Res., Vol. 67, Akademie-Verlag, Berlin, 1992, pp. 309–314.

47.

Weihrauch, Computable Analysis: An Introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.

48.

Zapletal, Dimension theory and forcing, Topology Appl., 167 (2014), 31–35.

Cardinal invariants,non-lowness classes,and Weihrauch reducibility

Abstract

Keywords

1. Introduction

2. Basics

2.1. Weihrauch problems and effective morphisms

7 Terminology by Schnorr [41].

Corollary 3.16 (Rupprecht [39,40]).

Corollary 3.17 (Terwijn and Zambella [43]).

3.6. Reducing category to measure

4.1. Sequential composition

Lemma 4.8. ⇢ is transitive, andis an equivalence relation. If A ⇢ B then Card ( A ) ⩽ Card ( B ) and Card ( A ⊥ ) ⩾ Card ( B ⊥ ) . If A ⇢ B then NL ( A ) ⊆ NL ( B ) . 4.3. An example: Supset ( M )

Theorem 5.3 (Greenberg, Monin [20]).

6. Addition, multiplication, and the Γ question

6.1. Addition and multiplication

The main map

Infinitely often closeness

Bounded traces

Theorem 7.1. . As a result we get: Theorem 7.2 (Bartoszynski, Shelah [3]).

Theorem 7.3. A degree is low for Σ 2 0 null sets if and only if it is hyperimmune-free and not DNR. 7.1. Lowness for Kurtz tests and randomness

Theorem 7.7 (Kjos-Hanssen, Nies, Stephan, Yu [27]).

7.2. Revising the problem

Proposition 7.8. . As a result, we obtain: Theorem 7.9 (Greenberg, J. Miller [19]).

Proof of Proposition 7.8. By Proposition 7.13, Supset ( E , N ) → IOE . In the other direction, we have IOE → Supset ( E , N ) ⋆ Esc and Esc → Supset ( E , N ) , so IOE → Supset ( E , N ) ⋆ 2 . □ 7.4. A self-contained argument

Lemma 7.17 (With Harrison-Trainor).

Lemma 8.2 (Rupprecht [39]).

References

⁷
Terminology by Schnorr [41].

Lemma 4.8.

⇢ is transitive, andis an equivalence relation.

If $A ⇢ B$ then $Card (A) ⩽ Card (B)$ and $Card (A^{⊥}) ⩾ Card (B^{⊥})$ .

If $A ⇢ B$ then $NL (A) \subseteq NL (B)$ .

4.3. An example: $Supset (M)$

Theorem 7.1.
.

As a result we get:
Theorem 7.2 (Bartoszynski, Shelah [3]).

Theorem 7.3.
A degree is low for $Σ_{2}^{0}$ null sets if and only if it is hyperimmune-free and not DNR.

7.1. Lowness for Kurtz tests and randomness

Proposition 7.8.
.

As a result, we obtain:
Theorem 7.9 (Greenberg, J. Miller [19]).

Proof of Proposition 7.8.
By Proposition 7.13, $Supset (E, N) \to IOE$ . In the other direction, we have $IOE \to Supset (E, N) ⋆ Esc$ and $Esc \to Supset (E, N)$ , so $IOE \to Supset {(E, N)}^{⋆ 2}$ . □

7.4. A self-contained argument