1 Introduction
We would like to compare the computational power of algebraic structures. For countable structures, Muchnik reducibility provides a useful way to do this: if
$\mathcal {A}$
and
$\mathcal {B}$
are countable structures (in computable languages), then
$\mathcal {A}$
is Muchnik reducible to
$\mathcal {B}$
(
$\mathcal {A}\leq _w \mathcal {B}$
) provided that every copy of
$\mathcal {B}$
computes a copy of
$\mathcal {A}$
. Schweber, in [Reference Knight, Montalbán and Schweber9], introduced a generalization of this reducibility that allows us to compare the computational power of structures of arbitrary cardinality.
Definition 1.1 (Generic Muchnik reducibility).
For a pair of structures
$\mathcal {A}$
and
$\mathcal {B}$
(not necessarily countable) in V, we say that
$\mathcal {A}$
is generically Muchnik reducible to
$\mathcal {B}$
, and we write
$\mathcal {A} \leq _w^* \mathcal {B}$
, if for any generic extension
$V[G]$
of the set-theoretic universe V in which both structures are countable, we have
$V[G] \models \mathcal {A} \leq _w \mathcal {B}$
.
In other words, we collapse cardinals so that the structures
$\mathcal {A}$
and
$\mathcal {B}$
become countable, and then we apply the standard tools of computability theory to study them. It follows from Shoenfield’s absoluteness theorem [Reference Shoenfield18] that generic Muchnik reducibility is set-theoretically robust:
Lemma 1.2 (Schweber [Reference Knight, Montalbán and Schweber9]).
If
$\mathcal {A}\leq _w^* \mathcal {B}$
, then
$\mathcal {A}\leq _w \mathcal {B}$
in every forcing extension that makes
$\mathcal {A}$
and
$\mathcal {B}$
countable.
After the initial paper [Reference Knight, Montalbán and Schweber9], there have been several further papers in which generic Muchnik reducibility is used to compare the computational power of structures related to the real numbers. Here are some of these structures.
-
• Cantor space: This is represented in [Reference Knight, Montalbán and Schweber9] by
$\mathcal {W} = (\mathcal {P}(\omega )\cup \omega ,\mathcal {P}(\omega ),\omega ,S,\in )$
, where S is the successor function on
$\omega $
. Another representation, possibly more natural, is
$\mathcal {C} = (2^\omega ,(R_n)_{n\in \omega })$
, where for
$\alpha \in 2^\omega $
,
$\alpha \in R_n$
if and only if
$\alpha (n) = 1$
. Clearly,
$\mathcal {W}\equiv _w^*\mathcal {C}$
. -
• The ordered field of reals: This is
$\mathcal {R} = (\mathbb {R}, +,\times , <)$
. -
• The non-standard reals:
$\mathcal {R}^*$
is an
$\omega $
-saturated extension of
$\mathcal {R}$
. Note that this structure is not unique, although it becomes unique after collapse of cardinals. -
• Baire space: This is the structure
$\mathcal {B} = (\omega ^\omega ,(R_{n,m})_{n,m\in \omega })$
, where
$f\in R_{n,m}$
if and only if
$f(n) = m$
.
The structures listed above all fall into one of two generic Muchnik degrees. In [Reference Knight, Montalbán and Schweber9], it is shown that
$\mathcal {W}\leq _w^*\mathcal {R}$
. Igusa and Knight [Reference Igusa and Knight6] showed, using a result of MacIntyre and Marker [Reference MacIntyre and Marker11], that
$\mathcal {R}^*\equiv _w^*\mathcal {W}$
. Downey, Greenberg, and Miller [Reference Downey, Greenberg and Miller3] showed that
$\mathcal {R}\equiv _w^*\mathcal {B}$
. Thus, we have that
$$\begin{align*}\mathcal{C} \equiv^*_w \mathcal{W} \equiv^*_w \mathcal{R}^* \leq^*_w \mathcal{R} \equiv^*_w \mathcal{B}.\end{align*}$$
Finally, we know from [Reference Downey, Greenberg and Miller3, Reference Igusa and Knight6] that the above inequality
$\leq ^*_w$
is strict, so
$$\begin{align*}\mathcal{C} \equiv^*_w \mathcal{W} \equiv^*_w \mathcal{R}^* <^*_w \mathcal{R} \equiv^*_w \mathcal{B}.\end{align*}$$
In the present paper, we investigate structures of the form
$\mathcal {R}_f = (\mathcal {R},f)$
, the ordered field of reals expanded by a function f. Igusa, Knight, and Schweber [Reference Igusa, Knight and Schweber7] showed that if f is analytic, then
$\mathcal {R}_f \equiv _w^*\mathcal {R}$
. They asked whether this remains true for arbitrary continuous functions f. They believed that the answer should be negative, witnessed possibly by something like Brownian motion, with complicated level sets as studied in [Reference Allen, Bienvenu and Slaman1]. Here, we show that the answer to the question is actually positive.
Theorem 1.3. If f is a continuous function (of any arity) on
$\mathcal {R}$
, then
$\mathcal {R}_f\leq _w^*\mathcal {R}$
.
Below, we give a brief outline of the proof of Theorem 1.3. Recall that for a countable family of sets
$S\subseteq \mathcal {P}(\omega )$
, an enumeration is a relation
$E\subseteq \omega ^2$
such that the sets
$E_n = \{x:(n,x)\in E\}$
are exactly those in S. For a countable family of functions
$F\subseteq \omega ^\omega $
, an enumeration is a function
$P:\omega ^2\rightarrow \omega $
such that the functions
$P_n(x) = P(n,x)$
are exactly those in F.
Definition 1.4 (Turing ideal, jump ideal).
-
(1) A Turing ideal is a family of sets
$S\subseteq \mathcal {P}(\omega )$
that is closed under disjoint union and Turing reducibility. -
(2) A jump ideal is a Turing ideal that is closed under Turing jump.
After collapse, the old
$\mathcal {P}(\omega )$
becomes a countable jump ideal S, and the family F of functions
$f\in \omega ^\omega $
that are present in the old
$\omega ^\omega $
is the family of functions computable from elements of S. Downey, Greenberg, and Miller [Reference Downey, Greenberg and Miller3] give an important characterization of the two generic Muchnik degrees discussed above, that of
$\mathcal {C}$
and that of
$\mathcal {R}$
. After collapse, computing a copy of
$\mathcal {C}$
is equivalent to computing an enumeration of S, while computing a copy of
$\mathcal {R}$
is equivalent to computing an enumeration of F. The first step in the proof of our main theorem is to explore what computational power is given by an enumeration of F, but not given by an enumeration of S.
Let S be a countable jump ideal, and let E be an enumeration of S. We may think of E as a function taking each index n to the set
$E_n$
. We consider the companion function J taking n to the set
$(E_0\oplus \cdots \oplus E_n)'$
. More formally, J will be an enumeration of a subfamily of S, with specified indices.
Definition 1.5 (Running jump).
Let E be an enumeration of a jump ideal S. The running jump for E is the relation
$J\subseteq \omega ^2$
such that
$(n,x)\in J$
if and only if
$x\in (E_0\oplus \cdots \oplus E_n)'$
.
In Section 2, we prove the following result, which we believe is of independent interest.
Theorem 1.6. Let
$S\subseteq \mathcal {P}(\omega )$
be a countable jump ideal, and let
$F\subseteq \omega ^\omega $
be the family of all functions computable from sets in S. From an arbitrary enumeration P of F, we can compute an enumeration E of S together with the running jump for E.
After collapse, let S be the family of sets in the old
$\mathcal {P}(\omega )$
, and let
$F\subseteq \omega ^\omega $
be the family of functions computable from sets in S. From a copy of
$\mathcal {R}$
(now a countable structure), we can compute an enumeration P of F (this is immediate from the fact that
$\mathcal {R}\equiv _w^* \mathcal {B}$
). Applying Theorem 1.6, we get an enumeration E of S together with the running jump J for E. In Section 3, we show that the combination of E and the running jump J provides the information needed to build a copy of
$\mathcal {R}_f$
.
Theorem 1.7. Suppose
$f:\mathcal {R}^k\rightarrow \mathcal {R}$
is continuous. After collapse, let E be an enumeration of the sets in the old
$\mathcal {P}(\omega )$
, let J be the running jump for E, and let
$\mathcal {R}_f = (\mathcal {R},f)$
. Then there is a copy of
$\mathcal {R}_f$
computable from
$E\oplus J$
.
We further show that continuous expansions of Cantor space also have generic Muchnik degree bounded by the degree of
$\mathcal {R}$
. Denote by
$\mathcal {C}_f$
the expansion of
$\mathcal {C}$
by a function f on Cantor space. The following is a direct consequence of the more generally phrased Theorem 3.2.
Theorem 1.8. If f is a continuous function (of any arity) on
$\mathcal {C}$
, then
$\mathcal {C}_f\leq _w^*\mathcal {R}$
.
In Section 3, we also give examples of continuous functions f such that
$\mathcal {C}_f\equiv _w^*\mathcal {R}$
. An interesting question arises: are there generic Muchnik degrees strictly between the degree of
$\mathcal {C}$
and the degree of
$\mathcal {R}$
and if so, can they be obtained as continuous expansions of
$\mathcal {C}$
? This problem is treated in detail in the upcoming paper by Andrews, Miller, Schweber, and M. Soskova [Reference Andrews, Miller, Schweber and Soskova2]. They show that there is a degree strictly between
$\mathcal {C}$
and
$\mathcal {R}$
. Later GuraFootnote
1
exhibited a whole hierarchy of such degrees. On the other hand, Andrews, Miller, Schweber, and M. Soskova [Reference Andrews, Miller, Schweber and Soskova2] show a dichotomy result for expansions of
$\mathcal {C}$
by closed predicates: they lie either in the degree of
$\mathcal {C}$
or in the degree of
$\mathcal {R}$
. Recall that continuous functions have closed graphs, and hence this answers our original questions.
In Section 4, we investigate continuous expansions of Baire space
$\mathcal {B}$
. We show that, unlike with
$\mathcal {R}$
, there is a way to continuously expand
$\mathcal {B}$
to get a structure of strictly higher complexity. Let
$(\mathcal {B}, \oplus , ')$
be the structure of Baire space with adjoined join and jump functions (appropriately defined for members of
$\omega ^{\omega }$
). We show that this structure has a very powerful generic Muchnik degree.
Theorem 1.9. There is a continuous expansion of Baire space in the generic Muchnik degree of
$(\mathcal {B}, \oplus , ')$
.
-
(1)
$(\mathcal {B}, \oplus , ')>^*_w \mathcal {B}$
. -
(2) Every Borel expansion (even Borel quotient) of
$\mathcal {B}$
is generic Muchnik reducible to
$(\mathcal {B}, \oplus , ')$
.
We refer to the generic Muchnik degree of the structure
$(\mathcal {B}, \oplus , ')$
as the Borel complete degree. In Section 4, we show that as a consequence of this, Theorem 1.3 cannot be strengthened to Borel expansions of
$\mathcal {R}$
—there are such expansions of
$\mathcal {R}$
in the Borel complete degree. As with
$\mathcal {C}$
, it is natural to ask if continuous expansions of
$\mathcal {B}$
can lie strictly between
$\mathcal {B}$
and the Borel complete degree. Assuming
$\mathbf {\Delta ^1_2}$
-Wadge determinacy, Andrews, Miller, Schweber, and M. Soskova [Reference Andrews, Miller, Schweber and Soskova2] prove a dichotomy result for closed (equivalently, continuous) expansions of
$\mathcal {B}$
: they have the same generic Muchnik degree either as
$\mathcal {B}$
or as the Borel complete degree. They also show that there are generic Muchnik degrees strictly between these two.
2 Results on enumerations
We turn to the proof of Theorem 1.6. Recall the statement.
Theorem 1.6. Let
$S\subseteq \mathcal {P}(\omega )$
be a countable jump ideal, and let
$F\subseteq \omega ^\omega $
be the family of functions computable from sets in S. From an arbitrary enumeration P of F, we can compute an enumeration E of S together with the running jump for E.
Proof We will compute an enumeration E in stages, so that at any stage we have determined finitely many bits of E. At stage s, we will have instructions for each column
$E_n$
with
$n<s$
. These instructions either will be to copy some element of P (or rather a set associated with that element in a fixed way that will be made precise) or will be an index for a computation that describes how we should complete the column. In the former case, we will say that n is a copy column and in the latter case, we will say that n is a fix column.
The difficulty in the construction, of course, comes from computing the relation J that gives us the running jump for E. The core idea is that the jump ideal contains sets computing the settling time functions for the running jumps. Recall that
$A'$
has a standard representation as an A-c.e. set
$W^A$
. A settling time function for
$A'$
is a function
$s\colon \omega \rightarrow \omega $
such that
$n\in A'$
if and only if
$n\in W_{s(n)}^{A\upharpoonright s(n)}$
, i.e., n is the stage
$s(n)$
approximation to the set
$W^A$
and references the oracle A only on numbers less than n. If a jump ideal S contains A, then the least (with respect to majorizing) settling time function
$s_{A'}$
is computable from
$A'$
, and hence it is in F. To define
$J_i$
, we make an initial guess towards a P-index for a settling time function of
$(E_0 \oplus \dots \oplus E_i)'$
: we guess that
$P_0$
is such a function. We then try to compute
$(E_0 \oplus \dots \oplus E_i)'$
using our current guess of that function and the columns
$E_0, \dots , E_i$
. If the guess is incorrect, we will notice this after a finite amount of time. We will see that the settling time function predicted that some natural number
$x\notin (E_0 \oplus \dots \oplus E_i)'$
, but now, after computing more steps than our guess assured us would be enough, we see that
$x\in (E_0 \oplus \dots \oplus E_i)'$
. At that point, we would like to revise our guess at the settling time function by moving to the next possible function in our enumeration P of F, until we eventually hit the right one.
We need a way to deal with the injury that happens when we discover that our guess is incorrect. We will have already specified finitely many bits of E, and of J. We have already announced that
$x\notin (E_0 \oplus \dots \oplus E_i)'$
, misled by the wrong guess. This means that our assignment of copy columns and fix columns is no longer consistent with J being the running jump of E. To remedy this problem, we ensure during the construction that there is always a way to extend
$E_i$
that is compatible with
$J_i$
and that we can compute such an extension. To achieve this, we use the Low Basis Theorem by Jockusch and Soare [Reference Jockusch and Soare8]. We state it here in a relativized, uniform manner.
Theorem 2.1 (The Low Basis Theorem).
Let
$T\subseteq 2^{<\omega }$
be an infinite X-computable tree. There is an infinite path Y through T such that
$(X\oplus Y)'\leq _T X'$
. Moreover, an index for this reduction can be obtained uniformly in an index from the reduction witnessing that
$T\leq _T X$
.
As a result, J will remain correct. The trade-off is that this action interferes with the requirement that E is an enumeration of S. In particular, we will have to turn more columns into fix columns (whose role is simply to be filled in and keep J consistent). Indeed, as a copy column,
$E_n$
was trying to enumerate some element X of S, but after injury, we abandon this goal and instead let
$E_n$
fill in its column in a way that preserves J. Our only option is to enumerate X at position
$E_j$
for some fresh j.
The approach described above ensures that we compute J correctly, and that if every requirement copying some element X of S is injured only finitely often, then E is an enumeration of S. Intuitively, the injury should only happen finitely often because we eventually find the right settling time function. However, there is a complication. Let us fix a set X and assume that all higher priority requirements are no longer injured after stage s. At stage s, we find out that our guess towards the settling time function for
$(E_0 \oplus \dots \oplus E_i)'$
is incompatible with our assignment of
$E_i$
as a copy column and transition to the escape strategy explained above. We let
$E_i$
,
$E_{i+1}, \dots , E_{j-1}$
be fix columns and we begin filling them in with sets that are low with respect to previous columns, i.e.,
$E_{i+k}$
is low over
$E_0\oplus \dots \oplus E_{i+k-1}$
. Note that this will make it easy to fill in the columns
$J_{i}, \dots , J_{j-1}$
as
$(E_0\oplus \dots \oplus E_{i+k})'$
will be computable from
$(E_0\oplus \dots \oplus E_{i-1})'$
. We start copying X at position
$j> i$
, where j is a column for which we have not yet defined any values. We now need to guess at the settling time function for
$(E_0 \oplus \dots \oplus E_{j-1}\oplus X)'$
. This settling time function could be vastly different from the one for
$(E_0 \oplus \dots \oplus E_{i-1}\oplus X)'$
. Indeed, even though we were able to select the fix columns so that we can control the corresponding running jump columns, we cannot even guarantee that
$E_0\oplus \cdots \oplus E_{i-1}\oplus X \equiv _T E_0\oplus \dots \oplus E_{j-1}\oplus X$
. An easy counterexample can be derived from the existence of two low sets whose join is
$\emptyset '$
: it could be that both X and
$E_{i}\oplus \dots \oplus E_{j-1}$
are low over
$E_0\oplus \dots \oplus E_{i-1}$
but
$(E_0\oplus \dots \oplus E_{j-1}\oplus X)' \equiv _T (E_0\oplus \dots \oplus E_{i-1}\oplus X)"$
. Thus, there is no guarantee that we ever guess the settling time function correctly.
Luckily, there is an easy fix for this problem. Instead of guessing at the settling time function for
$(E_0 \oplus \dots \oplus E_{i-1}\oplus X)'$
and then for
$(E_0 \oplus \dots \oplus E_{j-1}\oplus X)'$
after the first injury, as we were previously doing, we will guess at a function that encodes the settling time function for all possible situations that we might end up in. More precisely, we guess at a function g with the property that if
$\Phi _e(((E_0 \oplus \dots \oplus E_{i-1})' \oplus X)') {\downarrow }= Z'$
for some set Z, then the e-th column
$g^{[e]}$
of g is the settling time function for
$Z'$
. Since the Low Basis Theorem is uniform, we will know an index e such that
$\Phi _e(((E_0 \oplus \dots \oplus E_{i-1})' \oplus X)') = (E_0 \oplus \dots \oplus E_{j-1}\oplus X)'$
. If our current guess towards g is
$\tilde {g}$
, we modify the construction to use
$\tilde {g}^{[e]}$
as the current guess at the settling time function, and if it turns out that
$\tilde {g}^{[e]}$
is incorrect, then we give up on
$\tilde {g}$
completely and move on to the next guess for g.
Construction. Our requirements are as follows. We have an ambient requirement:
-
• Q: for all
$x,i \in \omega $
,
$x \in J_i$
if and only if
$x \in (E_0 \oplus \dots \oplus E_i)'$
,
and we have countably many copy requirements:
-
•
$R_i$
: for every
$i \in \omega $
there exists a
$j \in \omega $
such that
$E_j = \hat {P}_i = \{n : P_i(n) = 1\}$
.
The ambient requirement Q will not be subject to injury, and the requirements
$R_i$
are given a priority order of order type
$\omega $
.
The construction will proceed in stages. At stage s, we will construct
$E[s]$
and
$J[s]$
such that, ultimately,
$E = \bigcup _{s<\omega } E[s]$
and
$J = \bigcup _{s<\omega } J[s]$
. We will omit
$[s]$
in the construction; unless explicitly mentioned, all objects being constructed are evaluated at the current stage.
For every
$i \in \omega $
, we have a module
$M_i$
that is building
$J_i$
and a module
$N_i$
that is building
$E_i$
. They share two parameters:
$q_i \in \omega \cup \{\mathrm{fix}\}$
and
$c_i\in \omega $
. If
$q_i\in \omega $
, then we are in the case that i is currently a copy column; our current guess for the function g described above is
$P_{q_i}$
, and
$c_i$
indicates that
$M_i$
is currently copying
$\hat {P}_{c_i}$
. If
$q_i = \mathrm{fix}$
, then we are in the case that
$E_i$
is a fix column and
$c_i$
is an index for a computation; we will endeavor to make
$(E_0\oplus \cdots \oplus E_i)'=\Phi _{c_i}((E_0\oplus \cdots \oplus E_{i-1})')$
. At any stage, let
$m_i < i$
be greatest such that
$q_{m_i}\neq \mathrm{fix}$
. If there is no such natural number
${m_i}$
, then we let
${m_i} = -1$
, and we let
$J_{-1} = \emptyset '$
. We have access to
$\emptyset '$
, having fixed an index for it in the enumeration P. Then by composing the computations
$\Phi _{c_{m_i+1}}$
through
$\Phi _{c_i}$
, we see how we intend to compute
$J_i$
from
$J_{m_i}$
, baring further injury.
At stage s, we attempt to determine the value of
$J(m)$
for every
$m=\langle i,j \rangle $
with
$i\leq s$
and
$j\leq s$
. We first call
$M_0$
on input x for every
$x\leq s$
, then
$M_1$
on input x for every
$x\leq s$
and so forth.
The M-module. We describe the module
$M_i$
on input x, that is, we describe how we determine the value of
$J_i(x)$
. Whenever we call the module
$M_i$
on input x, we first recursively call
$M_{i-1}$
on every input
$\leq x$
. (Note that both N and M modules may call an M module on numbers larger than s, so this instruction is not redundant. It ensures that if there is a mistake in our guess at an earlier column, then that mistake gets discovered. This will ultimately allow us to prove that every stage of the construction terminates in finite time.) If
$J_i(x)$
is already defined, we do nothing further. Otherwise, we have two cases to consider:
Case 1. Suppose that
$q_i \in \omega $
. That is, the i-th column is currently a copy column. Then using the indices
$c_k$
for
$k\in (m_i,i)$
, we can find a computation which (assuming no injury) will describe the columns
$E_{m_i+1},\ldots , E_{i-1}$
from
$(E_0\oplus \cdots \oplus E_{m_i})'$
, which (again assuming no injury) equals
$J_{m_i}$
. Thus we can find an index e so that (again assuming no injury) we will have
$(E_0\oplus \cdots \oplus E_i)'=\Phi _e((J_{m_i}\oplus E_i)')$
. We then let
$t=P_{q_i}(\langle e, x\rangle )$
. If the requirement’s guess is correct about
$q_i$
, then this t bounds the settling time function for
$(E_0\oplus \cdots \oplus E_i)'$
at x. We thus call the modules
$N_k$
on input
$x'$
for each
$k\leq i$
and
$x'\leq t$
. Once these all return, we will know the values of
$E_k(x')$
for each
$k\leq i$
and
$x'\leq t$
. We then run the enumeration of
$(E_0\oplus \cdots \oplus E_i)'$
(as a set c.e. in
$E_0\oplus \cdots \oplus E_i$
) for t stages to see if it enumerates x in this time. This determines whether we want to set
$J_i(x)$
to be
$0$
or
$1$
. We are almost ready to declare that
$J_i(x)$
is this value, but before we can do this, we have to ask permission of every previous column; we will describe the process of asking for permission below. If they all give permission, then we declare
$J_i(x)$
to be the value determined above.
Case 2. Suppose that
$q_i = \mathrm{fix}$
. Then the i-th column is a fix column, and
$c_i$
gives a parameter for a computation of
$J_i$
from
$J_{i-1}$
. Thus, we simply call
$M_{i-1}$
for every x for which
$J_{i-1}$
is undefined until we see a computation giving
$\Phi _{c_i}^{{J}_{i-1}}(x)\downarrow $
. Define a computable increasing function
$\alpha $
so that for all sets
$A,B$
, we have
$z\in B$
if and only if
$\alpha (z)\in (A\oplus B)'$
. We say that x is a coding number if and only if
$x=\alpha (z)$
for some z. Note that if
$x= \alpha (z)$
is a coding number for z then whether x enters
$(A\oplus B)'$
when this set is enumerated computably in
$A\oplus B$
will depend solely on whether
$z\in B$
. If
$\Phi _{c_i}^{{J}_{i-1}}(x)=0$
, we ask for permission from every previous column to make
${J}_i(x)=0$
. If
$\Phi _{c_i}^{{J}_{i-1}}(x)=1$
and
$x=\alpha (z)$
is a coding number, then we ask for permission to set
$E_i(z)=1$
and
$J_i(x)=1$
. If
$\Phi _{c_i}^{{J}_{i-1}}(x)=1$
and x is not a coding number, then we search for a confirmation set. This means that we call the modules
$N_0, \dots , N_i$
on increasing inputs until we have assigned enough of
$E_0\oplus \dots \oplus E_i$
so that the previous columns give permission to define
$J_i(x)$
to be 1.
The N-module. We now describe the modules
$N_i$
on input z. Our goal is to determine whether
$E_i(z)$
is 0 or 1.
Case 1. Suppose that
$q_i\in \omega $
. Then the goal of
$E_i$
is to copy
$\hat {P}_{c_i}$
. We ask permission to set
$E_i(z)=\hat {P}_i(z)$
and do so if every previous column gives permission.
Case 2.
$E_i$
is a fix column. Call
$M_i(\alpha (z))$
. If this assigns
$J_i(\alpha (z))=0$
, then assign
$E_i(z)=0$
. (The fact that previous columns gave permission to assign
$J_i(\alpha (z)) = 0$
will imply that they also give permission to make
$E_i(z) = 0$
.) Note that if
$M_i(\alpha (z))$
assigns
$J_i(\alpha (z))=1$
, then it also assigns
$E_i(z)=1$
.
Permissions. We now describe the process of asking for permission from previous columns. We either want to assign
$J_i(x)$
for some i and x, or
$E_i(z)$
for some i and z (or both) and we need permission from each previous column. Let m be the largest so that
$q_m$
is defined. We describe how the k-th column determines whether to give permission. Let
$\sigma _{k+1},\ldots , \sigma _{m}$
be the fragments of
$E_{k+1},\ldots , E_{m}$
determined so far including the requested assignment, and let
$\tau _{k+1},\ldots ,\tau _m$
be the fragments of
$J_{k+1},\ldots ,J_m$
determined so far including the requested assignment.
Let T be the tree of possible ways to complete
$\sigma _{k+1},\ldots ,\sigma _m$
so that for every
$j,x$
with
$j\in (k,m]$
and
$\tau _j(x)=0$
, we do not put x into the running jump. The k-th column wants to give permission if and only if:
-
• For every pair
$j,x$
with
$j\in (k,m]$
and
$\tau _j(x)=1$
,
$x\in (E_0\oplus \cdots \oplus E_k \oplus \sigma _{k+1}\oplus \cdots \oplus \sigma _j)'$
. Here
$E_0,\dots , E_k$
are not just the partial fragments determined so far, rather they are the sets as they would be determined assuming all our guesses are correct. In other words, over the first k columns, the
$\sigma $
’s have enough information already encoded to put x into the correct running jump. -
• T has an infinite path.
Note that these two conditions are true if and only if two bits in the set
$(E_0\oplus \cdots \oplus E_k)'$
have fixed specific values—the first condition is equivalent to a fixed bit being 1 and the second to a fixed bit being
$0$
. Thus, in order to determine whether or not to give permission, we call the module
$M_k$
on these bits. If these modules both return the correct value confirming the condition, then we give permission. Otherwise, if the first condition is incorrect (the module returns 0 to show that the first condition fails), then we simply deny permission but do not declare injury.
If the module returns a value signifying that T does not have a path, then we declare injury which means that for all
$j\in [i,m]$
, we set
$q_j$
to be
$\mathrm{fix}$
. Let S be the tree of possible ways to complete the columns
$E_i,\ldots , E_m$
so that for every
$j,x$
with
$j\in (k,m]$
and
$J_j(x)=0$
, we do not put x into the running jump. Since the
$(i-1)$
st column gave permission to the current configuration, there is some y such that
$J_{i-1}(y)=0$
and this confirms that S has a path. Thus, by the effectiveness of the Low Basis Theorem, we can set
$c_i,\ldots ,c_m$
to be so that there is some path through S so which would make
$\Phi _{c_j}^{J_{j-1}}=J_j$
for each
$j\in [i,m]$
. We then complete the stage (though we may have not succeeded in the goal of assigning any value of J).
Lastly, whether we declared injury or not during the stage, before finishing the stage, we take the least m so that
$q_m$
is undefined and the least i so that currently no column has
$c_j=i$
and define
$c_m$
to be i. If this is the l-th time that we define some
$c_j$
to be i since we last assigned some
$c_{j'}$
to be
$i-1$
, then we assign
$q_j$
to be l. This completes the construction.
Verification. We say that the i-th column is correct at stage s if for all
$j\leq i$
, the parameters
$q_j$
and
$c_j$
will never be changed at a stage
$t>s$
.
Lemma 2.2. Suppose that the i-th column is correct at stage s. Define the sets
$A_j, B_j$
for
$j\leq i$
inductively as follows:
$A_{-1}=\emptyset $
and
$B_{-1}=\emptyset '$
. If the j-th column has parameters
$q_j,c_j$
with
$q_j=\mathrm{fix}$
, then define
$B_j$
as
$\Phi _{c_j}(B_{j-1})$
. Define
$z\in A_j$
if and only if
$\alpha (z)\in B_j$
. If
$q_j\in \omega $
, then define
$A_j=\hat {P}_{c_j}$
and
$B_j=(A_0\oplus \cdots \oplus A_j)'$
. Then for each
$j\leq i$
,
$E_j=A_j$
and
$J_j=B_j$
. In particular,
$J_j=(E_0\oplus \cdots \oplus E_j)'$
.
Proof We prove the result by induction on j. It is clearly true for
$j=-1$
. If
$q_j=\mathrm{fix}$
, then since
$J_{j-1}=B_{j-1}=(A_0\oplus \cdots \oplus A_{j-1})'$
, it follows that when we determined the final value of the parameter
$c_j$
, we were looking at a tree S that was accurately determined by previous columns (which do not get injured again or else
$c_j$
would be modified) to be infinite. Thus, by the Low Basis Theorem, S has an infinite low path and the sequence of Turing functionals we determined, one of which is
$\Phi _{c_j}$
, is correct. Note that when we ask for permission to define
$J_j(x)$
or
$E_j(z)$
, it cannot end in injury by our assumption that the j-th column is already correct. When we run the
$N_j$
module on z, if we want to make
$E_j(z) = 1$
, then that permission will be given because changing a bit in E cannot result in a failure of the permission for the first reason (i.e., it can only cause injury). If we want to make
$E_j(z) = 0$
, then we do not even ask for permission. When we run the
$M_j$
module on x,
$\Phi _{c_j}$
will eventually converge on x. If
$M_j$
wants to define
$J_j(x) = 0$
, it will be given permission (or else j is not correct). If
$M_j$
wants to make
$J_j(x) = 1$
and
$x = \alpha (z)$
then we will get permission to enumerate z in
$E_j$
and that is all we need as a confirmation set, and hence
$M_j$
will be granted permission to define
$J_j(x)$
. If x is not a coding number then we are assured that eventually we will find a confirmation set by the correctness of
$\Phi _{c_j}$
and all previous columns and the fact that
$N_j$
always gets permission to define
$E_j$
, as we just argued. Thus, we will build
$E_j = A_j$
and
$J_j = B_j$
for some sets
$A_j$
and
$B_j$
so that
$(A_0\oplus \cdots \oplus A_j)'=B_j$
.
If
$q_j\in \omega $
, then since the column is correct, it follows that
$E_j=\hat {P}_{c_j}=A_j$
. Note that since, in Case 1 of the
$M_j$
module, we only ever request to place
$J_j(x)=1$
if we already see enough of
$E_0\oplus \cdots \oplus E_j$
defined, it follows that when we ask for permission to assign
$J_j(x)$
, we either get permission or some column declares injury. Since the columns are all correct by assumption, the latter case is impossible. Thus
$J_j$
defines a sequence in
$2^\omega $
. Since
$q_j$
is correct, it is never injured, so
$(A_0\oplus \cdots \oplus A_{j-1}\oplus A_j)'$
cannot contain an x so that
$J_j(x)=0$
. Thus
$J_j\supseteq (A_0\oplus \cdots \oplus A_j)'$
. Similarly, since we only ever put
$J_j(x)=1$
after we have already seen a fragment
$\sigma \preceq E_j$
such that
$x\in (A_0\oplus \cdots \oplus A_{j-1}\oplus \sigma )'$
, it follows that
$J_j=(A_0\oplus \cdots \oplus A_{j})'=B_j$
.
Lemma 2.3. If
$i-1$
is correct at stage s and
$q_{i}=\mathrm{fix}$
, then i is also correct at stage s.
Proof Let t be the stage when
$c_{i}$
was last redefined. It follows that the first i columns were correct at the stage t. Hence, the tree S that we considered at that stage was determined correctly and the Low Basis Theorem allowed us to compute the functional
$\Phi _{c_{i}}$
such that
$\Phi _{c_i}((E_0\oplus \cdots \oplus E_{i-1})') = B = (E_0\oplus \cdots \oplus E_{i-1}\oplus A)'$
for some set A, and the fragment of
$E_{i}$
that has already been determined agrees with A. By Lemma 2.2, if i is correct at stage t then eventually
$E_{i} = A$
(and
$J_{i} = B$
). Using the same proof as above, we can argue that unless i is injured, whenever it defines a value for
$E_{i}(z)$
from now on, it agrees with A. The only reason for i not being correct at stage s is that a request for permission ends in injury. This request can only come from
$M_{i}$
and only for a bit
$J_i(x)$
to be given value
$0$
, given the assumption that s is correct for
$i-1$
. (As we argued in the previous proof, requests for
$J_i(x)$
to be given value
$1$
do not end in a failure of the second kind and so do not cause injury.) On the other hand,
$M_{i}$
will only ask for such a permission if it has already seen that
$\Phi _{c_{i}}^{J_{i-1}}(x) = 0$
. The tree T of possible extensions of
$\sigma \preceq E_i$
that make
$J_{i}(x) = 0$
contains an infinite path, namely A. So injury will not occur.
Lemma 2.4. Every stage terminates.
Proof Note that when we call
$M_j$
on input x, we may have to call
$N_k$
for
$k\leq j$
, and when we call
$N_j$
on input x, we may call
$M_k$
for
$k\leq j$
. One fear is that we may call
$M_j$
from
$N_j$
and
$N_j$
from
$M_j$
. The only reason that we call
$M_j$
from
$N_j$
is if j is a fix column. In this case,
$N_j$
calls an instance
$M_j$
on input x where x is a coding number, so this instance of
$M_j$
does not call
$N_j$
. Thus there are no loops in the module calls.
The other fear is in
$M_j$
calls for fix columns j. This makes a sequence of
$M_{(j-1)}$
-calls and waits to see a computation converge. Notice that if the sequence of
$M_{(j-1)}$
-calls were infinite, then we would determine the full
$j-1$
first columns during this stage. Thus, the stage ends if
$j-1$
is not correct at stage s. If
$j-1$
is correct at stage s, then Lemma 2.3 shows that j is correct at stage s, and Lemma 2.2 shows that we eventually assign the appropriate values of
$J_j$
, and thus the stage ends.
Lemma 2.5. For every i, there is a stage s so that the i-th column is correct at stage s.
Proof Let
$s_0>i$
be a stage such that
$i-1$
is correct. Thus, at stage
$t>s_0$
, each of the columns
$j<i$
successfully determines
$J_j(x)$
for every
$x\leq t$
. By the definition of correctness, if the i-th column is not correct at stage
$s_0$
, then there is a
$t>s_0$
at which
$q_i$
becomes redefined to
$\mathrm{fix}$
. But then by Lemma 2.3, the i-th column is correct at stage t.
Lemma 2.6. For every n there is a stage s and a column i so that the i-th column is correct at stage s,
$q_i\in \omega $
, and
$c_i=n$
at stage s.
Proof Let
$s_0$
be the first stage at which the lemma is true for every
$m<n$
. Let
$X = \hat {P}_n$
. Let i be the largest such that
$q_i\in \omega $
is defined at stage
$s_0$
. By the final action for every stage, all
$t>s_0$
end with some column
$k(t)$
having
$q_k\in \omega $
and
$c_k=n$
. If this
$k(t)$
is constant from some stage onward, then we have that this column must be correct and we are done. Thus, we need to see why k cannot change infinitely often. Suppose this were the case. Then let t be a stage where
$q_{k(t)}$
is the P-index of a function g such that for every e, if
$\Phi _e(((E_0 \oplus \dots \oplus E_{i})' \oplus X)') {\downarrow }= Z'$
for some set Z, then the e-th column
$g^{[e]}$
of g bounds the settling time function for
$Z'$
.
Since every column between i and
$k(t)$
is a fix column, we know that the
$(k(t)-1)$
st column is correct at stage t. Also, for every stage greater than t where we call
$M_{k(t)}$
on any input, we will get the correct response because g bounds the appropriate settling time function. Hence the
$k(t)$
-th column is not injured, so it is also correct at stage t.
Lemma 2.7. The set E gives an enumeration of S, and J is the running jump of E.
Proof By Lemma 2.6, every set in S is enumerated in E. By Lemma 2.5, every column is eventually correct. By Lemma 2.2, this means that the columns up to the i-th column each either copy elements of S or are low over elements of S, thus are in S. Similarly, Lemma 2.2 shows that the i-th column of J is the running jump of the first i columns of E.
This completes the proof of Theorem 1.6.
Note that we did not build an injective enumeration in the previous proposition, but any enumeration E for which we can compute the running jump can easily be turned into an enumeration
$E^*$
without repetitions, using the running jump. Furthermore, we do not lose the running jump, because we also have an index telling us how to compute
$J^*_i$
from
$J_{i^*}$
, where
$i^*$
is the least j such that
$E_0,\dots ,E_j$
contains i different elements.
Finally, let us remark that it is essential that we started with an enumeration of the functions, but ended up with an enumeration of the sets. We cannot strengthen Theorem 1.6 by assuming that we are only given an enumeration of the sets in S; this follows from Lemma 3.3 and the fact mentioned above that
$\mathcal {C} <^*_w \mathcal {B}$
. On the other hand, we cannot strengthen Theorem 1.6 to give us an enumeration of the functions computable from elements of S, along with the running jump of this enumeration; this follows by Proposition 4.6 and Theorem 4.15.
3 Continuous expansions of the reals
We will now show that continuous expansions of
$\mathcal {R}$
are generic Muchnik reducible to Baire space.
Theorem 1.7. Suppose
$f:\mathcal {R}^k\rightarrow \mathcal {R}$
is continuous. After collapse, let E be an enumeration of the sets in the old
$\mathcal {P}(\omega )$
, let J be the running jump for E, and let
$\mathcal {R}_f = (\mathcal {R},f)$
. Then there is a copy of
$\mathcal {R}_f$
computable from E and J.
Proof We need a good way of representing the elements in our copy of
$\mathcal {R}_f$
. We may think of each element as the sum of an integer z and a remainder e in the interval
$[0,1]$
, where e has a binary expansion corresponding to some
$E_i$
. (Here, we identify
$E_i$
with
$\chi _{E_i}$
.) Recall that a dyadic rationalFootnote
2
is one of form
$\frac {z}{2^k}$
, where
$z\in \mathbb {Z}$
and
$k\in \omega $
. Let D be the set of dyadic rationals. If e is a dyadic rational in the interval
$[0,1]$
, then e has two binary expansions. Even fixing the binary expansion, our enumeration may have more than one index i for the same set
$E_i$
. To resolve this issue we note the following obvious claim and use the properties of the running jump.
Claim 1. Using oracle
$E_i$
, and fixing z, we can apply a uniformly effective procedure to enumerate the true statements
$q < z+E_i$
,
$z+E_i < q$
, where q is a dyadic rational.
Using E and J, we can effectively say whether
$z+E_i = q$
, where q is a dyadic rational. We can also effectively say whether
$z + E_i = z' + E_j$
. Thus, we can effectively build a structure
$(R,<,\{q\}_{q\in D})$
with the ordering, plus constants q for the dyadic rationals, and with the elements we want. The constants are dense in the ordering, and we have a many-one function F, computable from E and J, taking each pair
$\langle z,i\rangle $
to the appropriate
$r\in R$
such that the statements from Claim 1 are true.
Claim 2. Using E and J, we can effectively expand the structure
$(R,<,\{q\}_{q\in D})$
, adding
$+$
,
$\times $
, and f.
We prove Claim 2 as follows. Recall that the set
$T = \text {Th}(\mathcal {R}_f)$
is one of the columns in E, so we can fix it as a parameter. Using T, we can enumerate the sentences of T saying that f maps I into
$I'$
, where I is a k-fold product of closed intervals with dyadic rational endpoints and
$I'$
is a closed interval with dyadic rational endpoints. Using a tuple
$\bar {r}=\langle z_j+E_{i_j}: i<k\rangle $
, we can enumerate the set
$\mathcal S$
of k-fold products of closed intervals with dyadic rational endpoints which contain
$\bar {r}$
. We want
$f(\bar {r}) = F(z'+ E_m)$
, where
$z' + E_m$
lies in all of the intervals
$I'$
with dyadic rational endpoints that, according to the theory T, contain
$f(I)$
for some
$I\in \mathcal S$
. For the given
$\bar {r}$
, the set of
$I'$
is c.e. in T and the
$E_{i_j}$
. Given
$E_m$
, and the jump of
$T\oplus \bigoplus _{j<n}E_{i_j}\oplus E_m$
, we can determine whether a given
$z'+E_m$
is an appropriate F-pre-image of
$f(\bar {r})$
. Thus, using E and J, we can effectively compute
$f(\bar {r})$
from
$\bar {r}$
.
Similarly, since the operations
$+$
and
$\times $
are also continuous, we can effectively compute
$r+r'$
and
$r\times r'$
from r and
$r'$
.
In the same way, we can prove that
$(\mathcal {R},\{f_n\}_{n\in \omega })\leq _w^*\mathcal {R}$
, where
$\{f_n\}_{n\in \omega }$
is a countable family of continuous functions on
$\mathcal {R}$
.
Theorem 3.1. Let
$f_1,f_2,\dots $
be continuous functions (of any arities) on
$\mathcal {R}$
. Then
$(\mathcal {R},\{f_n\}_{n\in \omega })\equiv _w^*\mathcal {R}$
.
In [Reference Downey, Greenberg and Miller3, Reference Igusa, Knight and Schweber7], it is shown that
$(\mathbb {R},+,<)$
and
$(\mathbb {R},\{q\}_{q\in \mathbb {Q}},<)$
are both generic Muchnik equivalent to
$\mathcal {R}$
. Using the techniques given above, and the fact that both of these structures are generic Muchnik above
$\mathcal {B}$
, it is now straightforward to show that
$(\mathbb {R},+,<)$
and
$(\mathbb {R},\{q\}_{q\in \mathbb {Q}},<)$
expanded with a countable number of continuous functions are equivalent to the original structures. In particular,
$(\mathbb {R},+,<) \equiv ^*_w (\mathbb {R},\{q\}_{q\in \mathbb {Q}},<) \equiv ^*_w \mathcal {R}$
now follows directly, because
$\times $
and
$+$
are continuous.
Recall that two other structures that have been studied are Cantor space
$\mathcal {C}$
and Baire
$\mathcal {B}$
space and for them we know that
$\mathcal {C}\equiv _w^*\mathcal {R}^*$
, and Baire space
$\mathcal {B}\equiv _w^*\mathcal {R}$
. We may consider expanding either structure by continuous functions. Let us start with
$\mathcal {C}$
.
Theorem 3.2. Let
$f_1,f_2,\dots $
be continuous functions (of any arities) on
$2^\omega $
. Then
$(\mathcal {C},\{f_i\}_{i\in \omega })\leq ^*_w \mathcal {B}$
.
Proof After collapse, given a copy of
$\mathcal {B}$
, we can compute an enumeration E of the family of sets in the old
$\mathcal {P}(\omega )$
, together with the associated running jump enumeration J by Theorem 1.6. Given E, we immediately compute a copy
$\mathcal {A}$
of
$\mathcal {C}$
. Computable in E and J, we have a many-one function I taking all indices i for sets
$E_i$
to elements
$a\in \mathcal {C}$
such that if
$E_i = E_j$
, then
$I(i) = I(j)$
. We let
$R_n(a)$
hold if and only if
$n\in E_i$
for any and all i such that
$I(i) = a$
. For simplicity, consider a single continuous function f on
$\mathcal {C}$
, of a single variable x. The fact that f is continuous means that
$\text {Th}(\mathcal {C},f)$
includes sentences
$\varphi _{\sigma ,\tau }$
, saying, for certain
$\sigma ,\tau \in 2^{<\omega }$
, that f maps the sequences extending
$\sigma $
to sequences extending
$\tau $
. For
$a\in \mathcal {A}$
, we say that a extends
$\sigma $
if, for all
$k\in dom(\sigma )$
,
$\sigma (k) = 1$
implies
$R_k(a)$
and
$\sigma (k) = 0$
implies
$\neg {R_k}(a)$
.
We let
$f(a) = b$
where for all sentences
$\varphi _{\sigma ,\tau }$
in
$\text {Th}(\mathcal {C},f)$
, if a extends
$\sigma $
, then b extends
$\tau $
. For each
$a\in \mathcal {A}$
, let
$T_a$
be the set of
$\tau $
such that for some sentence
$\varphi _{\sigma ,\tau }\in \text {Th}(\mathcal {C},f)$
, a extends
$\sigma $
. Assuming that
$E_j$
is the theory and
$I(i) = a$
, we can effectively enumerate
$T_a$
using
$E_i$
and
$E_j$
. For any
$s> i,j$
, we can use
$J_s$
to see if there is
$k\leq s$
with
$I(k) = b$
such that b extends
$\tau $
for all
$\tau \in T_a$
. For sufficiently large s, we will find an appropriate k and b. We let
$f(a) = b$
.
Recall that
$\mathcal {C}$
itself is not equivalent to
$\mathcal {B}$
, so not all continuous expansions of
$\mathcal {C}$
are equivalent to
$\mathcal {B}$
. However, some simple-looking expansions of
$\mathcal {C}$
turn out to be equivalent to
$\mathcal {B}$
. In particular, let
$\oplus \colon 2^\omega \times 2^\omega \to 2^\omega $
denote the join operator and
$\sigma \colon 2^\omega \to 2^\omega $
denote the shift, i.e.,
$\sigma (b_0b_1b_2b_3\cdots ) = b_1b_2b_3\cdots $
. Both are natural continuous functions on Cantor space. We show that Cantor space with join, and Cantor space with shift, are both equivalent to Baire space.
Lemma 3.3. If X can compute an enumeration E of the sets in a jump ideal I, and the set
$\text {Fin}_E = \{n : E_n \mathrm { is finite}\}$
is c.e. in X, then X computes an enumeration P of the functions in I.
Proof First, we show that X computes an enumeration F of the infinite sets in I. The construction of F is straightforward:
$F_n$
initially copies
$E_n$
, and if at any stage s we see that
$E_n$
is finite, because n enters the c.e. in X set
$Fin_E$
, we make
$F_n$
cofinite by adding all elements
$\geq s$
.
If A is an infinite set, then let
$f_A$
be the function such that
$f_A(n)$
is one less than the distance between the
$(n+1)$
-st and
$(n+2)$
-nd element of A; in other words,
$f_A(n) = p_A(n+1)-p_A(n)-1$
, where
$p_A$
is the principal function of A. It is straightforward to check that the functions computable from sets in I are exactly the functions of the form
$f_A$
where A is an infinite set in I. We can compute an enumeration P of these functions from the enumeration F.
Proposition 3.4.
$(\mathcal {C},\oplus )\equiv _w^* (\mathcal {C},\sigma )\equiv _w^*\mathcal {B}$
.
Proof That
$(\mathcal {C},\oplus )\leq _w^* \mathcal {B}$
and
$(\mathcal {C},\sigma )\leq _w^*\mathcal {B}$
follows directly from Theorem 3.2. For the other direction, we claim that, after collapse, every copy of
$(\mathcal {C},\oplus )$
or
$(\mathcal {C},\sigma )$
computes an enumeration E of the sets in the old
$\mathcal {P}(\omega )$
and enumerates the set
$\text {Fin}_E$
of the indices of finite sets in E. By Lemma 3.3 and the characterization given in [Reference Downey, Greenberg and Miller3] this shows that
$(\mathcal {C},\oplus )\geq _w^* \mathcal {B}$
and
$(\mathcal {C},\sigma )\geq _w^*\mathcal {B}$
.
For the structure
$(\mathcal {C},\sigma )$
, the claim follows from the fact that a set A is finite if and only if
$\sigma ^n(A) = 0^{\omega }$
for some
$n \in \omega $
. For
$(\mathcal {C},\oplus )$
, the claim follows from the fact that every finite set can be generated by taking joins of
$0^{\omega } = (0000\cdots )$
and
$10^{\omega } = (1000\cdots )$
. We show by induction on n that for any
$\sigma $
of length
$2^n$
, the sequence
$\sigma 0^{\omega }$
can be obtained from applying the operation join to
$0^{\omega }$
and
$10^{\omega }$
. For
$\sigma $
of length
$1$
the statement is obviously true. Suppose the statement is true for all
$\tau $
with
$|\tau |=2^n$
. Let
$\sigma $
be a string of length
$2^{n+1}$
. Let
$\tau _0$
be the string with length
$2^n$
, such that
$\tau _0(k) = \sigma (2k)$
, and let
$\tau _1$
be the string with length
$2^n$
, such that
$\tau _1(k) = \sigma (2k+1)$
. Note that
$\tau _00^\omega \oplus \tau _10^\omega = \sigma 0^\omega $
, so if
$E_1$
and
$E_2$
are the expressions for
$\tau _00^\omega $
and
$\tau _10^\omega $
, then
$(E_1)\oplus (E_2)$
is the expression for
$\sigma 0^{\omega }$
.
Another interesting relationship between Cantor space and Baire space is given by the notion of the jump of a structure. There have been several approaches to this notion: A. Soskova and Soskov [Reference Soskova, Cooper, Löwe and Sorbi19, Reference Soskova and Soskov20] use Moschovakis extensions [Reference Moschovakis15] and a coding of the forcing relation for
$\Pi _1$
formulas, Puzarenko [Reference Puzarenko16] and Stukachev [Reference Stukachev23] proposed a definition that works well with
$\Sigma $
-reducibility, and Montalbán investigated a definition that expands the original structure by a complete set of relations defined by computable infinitary
$\Pi _1$
formulas [Reference Montalbán12]. The relationships among these three approaches are discussed by Montalbán in [Reference Montalbán13]. In [Reference Montalbán13], Montalbán uses relations defined by computable infinitary
$\Sigma _1$
formulas. This is the approach that we use, lifting it to uncountable structures.
Definition 3.5 (Jump of a structure).
Let
$\mathcal {A}$
be a structure in a computable language. The jump of
$\mathcal {A}$
is the structure
$\mathcal {A}' = (\mathcal {A}, P_0, P_1, \dots )$
, where
$\{P_n\}_{n<\omega }$
is a listing of the relations on
$\mathcal {A}$
defined by computable infinitary
$\Sigma _1$
formulas (without parameters). (Note that we have a computable list of the formulas that define these relations.)
Proposition 3.6.
$\mathcal {C}'\equiv ^*_{w}\mathcal {B}$
.
Proof We know that after collapse, every copy of
$\mathcal {B}$
computes an enumeration E of the family of sets that is the old powerset of
$\omega $
, together with the running jump. We claim that this computes a copy
$\mathcal {A}'$
of
$\mathcal {C}'$
. We assign constants a effectively to indices for the distinct sets
$E_i$
. Note that equality can be determined using the running jump (although we could even have assumed that our original enumeration were injective). Also using the running jump, we can determine the truth of a given computable
$\Sigma _1$
formula
$\varphi (\bar {a}) = \bigvee _j(\exists \bar {u}_j)\;\alpha _j(\bar {a},\bar {u}_j)$
(where
$\alpha _j$
is finitary quantifier-free). To see this, we note that the elementary first-order theory of
$\mathcal {C}$
is computably axiomatizable, with effective elimination of quantifiers. So we have an effective procedure, using the sets
$\bar {a}$
, for deciding whether a given disjunct
$(\exists \bar {u}_j)\;\alpha _j(\bar {a},\bar {u}_j)$
is true. With the running jump, we can say whether there is some disjunct that is true.
After collapse, a copy
$\mathcal A$
of
$\mathcal {C}'$
with universe
$\omega $
computes an enumeration E of the sets in the old
$\mathcal {P}(\omega )$
. In particular, for the n-th element
$x_n$
of
$\mathcal A$
, we enumerate the set
$E_n$
so that
$x_n=\chi (E_n)$
. Further, the jump has predicates
$P_k$
which define the computable
$\Sigma _1$
formula which says that
$x(m)=1$
for some
$m>k$
. We can thus enumerate from
$\mathcal A$
the indices n so that for some k,
$\mathcal A\models \neg P_k (x_n)$
. Thus, computable in
$\mathcal A$
, we have an enumeration of all the sets in the old
$\mathcal {P}(\omega )$
and
$\text {Fin}_E$
is c.e. in
$\mathcal A$
. Thus by Lemma 3.3 and the characterization given in [Reference Downey, Greenberg and Miller3], this shows that
$\mathcal {C}'\geq _w^* \mathcal {B}$
.
4 The Borel complete degree
We have seen that
$\mathcal {B}\equiv ^*_w\mathcal {R}$
is generic Muchnik above every continuous expansion of
$\mathcal {R}$
or
$\mathcal {C}$
. In this section we prove that continuous expansions of Baire space can be strictly more complicated. This can be seen as a consequence of the fact that the projections of closed subsets of Baire space can be quite complicated—indeed, they are exactly the
$\boldsymbol\Sigma ^{\mathbf 1}_{\mathbf 1}$
classes. The upper bound of all continuous expansions of
$\mathcal {B}$
is an interesting generic Muchnik degree in its own right. We call it the Borel complete degree because, as we will see, it bounds all Borel structures (in fact, all Borel quotients).
We consider structures with universe equal to Baire space, although we could equally well consider structures with universe equal to Cantor space or
$\mathbb {R}$
. For Baire space, we have the topology generated by the basic open neighborhoods
$N_\sigma = \{f\in \omega ^\omega :f\supseteq \sigma \}$
, where
$\sigma \in \omega ^{<\omega }$
. The Borel subsets of Baire space are the members of the
$\sigma $
-algebra generated by these basic open neighborhoods.
Definition 4.1 (Borel structure, congruence relation, Borel quotient).
-
(1) For a Polish space X, a Borel structure (on X) has the form
$\mathcal {A} = (D,(R_n)_{n\in \omega })$
, where
$D\subseteq X$
is a Borel set, and for all n,
$R_n$
is a Borel relation on X. -
(2) For a structure
$\mathcal {A} = (D,(R_n)_{n\in \omega })$
, a binary relation E on D is a congruence relation if it is an equivalence relation and for all n, if
$R_n$
is k-ary and
$\bar {a},\bar {b}$
are k-tuples such that
$a_i E b_i$
for
$i < k$
, then
$R_n(\bar {a})$
iff
$R_n(\bar {b})$
. From a congruence relation E on
$\mathcal {A}$
, we get a well-defined quotient structure
$\mathcal {A}/_E$
with universe equal to the set of equivalence classes
$D/_E$
and relations
$R_n/_E$
that hold of a k-tuple
$a_0/_E,\ldots ,a_{k-1}/_E$
iff
$R_n$
holds of
$a_0,\ldots ,a_{k-1}$
. -
(3) A Borel quotient is the quotient of a Borel structure
$\mathcal {A}$
by a Borel congruence relation.
Borel structures were first studied by H. Friedman in unpublished notes (see [Reference Steinhorn, Harrington, Morley, ŠĊedrov and Simpson21]). More work on Borel structures can be found in [Reference Louveau, Judah, Just and Woodin10, Reference Steinhorn, Barwise and Feferman22]. Some recent work can be found in [Reference Hjorth and Nies5, Reference Montalbán, Nies, Greenberg, Hirschfeldt, Hamkins and Miller14], although they use the name Borel structure for what we call a Borel quotient.
Examples of Borel structures include
$(\mathcal {B},\oplus ,\,')$
,
$(\mathcal {C},\oplus ,\,')$
, and
$\mathcal {R}$
. An example of a Borel quotient is the Turing degrees with
$\oplus $
and
$'$
. The Büchi automatic structures are also Borel quotients [Reference Hjorth, Khoussainov, Montalbán and Nies4]. Another class of examples consists of the automorphism groups of countable structures that are algebraic in the sense that the language consists just of operation symbols.
Definition 4.2. A structure
$\mathcal {A}$
is Borel complete if it is a Borel structure that is generic Muchnik above every other Borel structure. The generic Muchnik degree of such a structure is also called Borel complete.
Below, we give an example of a continuous expansion of
$\mathcal {B}$
that turns out to have Borel complete degree. First, we know what the join and jump are, for sets; we define these operations on functions as follows.
Definition 4.3 (Join and jump for functions).
-
(1) For functions
$f,g\in \omega ^\omega $
, the join is the function h such that
$h(2n) = f(n)$
and
$h(2n+1) = g(n)$
. We write
$f\oplus g$
for the join. -
(2) For
$f\in \omega ^\omega $
, we have a jump
$\{e:\varphi _e^f(e)\downarrow \}$
. We define the jump of the function f to be the characteristic function of this set.
Example 4.4. Consider the following subclass of
$\omega ^\omega $
:
$$\begin{align*}P = \{(f\oplus g)\oplus h\colon h\text{ is the settling time function for }f'\text{ and }g=f'\}. \end{align*}$$
Note that it is
$\Pi ^0_1$
to verify that h is the settling time function for
$f'$
, and given h, it is
$\Pi ^0_1$
to verify that
$g=f'$
. Therefore, P is a
$\Pi ^0_1$
class in
$\omega ^\omega $
, hence closed. Let
$F\colon \mathcal {B}\to \mathcal {B}$
be a continuous function such that
$P = F^{-1}(0^\omega )$
. Because P is a
$\Pi ^0_1$
class, we can even take F to be computable. The structure
$(\mathcal {B},\oplus ,F)$
is a continuous expansion of
$\mathcal {B}$
with strictly higher generic Muchnik degree. Towards proving this, we need to understand what kind of computational power is present in copies of
$(\mathcal {B},\oplus ,F)$
after we collapse the continuum.
Proposition 4.5. Let I be a countable jump ideal. Let
$(\mathcal {B}_I,\oplus ,F)$
be the restriction of
$(\mathcal {B},\oplus ,F)$
to the functions in I. Any copy of
$(\mathcal {B}_I,\oplus ,F)$
computes an enumeration of the functions in I along with join and jump as functions on indices.
Proof A copy
$\mathcal {A}$
of
$(\mathcal {B}_I,\oplus ,F)$
gives us a natural enumeration
$\{f_n\}_{n\in \omega }$
of the functions in I such that
$\oplus ^{\mathcal {A}}$
is exactly a function that takes two indices to the index of the join. To find the jump of
$f_n$
, search for
$m,j\in \omega $
such that
$F^{\mathcal {A}}((n\oplus ^{\mathcal {A}} m)\oplus ^{\mathcal {A}} j)$
is the index of
$0^\omega $
. Then
$f_m = f_n'$
.
In Theorem 4.15, we will prove that for a sufficiently rich ideal I, it is strictly easier to compute an enumeration of the functions in I than to compute an enumeration of the functions in I along with join and jump as functions on indices. First, we make some easy observations about the difficulty of the latter task, before defining how rich we want our ideals to be.
Proposition 4.6. For a countable ideal I and a set X, the following are equivalent:
-
(1) X computes an enumeration of the sets, or the functions, in I, with join and jump as functions on indices.
-
(2) X computes an enumeration of the sets, or the functions, in I, with running jump as a function on indices.
-
(3) X computes an enumeration of the sets, or the functions, in I with the corresponding running double jump function, not on indices.
-
(4) X computes an enumeration of the functions in I, with the running jump function, not on indices.
Proof We first show that (1)
$\Rightarrow $
(2)
$\Rightarrow $
(3)
$\Rightarrow $
(4)
$\Rightarrow $
(1) for functions. Suppose X computes an enumeration E of the functions in I, with join and jump as functions on indices. We can find an index for
$(E_0\oplus \cdots \oplus E_n)'$
, so we have the running jump as a function on indices. Having an index j for
$(E_0\oplus \cdots \oplus E_n)'$
, we can find an index k for
$(E_0\oplus \cdots \oplus E_j)'$
, so we can compute
$E_n"$
. In particular, we can also compute the running jump function. Finally, having the running jump function, and two indices i and j, we can search for an index k such that
$E_i \oplus E_j = E_k$
, which we computably do using the running jump function; and given an index i, we can search for indices j and k such that
$E_k$
is the jump of
$E_i$
with settling time function
$E_j$
, which we can also do computably using the running jump function. Using the same argument, we can show that (4)
$\Rightarrow $
(1)
$\Rightarrow $
(2)
$\Rightarrow $
(3) holds with (1), (2), and (3) for sets.
Finally, we show that (3) for sets is equivalent to (3) for functions. Clearly, the version for functions implies the version for sets. Suppose that X computes an enumeration E of the sets in I along with the running double jump. From an infinite set A, we obtain a natural function
$f_A(n) = p_A(n+1)-p_A(n)-1$
, where
$p_A$
is the principal function of A as we did in the proof of Lemma 3.3. Once again we note that every function
$f\colon \omega \to \omega $
is of the form
$f_A$
for some infinite set A. Using the running double jump we can effectively determine whether
$E_i$
is infinite. If
$E_i$
is infinite, then we let
$F_i = f_{E_i}$
, and if
$E_i$
is finite, we let
$F_i$
be the identity function. Now, note that
$(E_0 \oplus \dots \oplus E_i)"$
can compute an index e such that
$\Phi _e(E_0 \oplus \dots \oplus E_i) = (F_0 \oplus \dots \oplus F_i)$
, so
$(E_0 \oplus \dots \oplus E_i)"$
can also compute
$(F_0 \oplus \dots \oplus F_i)"$
. Thus, we can compute the running double jump on the enumeration F of the functions.
Corollary 4.7.
$(\mathcal {B},\oplus ,\,')\equiv ^*_w (\mathcal {C},\oplus ,\,')$
.
Now it is not hard to show, using the standard encoding of Cantor space in the real numbers, that there is also a Borel expansion of
$\mathcal {R}$
in the same generic Muchnik degree as
$(\mathcal {B},\oplus ,\,')$
.
Proposition 4.6 also allows us to easily adapt the proof of Proposition 3.6 to give an additional example of a structure in the Borel complete degree.
Corollary 4.8.
$(\mathcal {B},\oplus ,\,')\equiv ^*_w \mathcal {B}'$
.
We turn toward the second main result of the paper, which says that adding further Borel relations to
$(\mathcal {B},\oplus ,\,')$
does not increase the generic Muchnik degree.
Theorem 4.9. If
$\mathcal {B}^*$
is a Borel expansion of
$\mathcal {B}$
, then
$\mathcal {B}^*\leq _w^*(\mathcal {B},\oplus ,\,')$
.
To extend this result from Borel expansions of
$\mathcal {B}$
to arbitrary Borel structures, we use the following general observation about quotients.
Observation 4.10. For any structure
$\mathcal {A}$
and any congruence relation E on
$\mathcal {A}$
,
$\mathcal {A}/_E\leq _w^*(\mathcal {A},E)$
. That is, from a copy of
$\mathcal {A}$
, with the congruence relation added, we can compute a copy of the quotient structure.
Hence, we get the following.
Corollary 4.11. If
$\mathcal {B}^*$
is a Borel expansion of
$\mathcal {B}$
and E is a Borel congruence relation on
$\mathcal {B}^*$
, then
$\mathcal {B}^*/_E\leq _w^*(\mathcal {B},\oplus ,\,')$
.
In other words,
$(\mathcal {B},\oplus ,\,')$
is Borel complete. Recall that we started this section promising that the continuous expansion
$(\mathcal {B},\oplus ,F)$
of
$\mathcal {B}$
has Borel complete degree.
Corollary 4.12.
$(\mathcal {B},\oplus ,\,')\equiv ^*_w (\mathcal {B},\oplus ,F)$
.
Proof Since
$(\mathcal {B},\oplus ,F)$
is a Borel expansion of
$\mathcal {B}$
, we have
$(\mathcal {B},\oplus ,F)\leq ^*_w (\mathcal {B},\oplus ,\,')$
. On the other hand,
$(\mathcal {B},\oplus ,\,')\leq ^*_w (\mathcal {B},\oplus ,F)$
by Proposition 4.5.
Toward the proof of Theorem 4.9, we note that the ideal of sets from the ground model satisfies a very strong closure property, much stronger than we have needed so far.
Definition 4.13 (Hyper-Scott ideal).
We say that I is a hyper-Scott ideal if it is a Turing ideal, and whenever
$T\subseteq \omega ^{<\omega }$
is a tree in I, if T has an infinite path, then it has an infinite path computable from a set in I.
Proposition 4.14. If I is the ideal sets from the ground model, then it is a hyper-Scott ideal.
Proof This is a very simple application of Shoenfield absoluteness [Reference Shoenfield18]. Arguing directly, if
$T\subseteq \omega ^{<\omega }$
is a tree in the ground model with no path, then in the ground model there is a rank function
$\rho \colon T\to \omega _1$
witnessing that T is well-founded. But
$\rho $
also witnesses that T is well-founded in the extension.
Proof of Theorem 4.9
Let
$\mathcal {B}^* = (\mathcal {B},(R_n)_{n\in \omega })$
, where the
$R_n$
’s are Borel relations. These relations may have different arity. However, we can code a finite sequence
$(f_0,\ldots ,f_r)$
of functions by a single function f, where
$f_i(k) = m$
iff
$f(r\cdot k + i) = m$
. With this in mind, we may suppose that the relations
$R_n$
are all unary. Furthermore, we can combine the relations
$R_n$
into one relation R such that
$R(nf)$
holds if and only if
$R_n(f)$
holds, where
$nf(k) = \langle n,f(k)\rangle $
. Thus, we may suppose that we have just one unary Borel relation
$R\subseteq \omega ^\omega $
.
Let I be the ideal of sets from the ground model. After collapse, any copy of
$(\mathcal {B},\oplus ,\,')$
can compute an enumeration of the functions in I along with join and jump as functions on indices of the enumeration. Since R is Borel in the ground model, it is
$\boldsymbol\Delta ^{\mathbf 1}_{\mathbf 1}$
. Hence there are trees
$T,S\subseteq \omega ^{<\omega }$
, both in I, such that
$$\begin{align*}R(f) \iff (\exists h)\; f\oplus h\in[T] \iff (\forall h)\; f\oplus h\notin[S]. \end{align*}$$
Note that
$f\oplus h\in [T]$
and
$f\oplus h\in [S]$
can be checked using
$(f\oplus h\oplus T)'$
and
$(f\oplus h\oplus S)'$
, which in turn can be uniformly computed from the indices of f, h, and the functions computing T and S. Therefore, by searching for a function h in I that witnesses either
$R(f)$
or its negation, we can effectively determine if
$R(f)$
holds for any function f from our enumeration of the functions in I. Now it is straightforward to compute a copy of
$\mathcal {B}^* = (\mathcal {B},R)$
.
Finally, we show that
$(\mathcal {B},\oplus ,\,')$
is strictly stronger than
$\mathcal {B}$
. Note that this does not follow immediately from the fact that
$\mathcal {B}'\equiv ^*_w (\mathcal {B},\oplus ,\,')$
because the jump of a structure is not necessarily strictly above the structure itself; both Montalbán [Reference Montalbán12] and Puzarenko [Reference Puzarenko17] give fixed points for the jump operator on structures, the former under an additional set theoretic assumption.
Theorem 4.15. Assume that I is a hyper-Scott ideal. Then there is an enumeration of the functions in I that does not compute an enumeration of the functions in I along with functions
$f\colon \omega ^2\to \omega $
and
$g\colon \omega \to \omega $
on indices of the enumeration that interpret join and jump, respectively.
Proof We produce an enumeration
$\mathcal {F}$
of the functions in I by forcing. Our forcing partial order consists of conditions
$q\in (\omega ^\omega )^{<\omega }$
that are sequences of functions from I. We say that a condition p extends q (written as
$p\preceq q$
) if p extends q as a sequence.
Consider Turing functionals
$\mathcal {E}$
, f, and g. We want to diagonalize against
$\mathcal {E}^{\mathcal {F}}$
being an enumeration of the functions in I such that
$f^{\mathcal {F}}\colon \omega ^2\to \omega $
takes any two indices of functions in
$\mathcal {E}^{\mathcal {F}}$
to an index of their join, and
$g^{\mathcal {F}}\colon \omega \to \omega $
takes every index of a function in
$\mathcal {E}^{\mathcal {F}}$
to an index of its jump. Assume, for a contradiction, that there is a condition q that forces this outcome. Fix an index e such that
$e\in (T\oplus h)'$
if and only if h is not a path through T, where T is treated as a tree under an effective bijection between trees in
$\omega ^{<\omega }$
and elements of
$\omega ^\omega $
. We will use the symbol
to denote compatibility. In particular, for
$\sigma \in (\omega ^{<\omega })^{<\omega }$
and a condition p,
if each component
$\sigma _n$
is an initial segment of the corresponding component
$p_n$
.
Claim. For any tree T in I, the following
$\Pi ^1_1[q\oplus T]$
statement is equivalent to “T has an infinite path”:
(Here p is understood to range over extensions of q in
$(\omega ^\omega )^{<\omega }$
, though not necessarily forcing conditions—the new functions that are listed need not be in I. Also,
$\sigma $
and
$\tau $
are intended to be finite, and hence they are essentially number quantifiers.)
Note that if we can prove this claim, then we have the necessary contradiction, because it is
$\Sigma ^1_1[q]$
-complete to determine whether a q-computable tree
$T\subseteq \omega ^{<\omega }$
has an infinite path.
To prove the claim, let T be a tree in I. First, let us assume that (*) holds. Let
$p\preceq q$
force the specific location of T in the list
$\mathcal {E}^{\mathcal {F}}$
, and let this location be n. Therefore, it is true that
. Otherwise, we could refute our choice of p. Since (*) holds, we have
Let
$r\preceq p$
extend
$\tau $
. Then r forces that
$e\notin (T\oplus \mathcal {E}^{\mathcal {F}}_m)'$
, so
$\mathcal {E}^{\mathcal {F}}_m$
is a path on T. Therefore, T has an infinite path.
Now assume that T has an infinite path. Because I is a hyper-Scott ideal, T has a path h in I. Also, because I is a hyper-Scott ideal, if (*) fails, it fails for a
$p\in I$
. So it is enough to consider
$p\preceq q$
and
$n\in \omega $
such that
. Note that p forces
$\mathcal {E}^{\mathcal {F}}_n$
to be T, because q forces it to be total and it cannot be incompatible with T. Take
$r\preceq p$
forcing the specific location of h in
$\mathcal {E}^{\mathcal {F}}$
, and let this location be m. Now take
and k such that
$g^\tau (f^\tau (n,m))\downarrow = k$
and
$\mathcal {E}^\tau _k(e)\downarrow $
. Such a
$\tau $
exists because q forces
$g^{\mathcal {F}}$
,
$f^{\mathcal {F}}$
, and
$\mathcal {E}^{\mathcal {F}}$
to be total. Our choice of r ensures that
$\mathcal {E}^\tau _k(e)=(T\oplus h)'(e)=0$
, because h is a path on T. Therefore, (*) holds.
We have proved that any tree T in I has an infinite path if and only if (*) holds. This is a contradiction, and hence any condition can be extended to a condition that diagonalizes against
$\mathcal {E}$
, f, and g.
Theorem 4.16.
$(\mathcal {B},\oplus ,\,')>^*_w \mathcal {B}$
.
Note that, as a function on either
$\mathcal {B}$
or
$\mathcal {C}$
, the jump
$'$
is of Baire class 1, i.e., a pointwise limit of continuous functions. Indeed it is a pointwise limit of a computable sequence of computable functions. In terms of the effective Borel hierarchy, the graph of
$'$
is
$\Pi ^0_2$
, in other words effective
$G_\delta $
. So as mentioned above, there is an expansion of the real numbers by continuous functions and a unary function of Baire class 1 (or a
$\Pi ^0_2$
binary relation) which is in the Borel complete degree. This puts a severe limitation on any potential strengthening of Theorem 1.7.
Funding
Andrews was partially supported by grant DMS #1600228 from the National Science Foundation. Knight was partially supported by grant DMS #1800692 from the National Science Foundation. Miller was partially supported by grant #358043 from the Simons Foundation. Soskova was partially supported by grant DMS #1762648 from the National Science Foundation. Soskova and Miller were partially supported by grant DMS #2053848 from the National Science Foundation.
