1 Introduction
A longstanding programme in computability theory explores the relationship between the computably enumerable degrees and the lattice of computably enumerable sets. A great deal of Soare’s classic text [Reference Soare7] is devoted to this analysis. For example, if
${\mathbf a}$
is high then
${\mathbf a}$
contains a maximal c.e. set, and no non-high c.e. degree contains a maximal set,Footnote
1
as proven in the ground-breaking paper of Martin [Reference Martin4].
One of the fundamental themes is that low and low
$_2$
sets resemble computable sets in that, for example, low
$_2$
c.e. sets have maximal supersets. Here A is low if
$A'\equiv _T \emptyset '$
and A is low
$_2$
if
$A''\equiv _T \emptyset ''$
. Indeed, if A is c.e. and low, then the lattice of c.e. supersets of A is isomorphic to the lattice of c.e. sets (Soare [Reference Soare6]) and this is long conjectured to be true for the supersets of low
$_2$
sets, but this much harder question remains open (see Soare [Reference Soare7, Chapters X and XVI], for example).
On the other hand, low
$_2$
seems to be a demarcation point. Non-low
$_2$
sets have certain domination properties which are certainly useful in the structure of the global degrees. For example, non-low
$_2$
degrees bound 1-generic degrees, and are complemented below, whereas there are minimal low
$_2$
degrees. See, for example, Lerman [Reference Lerman3].
For the c.e. sets, in 1976, Shoenfield [Reference Shoenfield5] proved that non-low
$_2$
c.e. degrees contain c.e. sets with no maximal c.e. supersets, and Lachlan [Reference Lachlan2] showed that low
$_2$
c.e. sets have maximal supersets (and hence r-maximal supersets defined below). Thus there is an elementary difference between properties of low
$_2$
c.e. sets and some non-low
$_2$
c.e. sets. Indeed, Shoenfield’s Theorem shows that a certain natural set, called the deficiency set, has no hyperhypersimple c.e. superset.
One of the natural variations on being maximal is what is known as r-maximal. We recall that a co-infinite c.e. set D is r-maximal if for all computable sets X,
$X\cup D=^*\omega $
, or
$\overline {X}\cup D=^*\omega $
. That is no computable set splits
$\overline {D}.$
In this paper we solve a question first stated in 1987 by Soare [Reference Soare7, p. 233]. Soare asks to classify the degrees of c.e. sets with no r-maximal supersets. In this paper we show that the classification aligns with that of those with no maximal supersets.
Theorem 1.1. Suppose that
${\mathbf a}$
is a c.e. non-low
$_2$
degree. Then
${\mathbf a}$
contains a c.e. set D with no r-maximal superset.
The techniques we use are quite different than the mysterious ones of Shoenfield [Reference Shoenfield5], and build on ideas of Downey and Shore [Reference Downey and Shore1].
2 The proof
The proof of Theorem 1.1 uses some general machinery developed by Downey and Shore [Reference Downey and Shore1] for working below a non-low
$_2$
c.e. degree. We will need to discuss some of these ideas to make the current paper self-contained.
In the global degrees, there is a well-known technique of working below a non-low
$_2$
degree using escape functions. A degree
${\mathbf d} \leq {\mathbf 0'}$
is non-low
$_2$
iff for every function
$h \leq _T \emptyset '$
, there is a function g computable in
${\mathbf d}$
such that g is not dominated by h. This characterization is used for constructions related to
${\mathbf d}$
as follows: Relying on specific properties of the requirements to be met, one defines “in advance” a function h which gives an appropriate “search space” inside of which one should look for witnesses to satisfy some requirements. This function will be computable from
$\emptyset '$
due to the specific nature of the relevant requirements. Now if
${\mathbf d}$
is non-low
$_2$
, there is a strictly increasing function g computable in
${\mathbf d}$
not dominated by h. The idea then is to use g to
${\mathbf d}$
-computably bound searches and hence make the construction an oracle one computable in
${\mathbf d}$
. By the way g and h have been constructed, the fact that
$g(x)> h(x)$
infinitely often guarantees that, by a priority argument, we get to meet all the requirements. The classical example of this is showing that all non-low
$_2$
degrees bound 1-generics, where we use a function h for which
$h(x)$
says: for all strings
$\sigma $
of length x and all
$e\le x$
, compute a stage where if
$\sigma $
has an extension in
$V_e$
, the e-th c.e. set of strings, we can see it by stage s. Then if we take a non-low
$_2$
set D there is a function
$g\le _T D$
which infinitely often escapes this function. We use
$g(x)$
as our search space to figure out which requirement to pursue. Then a standard finite injury argument works (see, e.g., Lerman [Reference Lerman3] and Downey and Shore [Reference Downey and Shore1]).
We consider this method in the context of c.e. degrees. The natural idea we pursue is to use the global characterization of non-low
$_2$
and then approximate the functions g and h via the Limit Lemma. Now we will be given a c.e. set
$D=\bigcup _s D_s$
of non-low
$_2$
degree and a “witness” function h for the satisfaction of some requirements. Again
$h\le _T \emptyset '$
. We apply the Limit Lemma to h so that
$h(x)=\lim _s h(x,s)$
with
$h(x,s)$
a computable approximation to h. Again, since D is not low
$_2$
, there will be a function
$g\le _T D$
not dominated by h which we can also approximate via the Limit Lemma. Since
$g\le _T D$
, there is a reduction
$\Gamma (D)=g$
. The problem is that, as
$h(x)$
only equals
$\lim _s h(x,s)$
and
$g(x)$
only equals
$\lim _s g(x,s)$
, we must be able to “correct” our mistakes. This is a serious problem since the objects we need to construct must not only be computable from D but also c.e.
The main idea in the constructions from Downey and Shore [Reference Downey and Shore1] is that we must be able to correct the mistakes that occur when
$g(x,s)$
does not have its final value by dumping elements into the set we are constructing whenever
$g(x,s)$
or even
$D\upharpoonright g(x,s)$
changes where
$g(x,s)$
is the standard approximation of
$\Gamma (D)$
. (In fact, below we will choose a c.e. member D of the given non-low
$_2$
degree
$\textbf {a}$
such that D has the desired dumping property.) Moreover, as in [Reference Downey and Shore1], for our construction we will require that our computable approximations
$h(x,s)$
and
$g(x,s)$
have certain nice properties like monotonicity (see the construction below for details).
Having explained some of its basic features we now turn to the proof of Theorem 1.1.
Proof of Theorem 1.1
Fix any c.e. set A in the given non-low
$_2$
c.e. degree
$\textbf {a}$
, let f be a computable 1-1 function enumerating A, and let
$$ \begin{align*}D = \{t: \exists \; s> t (f(s) < f(t) ) \}\end{align*} $$
be the deficiency set of A w.r.t. f. Since
$D \equiv _T A$
(see Soare [Reference Soare7, p. 81]), it suffices to show that no superset of D is r-maximal. So, for the remainder of the proof, fix a coinfinite c.e. superset W of D. It suffices to define a c.e. splitting
$(X_0,X_1)$
of
$\omega $
, i.e., c.e. sets
$X_0$
and
$X_1$
such that
$$ \begin{align} X_0 \cup X_1 = \omega \text{ and } X_0 \cap X_1 = \emptyset \end{align} $$
(hence
$X_0$
is computable and
$X_1 = \overline {X_0}$
), which meet the requirements
$$ \begin{align*}R_{2e+i}: \exists \; x \geq e \; (x \in X_i \cap \overline{W})\end{align*} $$
for
$e \geq 0$
and
$i \leq 1$
. Note that this ensures that
$X_0 \cap \overline {W}$
and
$\overline {X_0} \cap \overline {W}$
are infinite. So the computable set
$X_0$
witnesses that W is not r-maximal. In the remainder of the proof we construct the desired c.e. sets
$X_0$
and
$X_1$
by a finite injury argument.
Let
$\{D_s\}_{s \geq 0}$
be the natural enumeration of D defined by
$D_0= \emptyset $
and
$$ \begin{align*}D_{s+1} = D_s \cup \{x \leq s: f(s+1) < f(x)\}.\end{align*} $$
As in [Reference Downey and Shore1]’s proof that D has no maximal superset, the crucial property of this enumeration is that if x is enumerated into D at stage
$s+1$
then all elements of the interval
$(x,s]$
not yet in D also enter D at stage
$s+1$
:
$$ \begin{align} x \in D_{s+1} \setminus D_s \; \Rightarrow \; \big( x \leq s \; \& \; [x,s] \subseteq D_{s+1} \big) \end{align} $$
(namely, if
$r \in (x,s]$
then
$f(r)> f(x)$
as
$x\notin D_{r}$
and so
$r \in D_{s+1}$
). In the following we refer to this property as the dump property of
$\{D_s\}_{s \geq 0}$
.
The function h is defined by recursion as follows. Given a computable enumeration
$\{W_s\}_{s \geq 0}$
of W such that
$D_s \subseteq W_s \subset \omega \upharpoonright s$
, let
$$ \begin{align*}h(0) = 0\end{align*} $$
and
$$ \begin{align} \begin{array}{c} h(x+1) = \mu s> t_{x} \; (\overline{W} \cap [t_{x},s) \not= \emptyset) \\ \text{where } t_x = \mu t > h(x)\; (W_t \upharpoonright h(x) = W \upharpoonright h(x)). \end{array} \end{align} $$
Then, for any number x,
$$ \begin{align} x \leq h(x) < t_x < h(x+1), \end{align} $$
$$ \begin{align} W_{t_x} \upharpoonright h(x) = W \upharpoonright h(x), \end{align} $$
and
$$ \begin{align} \overline{W} \cap [t_x,h(x+1)) \not= \emptyset. \end{align} $$
We will work with computable approximations
$h(x,s)$
and
$t^s_x$
of
$h(x)$
and
$t_x$
, respectively, recursively defined as follows. Let
$h(0,s) = h(0)=0$
for
$s \geq 0$
, and let
$$ \begin{align} \begin{array}{c} h(x+1,s) = \mu s'> t^s_x \; (\overline{W_{s}} \cap [t^s_x,s') \not= \emptyset),\\ \text{where } t^s_x = \mu t > h(x,s) (W_s \upharpoonright h(x,s) \subseteq W_t \upharpoonright h(x,s)), \end{array} \end{align} $$
for
$x,s \geq 0$
. Note that
$$ \begin{align} x \leq h(x,s) < t^{s}_x < h(x+1,s) < t^s_{x+1}, \end{align} $$
$$ \begin{align} h(x,s) \leq h(x,s+1) \; \& \; t^{s}_x \leq t^{s+1}_x, \end{align} $$
$$ \begin{align} h(x,s) \not= h(x,s+1) \; \Rightarrow \; W_{s+1} \upharpoonright h(x,s) \not= W_{s} \upharpoonright h(x,s), \end{align} $$
$$ \begin{align} W_{s+1} \upharpoonright h(x,s) \not= W_{s} \upharpoonright h(x,s) \; \Rightarrow \; t^{s+1}_{x} \geq s+1, \end{align} $$
and
$$ \begin{align} \lim_{s \to \infty} h(x,s) = \sup_{s \to \infty} h(x,s) = h(x) \text{ and } \lim_{s \to \infty} t^s_x = \sup_{s \to \infty} t^s_x = t_x \end{align} $$
hold for all
$x,s \geq 0$
. For the sake of completeness, the rather straightforward proofs of (8)–(12) are given in the Appendix.
Obviously,
$h \leq _T W$
hence
$h \leq _T \emptyset '$
. So, since D is not low
$_2$
, there is a function
$\hat {g} \leq _T D$
not dominated by h. For the construction we replace
$\hat {g}(x)$
by a D-computable function
$g(x)$
majorizing
$\hat {g}(x)$
which has a more amenable computable approximation
$g(x,s)$
. The properties of the function
$g(x)$
and its approximation
$g(x,s)$
which are crucial for the construction of the desired c.e. sets
$X_0$
and
$X_1$
are given in the following claim.
Claim 1. There are total functions
$g(x)$
and
$g(x,s)$
such that the unary function g is not dominated by h, i.e.,
$$ \begin{align} \exists^{\infty}x \; (h(x) < {g}(x)), \end{align} $$
the binary function
$g(x,s)$
is computable and approximates
$g(x)$
from below, i.e.,
$$ \begin{align} {g}(x) = \sup_{s \to \infty} g(x,s) = \lim_{s \to \infty} g(x,s), \end{align} $$
and, for any numbers x and s,
$$ \begin{align} g(0,s)= g(0)=0, \end{align} $$
$$ \begin{align} x \leq g(x,s) \leq g(x+1,s) \; \& \; g(x,s) \leq g(x,s+1), \end{align} $$
and
$$ \begin{align} g(x,s) < g(x,s+1) \; \Rightarrow \; (D_{s+1} \upharpoonright g(x,s) \not= D_{s} \upharpoonright g(x,s) \; \& \; g(x,s+1)> s ). \end{align} $$
Proof of Claim 1 Since
$h \leq _T \emptyset '$
and D is not low
$_2$
, we may fix a function
$\hat {g} \leq _T D$
not dominated by h where w.l.o.g.
$\hat {g}$
is nondecreasing,
$\hat {g}(0)=0$
, and
$\hat {g}(x) \geq x$
for
$x \geq 0$
. Then there is a Turing functional
$\Gamma $
with use function
$\gamma $
such that
$\hat {g} = \Gamma ^D$
and such that, for any set X,
$\Gamma ^X(0) \downarrow $
,
$\Gamma ^X(0) = \gamma ^X(0)=0$
, and
$$ \begin{align} \Gamma^X(x) \downarrow \; \Rightarrow \; \forall x' \leq x ( \Gamma^X(x') \downarrow \; \& \; x' \leq \Gamma^X(x') \leq \gamma^X (x') \leq \gamma^X(x) ) \end{align} $$
for any number
$x \geq 0$
. Moreover, we may choose a computable enumeration
$\{\Gamma _s\}_{s \geq 0 }$
of
$\Gamma $
such that, for any set X,
$\Gamma ^X_0(0) \downarrow $
and
$$ \begin{align} \Gamma^X_s(x) \downarrow \; \Rightarrow \; \forall x' \leq x ( \Gamma^X_s(x') \downarrow \; \& \; \gamma^X (x') \leq s ) \end{align} $$
for any number x and any stage s.
It follows that, for the function
$u(x,s)$
defined by
$$ \begin{align*}u(x,s) = \mu u \geq s \; (\Gamma^{D_u}_u(x) \downarrow),\end{align*} $$
u is total and computable,
$u(0,s)=s$
for all numbers s, and
$$ \begin{align} x \leq u(x,s) \leq u(x+1,s) \; \& \; u(x,s) \leq u(x,s+1) \end{align} $$
and
$$ \begin{align} \forall x' \leq x (\Gamma^{D_{u(x,s)}}_{{u(x,s)}}(x') \downarrow). \end{align} $$
hold for all numbers x and s.
Now, for the definition of the functions
$g(x)$
and
$g(x,s)$
, we recursively define the binary function
$g(x,s)$
by letting
$$ \begin{align*}g(x,s) = \begin{cases} u(x,s) & \text{if }s=0 \text{ or } s>0 \text{ and}\\ & \exists x' \leq x \;( D_s \upharpoonright \gamma^{D_{g(x',s-1)}}(x') \not\subseteq D_{g(x',s-1)}), \\ g(x,s-1) & \text{otherwise}, \end{cases} \end{align*} $$
and we let
$$ \begin{align*}g(x) = \lim_{s \to \infty} g(x,s).\end{align*} $$
It remains to show that these functions have the required properties. Obviously the binary function
$g(x,s)$
is total and computable. Moreover, for any x and s,
$g(x,s) = u(x,t)$
for some
$t \leq s$
. In the following we let
$t^x_s$
be the least such number t.
Next we show that (15)–(17) hold.
For a proof of (15) it suffices to note that
$g(0,s)=g(0,0) = u(0,0) =0$
since
$\gamma ^{D_s}(0)=0$
for all numbers s.
The individual parts of (16) are shown as follows. The relation
$x \leq g(x,s)$
is immediate since
$x \leq u(x,t^x_s)$
by (20). For a proof of
$g(x,s) \leq g(x,s+1)$
w.l.o.g. assume that
$g(x,s) \not = g(x,s+1)$
. Then
$t^s_x \leq s$
and
$t^{s+1}_x = s+1$
, hence
$g(x,s) \leq g(x,s+1)$
by (20). The proof of
$g(x,s) \leq g(x+1,s)$
is by induction on s. If
$s=0$
then
$g(x,s) = u(x,s)$
and
$g(x+1,s)=u(x+1,s)$
, and the claim is immediate by (20). So fix
$s> 0$
. Since, by inductive hypothesis,
$g(x,s-1) \leq g(x+1,s-1)$
, w.l.o.g. we may assume that
$g(x, s) \not = g(x,s-1)$
or
$g(x+1, s) \not = g(x+1,s-1)$
. If the former holds then
$g(x,s)$
is defined according to the first case of the definition. But, by definition, this implies that
$g(x+1,s+1)$
is defined according to this case too, hence
$t^x_s = t^{x+1}_s=s$
. If the latter holds, then
$t^{x+1}_s = s$
while
$t^{x}_s \leq s$
. So, in either case, the claim follows by (20).
Finally, for a proof of (17), fix x and s such that
$g(x,s) < g(x,s+1)$
. Then, by definition, there is a number
$x' \leq x$
such that
$$ \begin{align} D_{s+1} \upharpoonright \gamma^{D_{g(x',s)}}(x') \not\subseteq D_{g(x',s)}. \end{align} $$
Then, in particular,
$g(x',s) \leq s$
. Moreover, by
$g(x',s) = u(x',t^{x'}_s)$
, and by (21),
$\Gamma ^{D_{g(x',s)}}_{g(x',s)}(x') \downarrow $
. Hence, by (19) and (16),
$\gamma ^{D_{g(x',s)}}(x') \leq g(x',s) \leq g(x,s)$
. So it suffices to show
$$ \begin{align} D_{s+1} \upharpoonright \gamma^{D_{g(x',s)}}(x') \not\subseteq D_{s}. \end{align} $$
For a contradiction assume that (23) fails. Then, by (22),
$g(x',s) < s$
, hence
$g(x',s) = g(x',s-1)$
, and
$$ \begin{align*}D_{s} \upharpoonright \gamma^{D_{g(x',s)}}(x') \not\subseteq D_{g(x',s)}. \end{align*} $$
But, by definition of g, this implies that
$g(x',s) = u(x',s) \geq s$
, a contradiction.
It remains to show that the unary function
$g(x)$
is total and that (14) and (13) hold. For this sake, by choice of
$\hat {g}$
and by (16), it suffices to show that, for given x, there is a stage
$s_x$
such that
$g(x,s) = g(x,s_x+1)$
for all
$s> s_x$
and
$\hat {g}(x) \leq g(x,s_x+1)$
.
Fix
$s^{\prime }_x$
such that, for any
$x' \leq x$
,
$\Gamma ^{D_{s^{\prime }_{x}}}(x')$
is defined and
$D_{s^{\prime }_x} \upharpoonright \gamma ^D(x') = D \upharpoonright \gamma ^D(x')$
. Then
$\Gamma ^{D_s}(x') = \Gamma ^D(x')$
and
$\gamma ^{D_s}(x') = \gamma ^D(x') \leq s^{\prime }_x$
for all numbers
$x' \leq x$
and
$s \geq s^{\prime }_x$
. So we may fix
$s_x \geq s^{\prime }_x$
such that
$D_{s_x} \upharpoonright m = D \upharpoonright m$
for
$m = \max \{\gamma ^{D_s}(x'): x' \leq x \; \& \; s \geq 0 \; \& \; \Gamma ^{D_s}(x') \downarrow \}$
. To show that
$g(x,s) = g(x,s_x+1)$
for
$s> s_x$
, for a contradiction fix
$s \geq s_x$
such that
$g(x,s+1) \not = g(x,s)$
. Then there is some
$x' \leq x$
such that
$D_{s+1} \upharpoonright \gamma ^{D_{g(x',s)}}(x')$
is not contained in
$D_{g(x',s)}$
. By choice of
$s_x$
this implies that
$g(x',s) < s_x$
. So, just as in the proof of (17), we may argue that
$g(x',s_x) = u(x',s_x) \geq s_x$
contrary to (16).
Finally, for a proof of
$\hat {g}(x) \leq g(x,s_x+1)$
, for a contradiction assume that
$g(x,s_x+1) < \hat {g}(x)$
. Note that, by definition of
$\Gamma $
and by choice of
$s_x$
,
$\hat {g}(x) = \Gamma ^D(x) = \Gamma ^{D_s}_s(x) \leq s$
for all
$s \geq s_x+1$
(where the last inequality holds by (18) and (19)). On the other hand, by definition of g,
$\Gamma ^{D_{g(x,s_x+1)}}_{g(x,s_x+1)}(x) \downarrow $
, hence (by (18) and (19))
$\Gamma ^{D_{g(x,s_x+1)}}(x) \leq \gamma ^{D_{g(x,s_x+1)}}(x) \leq g(x,s_x+1)$
. By assumption we may conclude that
$\Gamma ^{D_{g(x,s_x+1)}}(x) < \Gamma ^{D_{s_x+1}}(x)$
,
$g(x,s_x+1) < s_x+1$
, and
$D_{s_x+1} \upharpoonright \gamma ^{D_{g(x,s_x+1)}}(x) \not \subseteq {D_{g(x,s_x+1)}}$
(hence
$D_{s_x+2} \upharpoonright \gamma ^{D_{g(x,s_x+1)}}(x) \not \subseteq {D_{g(x,s_x+1)}}$
). It follows by definition of g that
$g(x,s_x+2) = u(x,s_x+2) \geq s_x+2> g(x,s_x+1)$
, a contradiction.
This completes the proof of Claim 1.⊣
For the remainder of the proof fix
$g(x)$
and
$g(x,s)$
as in Claim 1. We call a number x
$($
truly
$)$
good if
$h(x) < {g}(x)$
, and we call x good at stage s if
$h(x,s) < g(x,s)$
. Note that (by (13)) there are infinitely many truly good numbers x and, by (12) and (14), a number x is good iff it is good at infinitely many stages iff it is good at all sufficiently large stages. By the former we may inductively define good numbers
$x_n$
such that
$x_0$
is the least good number and
$x_{n+1}$
is the least good number
$> g(x_n)$
. (Note that, by
$h(0)=g(0)=0$
and by (8),
$1 \leq x_n \leq h(x_n) < g(x_n) < x_{n+1}$
—hence, in particular,
$n < x_n$
—for any number
$n \geq 0$
.) We will ensure that, for
$n = 2e+i$
,
$$ \begin{align} \overline{W} \cap [t_{x_n-1},g(x_n)) \subseteq X_i \end{align} $$
holds (where
$t_{x_n-1}$
is defined according to (3)). This implies that the requirements
$R_n$
are met as follows. Fix
$n= 2e+i$
. Then, by
$n < x_n$
and by (4),
$$ \begin{align*}e \leq n \leq x_n-1 < t_{x_n-1} < h(x_n),\end{align*} $$
and, by (6), there is a number
$x \in \overline {W}$
such that
$t_{x_n-1} \leq x < h(x_n)$
. Since, by goodness of
$x_n$
,
$h(x_n) < g(x_n)$
, (24) implies that
$x \in X_i$
. By
$e < t_{x_n-1} \leq x$
, this shows that
$R_n$
is met.
In order to achieve this, in the course of the construction we assign approximations of
$x_n$
to requirement
$R_n$
—called followers. At any stage
$s+1$
of the construction at which a new approximation
$x^{s+1}_n$
of
$x_n$
is assigned to
$R_n$
as follower we enumerate the numbers
$< g(x^{s+1}_n,s+1)$
which haven’t been put into
$X_0$
or
$X_1$
at previous stages into
$X_i$
(where
$n = 2e+i$
). We will argue that if a number in the interval
$[t_{x_n-1},g(x_n))$
has been previously put into
$X_{1-i}$
by some other requirement then, by the dump property, a later change of D will cause this number to enter D (hence W) whence this will not affect satisfaction of (24).
If it seems that an approximation is not correct or the corresponding g-value is not yet final then we cancel the follower as well as the existing lower priority followers (we say that we initialize
$R_n$
and the lower priority requirements) and we later assign a new follower. If defined, we let
$x^s_n$
denote the follower of
$R_n$
at the end of stage s (and we write
$x^s_n \uparrow $
otherwise). At any stage s there is a number
$m \geq 0$
such that the requirements
$R_n$
with
$n < m$
are the ones which have a follower, and
$1 \leq x^s_0 < x^s_1 < \dots < x^s_{m-1}$
(if
$m>0$
). For convenience, we let
$x^s_{-1} =0$
.
$X_{i,s}$
denotes the finite part of
$X_i$
enumerated by the end of stage s. The construction will ensure that
$X_{i,s} \subseteq \omega \upharpoonright s$
.
Using the above introduced notation, the formal construction is as follows.
-
Stage
$0$
is vacuous, i.e.,
$X_{0,s} = X_{1,s} = \emptyset $
and no requirement has a follower (i.e.,
$x^0_n \uparrow $
for
$n \geq 0$
).
-
Stage
$s+1$
. The stage consists of two steps.-
Step 1. For any requirement
$R_n$
which has a follower
$x^s_n$
at the end of stage s,
$R_n$
is initialized and
$x^s_n$
is cancelled if, for some number
$n' \leq n$
,
$x^s_{n'}$
is not good at stage
$s+1$
or there is a number
$x \leq x^s_{n'}$
such that
$g(x,s) < g(x,s+1)$
. -
Step 2. Requirement
$R_n$
requires attention via x if the following hold. -
(i)
$R_n$
is the highest priority requirement which does not have a follower after Step 1. -
(ii)
$x \geq 1$
and x is good at stage
$s+1$
, i.e.,
$h(x,s+1) < g(x,s+1)$
. -
(iii)
$x> g(x^s_{n-1},s+1)$
. -
(iv)
$g(x,s+1) \leq s+1$
.
$R_n$
requires attention then declare that
$R_n$
becomes active at stage
$s+1$
; for the least x such that
$R_n$
requires attention via x, appoint
$x^{s+1}_n = x$
as
$R_n$
-follower; and let where
$$ \begin{align*}\begin{array}{lll} X_{i,s+1} & = & X_{i,s} \cup \big( [0,g(x,s+1)) \setminus X_{1-i,s} \big),\\ X_{1-i,s+1} & = &X_{1-i,s}, \end{array}\end{align*} $$
$i=0$
if n is even and
$i=1$
if n is odd.
If no requirement requires attention, let
$X_{i,s+1}=X_{i,s}$
for
$i \leq 1$
. In any case, for any follower
$x^s_{n'}$
defined at the end of stage s and not cancelled in Step 1,
$x^{s+1}_{n'} = x^s_{n'}$
. -
-
In the remainder of the proof we will show that the sets
$X_0$
and
$X_1$
have the required properties. Obviously, the sets
$X_0$
and
$X_1$
are c.e. and disjoint. So it suffices to show that
$X_0 \cup X_1 = \omega $
and that the requirements
$R_n$
are met. In order to show this we prove a series of claims.
Claim 2. If
$x^s_n \downarrow $
then
$x^s_{n-1} \downarrow $
,
$x^s_n$
is the least number
$> g(x^s_{n-1},s)$
which is good at stage s, and
$g(x^s_n,s) \leq s$
. Hence, by (16) and (8),
$$ \begin{align} x^s_{n-1} \leq g(x^s_{n-1},s) < x^s_n \leq h(x^s_n,s) < g(x^s_n,s) \leq s. \end{align} $$
Proof The straightforward proof is by main induction on s and side induction on n.⊣
Next we show that any requirement
$R_n$
eventually obtains the good number
$x_n$
defined above as a permanent follower (i.e., there is a stage s such that
$x_n$
is appointed as
$R_n$
-follower at stage s and
$R_n$
is not initialized at any greater stage, hence
$x_n = x^{s'}_n$
for all
$s' \geq s$
). Recall that
$x_0$
is the least good number and
$x_{n+1}$
is the least good number greater than
$g(x_n)$
.
Claim 3.
$x_{n}$
is the permanent follower of requirement
$R_{n}$
.
Proof The proof is by induction on n. Fix n and assume the claim to be correct for
$n' < n$
. Fix
$s_0$
minimal such that the following hold.
-
(a) For any
$n' < n$
and any stage
$s \geq s_0$
,
$x_{n'}$
is the follower of
$R_{n'}$
at the end of stage s, i.e.,
$x_{n'} = x^s_{n'}$
. -
(b) For any
$x \leq x_{n}$
,
$h(x,s_0)= h(x)$
and
$g(x,s_0)=g(x) \leq s_0$
.
Then, for
$s \geq s_0$
,
$x_n$
is the least number
$> g(x_{n-1},s)$
which is good at stage s. So, if
$R_{n}$
has no follower at the end of stage
$s_0$
, then
$R_{n}$
requires attention at stage
$s_0+1$
and
$x_n$
becomes appointed. If
$R_n$
has a follower x at the end of stage
$s_0$
then
$x = x_n$
by Claim 2. In either case, it follows with (b) that
$R_{n}$
will not be initialized later. So the follower
$x_n$
is permanent.⊣
Note that, by Claim 3 and by (16), all numbers
$\leq x_n$
have entered
$X_0$
or
$X_1$
by the end of the first stage at which
$x_n$
becomes appointed as
$R_n$
-follower. So, by
$\lim _{n \to \infty } x_n = \omega $
,
$X_0 \cup X_1 = \omega $
. It remains to show that the requirements
$R_n$
are met. For this sake we first prove another auxiliary claim.
Claim 4. Let
$n \geq 1$
and let
$s_n$
be minimal such that no requirement
$R_{n'}$
with
$n' < n$
becomes active or is initialized after stage
$s_n$
. Then the following hold.
-
(A) For
$n' < n$
and
$s \geq s_n$
,
$x^s_{n'} = x_{n'}$
,
$x_{n'}$
is good at stage s, and
$g(x_{n'},s)= g(x_{n'}) \leq s_n$
. -
(B)
$x_{n-1}$
is appointed as
$R_{n-1}$
-follower at stage
$s_n$
. -
(C)
$x^{s_n}_n \uparrow $
. -
(D) For
$s \geq s_n$
,
$g(x',s)=g(x')$
for all
$x' \leq x_{n-1}$
and
$h(x',s) = h(x')$
and
$t^s_{x'} = t_{x'}$
for all
$x' < x_{n-1}$
$($
where
$t^s_{x'}$
and
$t_{x'}$
are defined in (7) and (3), respectively
$)$
. -
(E)
$X_{0,s_n} \cup X_{1,s_n} \subseteq \omega \upharpoonright g(x_{n-1})$
.
Proof For a proof of part (A), fix
$n' < n$
. By choice of
$s_n$
and by Claims 1 and 3,
$x^s_{n'} = x_{n'}$
and
$g(x_{n'},s) = g(x_{n'})$
for all stages
$s \geq s_n$
. The other items of (A) follow by Claim 2. Part (B) follows by minimality of
$s_n$
and by construction, and part (C) is immediate by (B). The first part of (D) is immediate by choice of
$s_n$
. For a proof of the second part, for a contradiction assume that there are numbers
$x' < x_{n-1}$
and
$s \geq s_n$
such that
$h(x',s) < h(x',s+1)$
or
$t^s_{x'} < t^{s+1}_{x'}$
. By (10) and by definition of
$t^s_{x'}$
this implies that
$W_{s+1} \upharpoonright h(x',s) \not = W_{s} \upharpoonright h(x',s)$
. (Namely, if
$h(x',s) < h(x',s+1)$
then this is immediate by (10); and if
$h(x',s) = h(x',s+1)$
and
$t^s_{x'} < t^{s+1}_{x'}$
then this follows by definition of
$t^s_{x'}$
.) So, by (11), we may conclude that
$t^{s+1}_{x'} \geq s+1$
, hence
$h(x'+1,s+1)> s+1$
by definition. Since
$x'+1 \leq x_{n-1}$
and since
$x_{n-1}$
is good this implies that
$g(x_{n-1})> s+1 > s_n$
contrary to (A).
This leaves (E). For a contradiction, assume that there is a number
$y \geq g(x_{n-1})$
such that
$y \in X_{0,s_n} \cup X_{1,s_n}$
. By (B), only numbers
$< g(x_{n-1})$
are enumerated into
$X_0$
and
$X_1$
at stage
$s_n$
. So there must be a stage
$s+1 < s_n$
, a requirement
$R_m$
, and a number x such that x becomes appointed as
$R_m$
-follower at stage
$s+1$
and
$y < g(x,s+1) \leq s+1$
.
Since
$g(x_{n-1},s+1) \leq g(x_{n-1}) \leq y$
, it follows that
$x_{n-1} < x$
. Moreover, by
$g(x_{n-1}) \leq y < s+1$
and by the second part of (17) (and by (16) and (14)),
$$ \begin{align} \forall x' \leq x_{n-1} (g(x',s+1) = g(x') < s+1). \end{align} $$
By goodness of
$x_{n'}$
this implies
$$ \begin{align} \forall n' \leq {n-1} (x_{n'} \text{ is good at all stages } \geq s+1). \end{align} $$
So, by Claim 2 (and by induction on
$n'$
),
$x^{s+1}_{n'} \leq x_{n'}$
if
$x^{s+1}_{n'}$
is defined
$(n' \leq n-1)$
. Since
$x_{n-1} < x = x^{s+1}_m$
, we may conclude that
$m \geq n$
and
$$ \begin{align*}\forall n' \leq n-1 (x^{s+1}_{n'} \downarrow \text{ and } x^{s+1}_{n'} \leq x_{n'}). \end{align*} $$
In fact,
$$ \begin{align} \forall n' \leq n-1 ( x^{s+1}_{n'}= x_{n'}). \end{align} $$
Namely, otherwise, fix
$n' \leq n-1$
minimal such that
$x^{s+1}_{n'} < x_{n'}$
. Then
$x^{s+1}_{n'}$
is good at stage
$s+1$
(since it is a follower) but not truly good (by (26) and by definition of
$x_{n'}$
). So
$h(x^{s+1}_{n'}, s+1) < h(x^{s+1}_{n'})$
, and—since
$x^{s+1}_{n'} < x_{n-1}$
—as in the proof of the second part of (D) we may argue that
$g(x_{n-1})> s+1$
contrary to (26).
Now, by (26)–(28), no requirement
$R_{n'}$
with
$n' < n$
becomes active or is initialized after stage
$s+1$
. By
$s+1 < s_n$
, this contradicts minimality of
$s_n$
.⊣
Claim 5. Requirement
$R_n$
is met.
Proof Fix
$n = 2e+i$
(
$e \geq 0, i \leq 1$
). Since
$R_{n+2}$
is stronger than
$R_n$
, w.l.o.g. we may assume that
$n \geq 1$
. We will show that (24) holds. Since
$e \leq n \leq x_n-1$
and since
$x_n$
is good, by (4) and (6) this guarantees that
$R_n$
is met.
Fix
$s_n$
and
$s_{n+1}$
(correspondingly defined for
$n+1$
in place of n) as in Claim 4. Then
$x^{s_n}_n \uparrow $
,
$x_n$
becomes assigned to
$R_n$
permanently at stage
$s_{n+1}$
(hence
$x_n = x^{s}_n$
for
$s \geq s_{n+1}$
), and
$$ \begin{align*}[t^{s_{n+1}}_{x_n-1},g(x_n, s_{n+1})) = [t_{x_n-1},g(x_n)).\end{align*} $$
By construction, this implies that all elements of
$[t_{x_n-1},g(x_n))$
which have not been put into
$X_0$
or
$X_1$
at a previous stage are enumerated into
$X_i$
at stage
$s_{n+1}$
. So it suffices to show that, for any number y,
$$ \begin{align} y \in X_{1-i,s_{n+1}-1} \cap [t_{x_n-1},g(x_n)) \; \Rightarrow \; y \in D. \end{align} $$
Fix y as in the premise of (29). Note that
$g(x_{n-1}) < t_{x_n-1}$
(since
$g(x_{n-1}) < x_n$
by definition of
$x_n$
and
$x_n-1 < t_{x_n-1}$
by (4)). Since
$R_n$
does not enumerate numbers into
$X_{1-i}$
, and since, by choice of
$s_n$
, no requirement
$R_{n'}$
where
$n' < n$
becomes active after stage
$s_n$
, it follows, by Claim 4(E), that there is a requirement
$R_m$
where
$m=2e'+(1-i)> n$
, a number x, and a stage
$s+1$
such that
$s_n < s+1 < s_{n+1}$
, x becomes appointed as
$R_m$
-follower at stage
$s+1$
, hence
$x = x^{s+1}_m$
, and
$$ \begin{align} y < g(x^{s+1}_m,s+1) \leq s+1 \; \& \; y \not\in X_{0,s} \cup X_{1,s}. \end{align} $$
Moreover,
$x^{s+1}_m$
is good at stage
$s+1$
, hence
$h(x^{s+1}_m,s+1) < g(x^{s+1}_m,s+1)$
.
By
$n < m$
and by construction,
$R_n$
has a follower
$x' < x$
at stage s and is not initialized at stage
$s+1$
. So
$x^{s+1}_n = x^s_n < x$
and
$g(x^s_{n},s+1) = g(x^s_{n},s)$
where, by
$s \geq s_n$
,
$x^s_{n-1} = x_{n-1}$
and
$g(x_{n-1}) = g(x_{n-1},s) < x^s_n$
. Now distinguish between the following cases.
Case 1:
$x^s_n < x_n$
. Then, by
$g(x_{n-1}) < x^s_n < x_n$
and by choice of
$x_n$
,
$x^s_n$
is not good but (by Claim 2)
$x^s_n$
is good at stage s. So there is a stage
$t \geq s+1$
such that
$h(x^s_n,t+1) \not = h(x^s_n,t)$
. By (10) and by (12) this implies
$W_t \upharpoonright h(x^s_n) \not = W \upharpoonright h(x^s_n)$
which in turn (by definition of
$t_{x_n-1}$
) implies that
$t_{x_n-1}> t$
. Since
$y \leq s+1 \leq t$
, this contradicts the choice of y. So this case cannot apply.
Case 2:
$x^s_n> x_n$
. Then, by Claim 2,
$x_n$
is not good at stage
$s+1$
. Since
$x_n$
is good, it follows that there is a stage
$t \geq s+1$
such that
$g(x_n,s+1) = g(x_n,t) < g(x_n,t+1)$
. So, by (17) and by the dump property (2),
$$ \begin{align} [g(x_n,s+1), s+1] \subseteq D. \end{align} $$
On the other hand, since
$x_n < x^s_n < x$
,
$x^s_n$
is follower of
$R_n$
at stage
$s+1$
and x is follower of
$R_m$
at stage
$s+1$
, it holds that
$g(x_n,s+1) < g(x^s_n,s+1) = g(x^s_n,s)$
and all numbers
$ < g(x^s_n,s)$
are in
$X_{0,s} \cup X_{1,s}$
. So, by the second part of (30),
$g(x_n,s+1) \leq y < s+1$
whence
$y \in D$
by (31).
Case 3:
$x^s_n = x_n$
. Since
$s+1 < s_{n+1}$
,
$R_n$
becomes initialized after stage
$s+1$
. Since
$x_n$
is good, this implies that there is a stage
$t \geq s+1$
such that
$g(x_n,s+1) = g(x_n,t) < g(x_n,t+1)$
. But then we may argue as in Case 2 that
$y \in D$
.
This completes the proof of Claim 5 and the proof of the theorem.⊣
Acknowledgment
Downey thanks the Marsden Fund of New Zealand.
This paper is derived from research whilst Downey was at the University of Heidelberg under the auspices of an Alexander von Humboldt Research Award.
Proofs of (8)–(12)
Proof of (8)
The strict inequalities are immediate by definition. So, in particular,
$h(x,s)$
is strictly increasing in the first argument, hence
$x \leq h(x,s)$
.⊣
Proof of (9)
The proof is by induction on x. Fix x and s and assume the claim to be true for all numbers less than x. For the proof of the first part, we may assume that
$x> 0$
since
$h(0,s)=0$
for all stages s. Note that
$t^s_{x-1} \leq t^{s+1}_{x-1}$
by inductive hypothesis and
$\overline {W_{s+1}} \subseteq \overline {W_s}$
. So, for any number
$s'> t^{s+1}_{x-1}$
, it holds that
$s'> t^s_{x-1}$
and
$$ \begin{align*}\overline{W_{s+1}} \cap [t^{s+1}_{x-1},s') \subseteq \overline{W_{s}} \cap [t^{s}_{x-1},s').\end{align*} $$
But this implies
$h(x,s) \leq h(x,s+1)$
by definition. For a proof of the second part, note that, by the first part and by
$W_s \subseteq W_{s+1}$
,
$h(x,s) \leq h(x,s+1)$
and
$W_s \upharpoonright h(x,s) \subseteq W_{s+1} \upharpoonright h(x,s+1)$
. So
$t^s_x \leq t^{s+1}_x$
by definition.⊣
Proof of (10)
The proof is by induction on x. Fix x and assume that
$h(x,s) \not = h(x,s+1)$
hence
$h(x,s) < h(x,s+1)$
by (9). Then
$x>0$
and, by (8) and inductive hypothesis, we may assume that
$W_{s+1} \upharpoonright h(x-1,s) = W_{s} \upharpoonright h(x-1,s)$
and
${h(x-1,s)} = h(x-1,s+1)$
. It follows that
$t^s_{x-1} = t^{s+1}_{x-1}$
hence
$[t^s_{x-1}, h(x,s)) = [t^{s+1}_{x-1},h(x,s))$
. By
$h(x,s) < h(x,s+1)$
and by definition of
$h(x,s+1)$
this implies that
$\overline {W_{s+1}} \cap [t^s_{x-1},h(x,s)) = \emptyset $
. On the other hand, by definition of
$h(x,s)$
,
$\overline {W_{s}} \cap [t^s_{x-1},h(x,s)) \not = \emptyset $
. So
$W_{s+1} \upharpoonright h(x,s) \not = W_{s} \upharpoonright h(x,s)$
.⊣
Proof of (11)
Assume that
$W_{s+1} \upharpoonright h(x,s) \not = W_{s} \upharpoonright h(x,s)$
. Then, by
$h(x,s) \leq h(x,s+1)$
,
$W_{s+1} \upharpoonright h(x,s+1) \not \subseteq W_{t} \upharpoonright h(x,s+1)$
for all
$t \leq s$
. So
$t^{s+1}_x \geq s+1$
by definition.⊣
Proof of (12)
The proof is by induction on x. Given x, by (9) it suffices to show that
$h(x,s)=h(x)$
and
$t^s_x = t_x$
for all sufficiently large s. If
$x = 0$
then this is immediate since
$h(0,s) =0 = h(0)$
and
$t^s_0 = 1 = t_0$
for all stages s. So we may assume that
$x>0$
and, by inductive hypothesis, we may fix a stage
$s_0$
such that
$h(x-1,s) = h(x-1)$
,
$t^s_{x-1} = t_{x-1}$
, and
$W_s \upharpoonright u+1 = W \upharpoonright u+1$
for all
$s \geq s_0$
where u is minimal such that
$u \geq t_{x-1}$
and
$u \not \in W$
. Then, for
$s \geq s_0$
,
$h(x,s) = u+1 = h(x)$
. Moreover, for the least stage
$t> h(x)$
such that
$W_t \upharpoonright h(x) = W \upharpoonright h(x)$
,
$t^s_x = t = t_x$
for all stages
$s \geq \max \{s_0,t\}$
.⊣
