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

DOI10.1016/J.APAL.2016.11.005zbMATH Open1422.03086DBLPjournals/apal/Shafer17OpenAlexW2962938955WikidataQ57948749 ScholiaQ57948749MaRDI QIDQ515565FDOQ515565

Authors: Paul Shafer 

Publication date: 16 March 2017

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

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$.

Full work available at URL: https://arxiv.org/abs/1604.06592

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)