On the decidability of the _2 theories of the arithmetic and hyperarithmetic degrees as uppersemilattices

DOI10.1017/JSL.2017.51MaRDI QIDQ4600467zbMATH OpenOpenAlexFDO

Authors James S. Barnes

Publication date 11 January 2018

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

arithmetic degreesdegree theoryhyperarithmetic degreesKumabe-Slaman forcingrecursion theory

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: We establish the decidability of the $Sigm{a}_2$ theory of both the arithmetic and hyperarithmetic degrees in the language of uppersemilattices i.e. the language with $leq,0$ and $sqcup$. This is achieved by using Kumabe-Slaman forcing - along with other known results - to show that given finite uppersemilattices $mathcalM$ and $mathcalN$, where $mathcalM$ is a subuppersemilattice of $mathcalN$, then for both degree structures, every embedding of $mathcalM$ into the structure extends to one of $mathcalN$ iff $mathcalN$ is an end-extension of $mathcalM$.

Recommendations

• On the Σ₂-theory of the upper semilattice of Turing degrees
• Embedding jump upper semilattices into the Turing degrees
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
• Decidability and Invariant Classes for Degree Structures
• Lattice initial segments of the hyperdegrees

Cites work

• Computable structures and the hyperarithmetical hierarchy
• Defining the Turing jump
• Forcing and reducibilities
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• Lattice initial segments of the hyperdegrees
• On the Σ₂-theory of the upper semilattice of Turing degrees

Cited in

(4)

• Elementary theories and hereditary undecidability for semilattices of numberings
• The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable
• Lattice initial segments of the hyperdegrees
• On the Σ₂-theory of the upper semilattice of Turing degrees

This page was built for publication: On the decidability of the \(\Sigma_2\) theories of the arithmetic and hyperarithmetic degrees as uppersemilattices

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