2
$\begingroup$

Is there a $\Pi^0_2$ singleton that forms a minimal pair with $0''$? That is, is there a set $X$ such that $X$ is the unique solution to $\forall x \exists y \phi(X|_y, x)$, $X$ and $0''$ are incomparable and if $Y \leq_T 0'' \land Y \leq_T X$ then $Y \leq_T 0$.

For some motivation, note that the most common examples of $\Pi^0_2$ singletons are the $\alpha$-REA sets. Because every $\alpha$-REA set is built up in uniform r.e. sets no $\alpha$-REA set forms a minimal pair with $0''$ (induction and use $0''$ at limit stages to convert r.e. indexes to recursive ones).

Even Harrington's construction of a $\Pi^0_2$ singleton not of $\omega$-REA degree builds the $\Pi^0_2$ singleton by stitching together a part that is built computably in $0'$ with parts built computably in $0''$, $0'''$ and so on.

So it's an attractive hypothesis to think that, in some sense, every $\Pi^0_2$ singleton is somehow built up in pieces analagous to the $\omega$-REA situation. I suspect it's false but don't have a proof.

$\endgroup$
1
  • $\begingroup$ The answer is yes. You may find it in Harrington's "Mclaughlin’s conjecture". – $\endgroup$
    – 喻 良
    Commented May 21, 2023 at 12:45

1 Answer 1

4
$\begingroup$

Maybe I should give a more detailed answer.

Harrington proved (or claimed) the following result in his handwritten draft.

Theorem There is a $\Pi^0_2$-singleton $x$ so that $\forall n<\omega (x^{(n)}\equiv_T x\oplus \emptyset^{(n)}\wedge \forall m\geq n \forall z (z\leq_T x^{(n)}\wedge z\leq_T \emptyset^{(m)}\implies z\leq_T \emptyset^{(n)}))$.

An immediate conclusionis that there is a $\Pi^0_2$-singleton which forms a minimal pair with $\emptyset^{(n)}$ forall $n<\omega$.

$\endgroup$
1
  • $\begingroup$ Ahh, right I forgot about that part of the result. Thanks! $\endgroup$ Commented May 21, 2023 at 17:05

You must log in to answer this question.

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