0
$\begingroup$

I'm sure i have read that the following (or something that implies this) is true

Let $X$ be a $\Pi_1^0$ class with top Medvedev degree. Then for every $x\in X$, there is $y\in X$ with $y<_T x$.

But i don't remember where. If this is true, do you know where can I find this or a similar statement?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

We can modify the proof of the Kreisel/Shoenfield basis theorem (see Theorem 3.7 in Diamondstone/Dzhafarov/Soare):

Let $T\subseteq 2^{<\omega}$ be an infinite binary tree all of whose paths are of PA-degree (this is equivalent to $[T]$, the set of paths through $T$, having top Medvedev degree amongst $\Pi^0_1$ classes). Fix a path $f\in [T]$; we want to find a path $g\in [T]$ with $g<_Tf$.

Consider the following computable $4$-ary tree $S$: a node on $S$ of length $n$ consists of a pair $(\alpha,\beta)$ where $\alpha$ is a node on $T$ of length $n$ and $\beta$ is a binary string of length $n$ such that for each $e<i$ it is not the case that $\Phi_e^\alpha(e)[n]\downarrow=\beta(n)$. Clearly $S$ is infinite, so $S$ has a path $h=(h_0,h_1)\le_Tf$. But $h_0$ is a path through $T$ such that $h_0\not\ge_Th_1$, and since $(h_0,h_1)\le_Tf$ we have that $h_0\not\ge_Tf$.

$\endgroup$

You must log in to answer this question.

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