Bounded low and high sets

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

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,227

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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
2017-08-04

Downloads
23 (#685,787)

6 months
8 (#370,225)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
Computability Theory.Barry Cooper - 2010 - Journal of the Indian Council of Philosophical Research 27 (1).
A Refinement of Low n_ and High _n for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Mathematical Logic Quarterly 32 (1-5):5-12.
A Refinement of Low n and High n for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Mathematical Logic Quarterly 32 (1‐5):5-12.

View all 8 references / Add more references