Initial segments of the degrees of size _ 1

DOI10.1007/BF02772668MaRDI QIDQ1820153zbMATH OpenFDO

Authors Uri Abraham, Richard A. Shore

Publication date 1986

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02772668

zbMATH Keywords

countable predecessor propertydegrees of unsolvabilityforcingtruth-table degreesTuring degreesupper semi-lattice

Mathematics Subject Classification ID

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

Review text

It is proved (in ZFC) that every upper semi-lattice of size \(\aleph_ 1\) that has 0 and the countable predecessor property (each element has countably many predecessors) is isomorphic to an initial segment of the Turing degrees. This remarkable positive result answers questions raised by Yates in 1968. The authors first treat the case of countable linear orderings, then linear orderings of size \(\aleph_ 1\), and finally arbitrary upper semi-lattices of that size. The main arguments are forcing arguments, with key ideas credited to Shelah. Minor modifications allow this result to be adapted to both the truth-table degrees and the weak truth-table degrees. But it is known from work of Groszek and Slaman that the result cannot be extended to upper semi-lattices of size \(\aleph_ 2\), even when \(\aleph_ 2\) is less than the size of the continuum. The paper is nearly self-contained, requiring only a few constructions found in \textit{M. Lerman}'s Degrees of unsolvability (1983; Zbl 0542.03023).

Recommendations

• Local Initial Segments of The Turing Degrees
• Lattice initial segments of the hyperdegrees
• Initial segments of Δ_2n+1¹-degrees
• Undecidability and initial segments of the (r.e.) tt-degrees
• Lattice nonembeddings and initial segments of the recursively enumerable degrees

Cites work

• Countable initial segments of the degrees of unsolvability
• Degrees of unsolvability: structure and theory
• Distributive Initial Segments of the Degrees of Unsolvability
• First-order theory of the degrees of recursive unsolvability
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 3329000 (Why is no real title available?)
• Independence Results on the Global Structure of the Turing Degrees
• Initial segments of the degrees of unsolvability
• Initial Segments of Turing Degrees
• On degrees of recursive unsolvability
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• Recursively enumerable sets of positive integers and their decision problems
• Reducibility orderings: Theories, definability and automorphisms
• Sublattices and Initial Segments of the Degrees of Unsolvability
• The homogeneity conjecture
• The strong homogeneity conjecture
• The upper semi-lattice of degrees of recursive unsolvability

Cited in

(15)

• Lattices of c-degrees
• Initial segments of the degrees of constructibility
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Morasses, square and forcing axioms
• Initial segments of Δ_2n+1¹-degrees
• scientific article; zbMATH DE number 8116 (Why is no real title available?)
• as an initial segment of the c-degrees
• Local Initial Segments of The Turing Degrees
• Intervals of the Muchnik lattice
• Embedding jump upper semilattices into the Turing degrees
• Lattice initial segments of the hyperdegrees
• Cofinal maximal chains in the Turing degrees
• Maximal chains in the Turing degrees
• Martin's axiom and embeddings of upper semi-lattices into the Turing degrees
• Undecidability and 1-types in the recursively enumerable degrees

This page was built for publication: Initial segments of the degrees of size \(\aleph _ 1\)

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