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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.