On the Kleene Degrees of $\Pi^1_1$ Sets
Slaman, Theodore A.
J. Symbolic Logic, Tome 51 (1986) no. 1, p. 352-359 / Harvested from Project Euclid
Let $A$ and $B$ be subsets of the reals. Say that $A_\kappa \geq B$, if there is a real $a$ such that the relation $"x \in B"$ is uniformly $\Delta_1 (a, A)$ in $L\lbrack \omega^{x,a,A}_1, x,a,A\rbrack$. This reducibility induces an equivalence relation $\equiv_\kappa$ on the sets of reals; the $\equiv_\kappa$-equivalence class of a set is called its Kleene degree. Let $\mathscr{K}$ be the structure that consists of the Kleene degrees and the induced partial order $\mathscr{K} \geq$. A substructure of $\mathscr{K}$ that is of interest is $\mathscr{P}$, the Kleene degrees of the $\Pi^1_1$ sets of reals. If sharps exist, then there is not much to $\mathscr{P}$, as Steel [9] has shown that the existence of sharps implies that $\mathscr{P}$ has only two elements: the degree of the empty set and the degree of the complete $\Pi^1_1$ set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in $\mathscr{P}$; in the context of $V = L$, Hrbacek has shown that $\mathscr{P}$ is dense and has no minimal pairs. The Hrbacek results led Simpson [6] to make the following conjecture: if $V = L$, then $\mathscr{p}$ forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if $V = L$, then Godel's maximal thin $\Pi^1_1$ set is the infimum of two strictly larger elements of $\mathscr{P}$. The second main result deals with the notion of jump in $\mathscr{K}$. Let $A'$ be the complete Kleene enumerable set relative to $A$. Say that $A$ is low-$n$ if $A^{(n)}$ has the same degree as $\varnothing^{(n)}$, and $A$ is high-$n$ if $A^{(n)}$ has the same degree as $\varnothing^{(n + 1)}$. Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete $\Pi^1_1$ set in $L$. They have also shown that various other $\Pi^1_1$ sets are neither high nor low in $L$. Legrand [5] extended their results by showing that, if there is a real $x$ such that $x^{\tt\#}$ does not exist, then there is an element of $\mathscr{P}$ that, for all $n$, is neither low-$n$ nor high-$n$. In $\S 2$, ZFC is used to show that, for all $n$, if $A$ is $\Pi^1_1$ and low-$n$ then $A$ is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp].
Publié le : 1986-06-14
Classification: 
@article{1183742100,
     author = {Slaman, Theodore A.},
     title = {On the Kleene Degrees of $\Pi^1\_1$ Sets},
     journal = {J. Symbolic Logic},
     volume = {51},
     number = {1},
     year = {1986},
     pages = { 352-359},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742100}
}
Slaman, Theodore A. On the Kleene Degrees of $\Pi^1_1$ Sets. J. Symbolic Logic, Tome 51 (1986) no. 1, pp.  352-359. http://gdmltest.u-ga.fr/item/1183742100/