Lattice initial segments of the hyperdegrees

DOI10.2178/JSL/1264433911MaRDI QIDQ5190191zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen, Richard A. Shore

Publication date 15 March 2010

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

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

zbMATH Keywords

fusion lemmahyperarithmetic latticehyperdegreesinitial segment

Mathematics Subject Classification ID

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

Abstract: We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, $mathcal{D}_h$. In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable locally finite lattice) is isomorphic to an initial segment of $mathcal{D}_h$. Corollaries include the decidability of the two quantifier theory of $\mathrm{\%}mathcal{D}_h$ and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of $omeg{a}_1^{CK}$. Somewhat surprisingly, the set theoretic analog of this forcing does not preserve $omeg{a}_1$. On the other hand, we construct countable lattices that are not isomorphic to an initial segment of $mathcal{D}_h$.

Recommendations

• Initial segments of Δ_2n+1¹-degrees
• On the decidability of the \(\Sigma_2\) theories of the arithmetic and hyperarithmetic degrees as uppersemilattices
• Undecidability and initial segments of the (r.e.) tt-degrees
• Initial segments of the degrees of size \(\aleph _ 1\)
• Initial segments of the degrees of constructibility

Cites work

• A Note on Non-Distributive Sublattices of Degrees and Hyperdegrees
• Degrees of Unsolvability. (AM-55)
• Distributive Initial Segments of the Degrees of Unsolvability
• Forcing and reductibilities. II. Forcing in fragments of analysis
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• scientific article; zbMATH DE number 3289430 (Why is no real title available?)
• Initial segments of the degrees of constructibility
• Initial segments of the degrees of size \(\aleph _ 1\)
• Initial segments of the degrees of unsolvability
• Lattices of c-degrees
• Local Definitions in Degree Structures: The Turing Jump, Hyperdegrees and Beyond
• Local Initial Segments of The Turing Degrees
• On degrees of recursive unsolvability
• On Sequences of Degrees of Constructibility (Solution of Friedman'S Problem 75)
• On the representation of lattices
• THE FIRST‐ORDER THEORY OF THE c‐DEGREES
• The upper semi-lattice of degrees of recursive unsolvability
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable

Cited in

(5)

• Initial segments of the degrees of constructibility
• Initial segments of the degrees of size \(\aleph _ 1\)
• Initial segments of Δ_2n+1¹-degrees
• On the decidability of the \(\Sigma_2\) theories of the arithmetic and hyperarithmetic degrees as uppersemilattices
• The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable

This page was built for publication: Lattice initial segments of the hyperdegrees

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