On the Kleene degrees of <i>Π</i><sub>1</sub><sup>1</sup> sets (Q3029002)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4016893
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the Kleene degrees of <i>Π</i><sub>1</sub><sup>1</sup> sets |
scientific article; zbMATH DE number 4016893 |
Statements
On the Kleene degrees of <i>Π</i><sub>1</sub><sup>1</sup> sets (English)
0 references
1986
0 references
Borel sets
0 references
Kleene degrees
0 references
\(V=L\)
0 references
jump
0 references
0.797984778881073
0 references
0.7910662889480591
0 references
0.7879080772399902
0 references
0.7747642397880554
0 references
0.7747639417648315
0 references
Let A and B be subsets of the reals. Say that \(A_ K\geq B\), if there is a real a such that the relation ``x\(\in B''\) is uniformly \(\Delta_ 1(a,A)\) in \(L[\omega_ 1^{x,a,A},x,a,A]\). This reducibility induces an equivalence relation \(\equiv_ K\) on the sets of reals; the \(\equiv_ K\)-equivalence class of a set is called its Kleene degree. Let \({\mathcal K}\) be the structure that consists of the Kleene degrees and the induced partial order \(_{{\mathcal K}}\geq\). A substructure of \({\mathcal K}\) that is of interest is \({\mathcal P}\), the Kleene degrees of the \(\Pi^ 1_ 1\) sets of reals. If sharps exist, then there is not much to \({\mathcal P}\), as \textit{J. R. Steel} [Fundam. Math. 108, 83-88 (1980; Zbl 0463.03028)] has shown that the existence of sharps implies that \({\mathcal P}\) has only two elements: the degree of the empty set and the degree of the complete \(\Pi^ 1_ 1\) set. \textit{S. Legrand} [The Borel analogue of the Friedberg-Muchnik result (to appear)] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in \({\mathcal P}\); in the context of \(V=L\), Hrbáček has shown that \({\mathcal P}\) is dense and has no minimal pairs. The Hrbáček results led \textit{S. G. Simpson} [Logic, Methodology and Philosophy of Science VI, Proc. 6th Int. Congr., Hannover 1979, Stud. Logic Found. Math. 104, 263-270 (1982; Zbl 0525.03033)] to make the following conjecture: if \(V=L\), then \({\mathcal 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 Gödel's maximal thin \(\Pi^ 1_ 1\) set is the infimum of two strictly larger elements of \({\mathcal P}.\) The second main result deals with the notion of jump in \({\mathcal 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 \(\emptyset^{(n)}\), and A is high-n if \(A^{(n)}\) has the same degree as \(\emptyset^{(n+1)}\). \textit{S. G. Simpson} and \textit{G. Weitkamp} [J. Symb. Logic 48, 356-368 (1983; Zbl 0529.03018)] 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. \textit{S. Legrand} [A type 2 version of a question of Sacks (to appear)] extended their results by showing that, if there is a real x such that \(x^{\#}\) does not exist, then there is an element of \({\mathcal 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 the paper of Simpson and Weitkamp [loc. cit.].
0 references