A question about the non-transitivity of $\leq_{w\alpha}$

29 Views Asked by At

A very natural question when reading about $\alpha$-recursion theory is why and when the weak $\alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The Irregular and Non-Hyperregular $\alpha$-r.e. Degrees by Shore, in theorem $3.1$. Unfortunately, the characterization he gives for the ordinals such that the reducibility fails to be transitive relies on the existence of a complete $\alpha$-r.e. set $A$ such that $\forall X(A\leq_{w\alpha}X\leftrightarrow A\leq_\alpha X)$. The book by Sacks is given as a reference, but I am unable to locate the result, or to see how this is implied by the others in the book (the main reason is that Shore gives §25 as the number of the chapter where to find this result, but there is no such chapter in the book, probably because it still hadn't bee published by that time). Could anyone explain to me why a set $A$ as above exists, or point me to a proof?

1

There are 1 best solutions below

0
On BEST ANSWER

okay, false alarm: I was being misled by the requirement that $A$ had to be complete. The result I was trying to prove actually holds for every $\alpha$-r.e. set $A$ (and maybe also for other sets): it is enough to consider a slight modification of the set $A$, say $A^*:=\{\delta<\alpha: K_\delta\cap A\neq\emptyset\}$ (this is actually in Sacks' book, so my bad for checking poorly). For every set $B$, clearly $A^*\leq_{w\alpha}B\rightarrow A\leq_{\alpha} B$, and since $A=_\alpha A^*$ we are done.