Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability
type: Item
instance of: scholarly article
title: Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability
zbMATH Open document ID: 1267.03047
author: Noam Greenberg
author: Rodney G. Downey
published in: Advances in Mathematics
publication date: 2013-04-16T00:00:00Z
review text: Pseudo-jump operators are important in the study of the properties of the partially ordered structure \({\mathcal D}\) of the Turing degrees. They were introduced in [\textit{C. G. Jockusch jun.} and \textit{R. A. Shore}, Trans. Am. Math. Soc. 275, No. 2, 599--609 (1983; Zbl 0514.03028)] in order to approach the question of the definability of \({\mathbf 0}'\) in \({\mathcal D}\). This idea was right, because later, \textit{R. A. Shore} and \textit{T. A. Slaman} [Math. Res. Lett. 6, No. 5--6, 711--722 (1999; Zbl 0958.03029)] solved the question using pseudo-jump operators. For every \(e\in N\), the \(e\)-th pseudo-jump operator is the map \(J_e:2^{\omega}\rightarrow 2^{\omega}\) such that \(J_e(A):=A\oplus W_e^A\). Such operators are also known in the literature as 1-REA operators [\textit{C. G. Jockusch jun.} and \textit{R. A. Shore}, J. Symb. Log. 49, No. 4, 1205--1236 (1984; Zbl 0574.03026)]. In the paper under review, the authors prove the following main result: (1) There is a pseudo-jump operator, increasing on all sets, which cannot be inverted while avoiding any prescribed upper cone. It has been an open problem whether or not (1) was true for pseudo-jump operators increasing on all sets. Previously, (1) was proved in [\textit{R. Coles} et al., Ann. Pure Appl. Logic 136, No. 3, 297--333 (2005; Zbl 1085.03031)] for pseudo-jump operators increasing on c.e. sets. The strategy employed in this paper is to prove first the following result: (2) There is a noncomputable c.e. set which is computable from every strongly jump-traceable hard c.e. set. Then, they apply (2) to \textit{ultrahigh sets}, which were introduced in [\textit{K. M. Ng}, J. Symb. Log. 73, No. 1, 309--342 (2008; Zbl 1168.03031)]. A set \(B\) is strongly jump-traceable hard if \(\emptyset '\leq_{\mathrm{SJT}}B\), where the reducibility \(\leq_{\mathrm{SJT}}\) is defined in terms of strong jump-traceability, the latter having been introduced by \textit{S. Figueira} et al. [Ann. Pure Appl. Logic 152, …
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 6154621
zbMATH Keywords: pseudo-jump operators
zbMATH Keywords: computably enumerable degrees
zbMATH Keywords: strong jump-traceability
reviewed by: Patrizio Cintioli
MaRDI profile type: Publication
full work available at URL: j.aim.2012.12.018
OpenAlex ID: W2009037069
DOI: 10.1016/J.AIM.2012.12.018
Recommended article: STRONG JUMP-TRACEABILITY
Recommended article: Limits on jump inversion for strong reducibilities
Recommended article: Another Jump Inversion Theorem for Structures
Recommended article: Strong jump-traceability. II: \(K\)-triviality
Recommended article: Inverse pseudo orbit tracing property for robust diffeomorphisms
Recommended article: Inherent enumerability of strong jump-traceability
Recommended article: Strong polyhedral approximation of simple jump sets
Recommended article: Beyond strong jump traceability
Recommended article: Strong jump-traceability. I: The computably enumerable case
Recommended article: A jump inversion theorem for the enumeration jump
description: scientific article; zbMATH DE number 6154621