The undecidability of the recursively enumerable degrees

DOI10.1090/S0273-0979-1982-14970-9zbMath0518.03016WikidataQ29011875 ScholiaQ29011875MaRDI QIDQ3666835

Saharon Shelah, Leo Harrington

Publication date: 1982

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

undecidability; partial ordering; recursively enumerable degrees; priority argument

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

Working below a high recursively enumerable degree, Annual meeting of the Association for Symbolic Logic, Notre Dame, 1993, The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees, 1998–99 Annual Meeting of the Association for Symbolic Logic, European Summer Meeting of the Association for Symbolic Logic, Infima in the d.r.e. degrees, Undecidability and 1-types in the recursively enumerable degrees, Incomparable prime ideals of recursively enumerable degrees, Splitting theorems in recursion theory, Interpreting true arithmetic in the theory of the r.e. truth table degrees, The last question on recursively enumerable \(m\)-degrees, Definability in the Recursively Enumerable Degrees, The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility, The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable