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

DOI10.1017/JSL.2017.51zbMATH Open1391.03031arXiv1606.07392OpenAlexW2963134242MaRDI QIDQ4600467FDOQ4600467

Authors: James S. Barnes 

Publication date: 11 January 2018

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

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

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

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

zbMATH Keywords

degree theoryrecursion theoryarithmetic degreeshyperarithmetic degreesKumabe-Slaman forcing

Mathematics Subject Classification ID

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

Cites Work

• Computable structures and the hyperarithmetical hierarchy
• Title not available (Why is that?)
• Defining the Turing jump
• Title not available (Why is that?)
• Forcing and reducibilities
• On the Σ₂-theory of the upper semilattice of Turing degrees
• Lattice initial segments of the hyperdegrees

Cited In (3)

• Lattice initial segments of the hyperdegrees
• 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

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)