Honest elementary degrees and degrees of relative provability without the cupping property

DOI10.1016/J.APAL.2016.11.005MaRDI QIDQ515565zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paul Shafer

Publication date 16 March 2017

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.06592, http://eprints.whiterose.ac.uk/111927/1/ShaferNoCupping.pdf

zbMATH Keywords

degrees of relative provabilityhonest elementary degreessub-recursive hierarchies

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Recursive functions and relations, subrecursive hierarchies (03D20) Logical aspects of lattices and related structures (03G10) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: An element $a$ of a lattice cups to an element $b>a$ if there is a $c<b$ such that $acupc=b$. An element of a lattice has the cupping property if it cups to every element above it. We prove that there are non-zero honest elementary degrees that do not have the cupping property, which answers a question of Kristiansen, Schlage-Puchta, and Weiermann. In fact, we show that if $mathbfb$ is a sufficiently large honest elementary degree, then there is a non-zero honest elementary degree $mathbfa{<}_{mathrmE}mathbfb$ that does not cup to $mathbfb$. For comparison, we modify a result of Cai to show that in several versions of the related degrees of relative provability the preceding property holds for all non-zero $mathbfb$, not just sufficiently large $mathbfb$.

Recommendations

• On the structure of the degrees of relative provability
• Degrees of relative provability
• Degrees of insolubility of extensions of arithmetic by true propositions
• Cupping and definability in the local structure of the enumeration degrees
• Good degree bounds on Nullstellensatz refutations of the induction principle
• Intuitionistic logic and Muchnik degrees
• Cauchy completeness in elementary logic
• Elementary proofs of Kempe universality
• scientific article; zbMATH DE number 4061229
• Provability logic without Craig's interpolation property

Cites work

• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1144041 (Why is no real title available?)
• scientific article; zbMATH DE number 1507242 (Why is no real title available?)
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• A Classification of the Recursive Functions
• A jump operator on honest subrecursive degrees
• Augmented loop languages and classes of computable functions
• Degrees of relative provability
• Degrees of total algorithms versus degrees of honest functions
• Induction rules, reflection principles, and provably recursive functions
• On the density of honest subrecursive classes
• On the induction schema for decidable predicates
• On the structure of the degrees of relative provability
• Provability algebras and proof-theoretic ordinals. I
• Streamlined subrecursive degree theory
• Subrecursive degrees and fragments of Peano arithmetic
• The honest subrecursive classes are a lattice
• Unprovability and proving unprovability

Cited in

(2)

• Properness Without Elementaricity
• Degrees of relative provability

This page was built for publication: Honest elementary degrees and degrees of relative provability without the cupping property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515565)