Archive for Mathematical Logic 56 (5-6):507-521 (2017)

Abstract
Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the Jump Theorem holds for the bounded jump: do we have A≤bTB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \le _{bT}B$$\end{document} if and only if Ab≤1Bb\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A^b \le _1 B^b$$\end{document}? We show the forward direction holds but not the reverse.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
ISBN(s)
DOI 10.1007/s00153-017-0537-8
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,564
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

A Refinement of Lown and Highn for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 32 (1-5):5-12.
A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.

View all 8 references / Add more references

Citations of this work BETA

Effective Domination and the Bounded Jump.Keng Meng Ng & Hongyuan Yu - 2020 - Notre Dame Journal of Formal Logic 61 (2):203-225.
Bounded-Low Sets and the High/Low Hierarchy.Huishan Wu - 2020 - Archive for Mathematical Logic 59 (7-8):925-938.

Add more citations

Similar books and articles

Classes Bounded by Incomplete Sets.Kejia Ho & Frank Stephan - 2002 - Annals of Pure and Applied Logic 116 (1-3):273-295.
A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.
The Structure of Amorphous Sets.J. K. Truss - 1995 - Annals of Pure and Applied Logic 73 (2):191-233.
Returning to Semi-Bounded Sets.Ya'acov Peterzil - 2009 - Journal of Symbolic Logic 74 (2):597-617.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Exact Pairs for Abstract Bounded Reducibilities.Wolfgang Merkle - 1999 - Mathematical Logic Quarterly 45 (3):343-360.
Finiteness Classes and Small Violations of Choice.Horst Herrlich, Paul Howard & Eleftherios Tachtsis - 2016 - Notre Dame Journal of Formal Logic 57 (3):375-388.
A Maximal Bounded Forcing Axiom.David Asperó - 2002 - Journal of Symbolic Logic 67 (1):130-142.
On Existence of Complete Sets for Bounded Reducibilities.Valeriy Bulitko & Vadim Bulitko - 2003 - Mathematical Logic Quarterly 49 (6):567-575.
Dominating and Unbounded Free Sets.Slawomir Solecki & Otmar Spinas - 1999 - Journal of Symbolic Logic 64 (1):75-80.
A Cohesive Set Which is Not High.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
Arithmetical Measure.Sebastiaan A. Terwijn & Leen Torenvliet - 1998 - Mathematical Logic Quarterly 44 (2):277-286.

Analytics

Added to PP index
2017-08-04

Total views
14 ( #737,950 of 2,533,568 )

Recent downloads (6 months)
1 ( #390,861 of 2,533,568 )

How can I increase my downloads?

Downloads

My notes