2
$\begingroup$

Recall that $M\subseteq\omega$ is maximal if it is c.e., and can be only trivially extended by other c.e. sets, i.e. if $M\subseteq N$ and $N$ is c.e., then either $\overline{N}$ or $N\setminus M$ is finite. Similarly say a set $M$ is $A$-maximal if it is $A$-c.e. and only trivially extended by other $A$-c.e. sets.

I am interested in sets $A$ such that all $A$-maximal sets are $\Delta^0_2$. If $A$ has this property, then relativizing Yates' construction of a complete maximal set gives an $A$-maximal $M$ with $M\oplus A\equiv_T A'$, so that $A$ is $\mathrm{GL}_1$.

Thus among $A\in\Delta^0_2$, the sets with this property are exactly the low ones - one direction is above, and for the reverse, if $A$ is low then all $A$-c.e. sets are $\Delta^0_2$.

My question is - is this property enjoyed by any non-$\Delta^0_2$ set?

By Martin's high domination theorem, this condition is equivalent to asking for a set $A$ such that all $A$-high, $A$-c.e. sets are $\Delta^0_2$ and high, i.e. if $B\in\Sigma^0_1(A)$ and $(B\oplus A)'\equiv_T A''$, then $B\in\Delta^0_2$ and $B'\equiv_T \emptyset''$. Edit: My understanding of the relativization of Martin's result was incorrect (thanks to Emma Harper on Twitter for spotting this!). The correct statement is that if a set $B$ is $A$-c.e. and $A$-high, there is an $A$-maximal $M$ with $M\oplus A\equiv_T B\oplus A$, so what I struck through is not obviously equivalent to the property I am concerned with. Indeed, it does not hold outside of the $\Delta^0_2$ degrees, as Noah correctly points out below.

My suspicion is that this requirement is too strong, that if $A\not\in\Delta^0_2$ some $A$-maximal real will always fail to be in $\Delta^0_2$. But I do not have a proof, nor can I rule out that some 'weak' set (like a hyperimmune-free or a bi-immune-free) might somehow have this property.

$\endgroup$
11
  • 1
    $\begingroup$ If $B\ge_TA$ is $A$-c.e. and $A$-high (so just relativize the usual high c.e. construction to $A$) we must have $B\not\in\Delta^0_2$ since $\Delta^0_2$ is closed downwards. Or am I misunderstanding your question? $\endgroup$ Commented Mar 12, 2022 at 2:15
  • 1
    $\begingroup$ Sure, but I'm saying we can always construct an $A$-high $A$-c.e. which is itself above $A$. $\endgroup$ Commented Mar 12, 2022 at 2:30
  • 1
    $\begingroup$ @NoahSchweber but how do you make it above $A$? $\endgroup$ Commented Mar 12, 2022 at 3:12
  • 1
    $\begingroup$ @BjørnKjos-Hanssen If $B$ is $A$-c.e. and $A$-high, then so is $B\oplus A$, right? (Or: just start the usual construction of an $A$-high $A$-c.e. set but with $A$ itself "pre-coded" into one of the rows of the set you're building. This should amount to the same thing I think.) $\endgroup$ Commented Mar 12, 2022 at 3:15
  • 1
    $\begingroup$ @NoahSchweber if $A$ is precoded then that conflicts with maximality does it not? $\endgroup$ Commented Mar 12, 2022 at 3:18

1 Answer 1

0
$\begingroup$

Turns out (as I suspected!) all such sets are $\Delta^0_2$, so that this property exactly characterizes lowness.

Fix an $A$-maximal $M$. For any $B\leq_T A$, one can build $C = \overline{M}\oplus_B\emptyset = \{n \mid p_B(n)\in\overline{M}\}$. Then any $W_e^A$ you might wish to intersect with $C$ can be transformed into a $W_{f(e)}^A$ (to be intersected with $\overline{M}$) by putting $n$ into $W_{f(e)}^A$ whenever $p_B(n)$ enters $W_e^A$.

Now the $A$-cohesiveness of $\overline{M}$ carries over nicely to $C$, since $|W_e^A\cap C| = |W_{f(e)}^A\cap\overline{M}|$ (and similarly for $\overline{W_e^A}$). So since $\overline{C}$ is $A$-c.e. and $A$-cohesive, it is $A$-maximal and thus $\Delta^0_2$.

Finally any $B\leq_T A$ has a $\Delta^0_2$ subset, which happens only when $A\in\Delta^0_2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .