Index sets related to prompt simplicity (Q1115863): Difference between revisions

The index sets are a field of special interest in recursion theory. Many results were obtained and there are also many open problems. The author investigates the index sets concerning promptly simple sets which were introduced in a paper of \textit{K. Ambos-Spies, C. Jockusch, R. Shore} and \textit{R. Soare} [Trans. Am. Math. Soc. 281, 109-128 (1984; Zbl 0539.03020)]. They proved that such degrees form a complement to the cappable degrees (degree \(\underset \tilde{} a\) is cappable if \(\underset \tilde{} a=\underset \tilde{} 0\) or \(\underset \tilde{} a\) is one half of a minimal pair) in the semilattice of r.e. T-degrees. Let PrSim be the index set \(\{\) x: \(W_ x\) is promptly simple\(\}\) and PrSimDg be \(\{\) x: T-degree of \(W_ x\) contains a promptly simple set\(\}\). Theorem. The index sets PrSim and PrSimDg are 1-complete in the class \(\Sigma_ 4\) of the arithmetic hierarchy. The tree version of the \(\underset \tilde{} 0''\)-priority method is used in the proof of the theorem.