The theory of the recursively enumerable weak truth-table degrees is undecidable

DOI10.2307/2275436zbMath0776.03020MaRDI QIDQ4032867

Ambos-Spies, Klaus, Richard A. Shore, André Nies

Publication date: 1 April 1993

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

Full work available at URL: https://doi.org/10.2307/2275436

zbMATH Keywords

semilattice; elementary theory; r.e. wtt-degrees

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

03D25: Recursively (computably) enumerable sets and degrees

Related Items

1998–99 Annual Meeting of the Association for Symbolic Logic, 1999 European Summer Meeting of the Association for Symbolic Logic, Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices, Splitting theorems in recursion theory, Boolean pairs formed by the \(\Delta_ n^ 0\)-sets, Classes bounded by incomplete sets, Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees, Interpreting true arithmetic in the theory of the r.e. truth table degrees, The last question on recursively enumerable \(m\)-degrees

Cites Work

• Classical recursion theory. Vol. II
• The recursively enumerable degrees have infinitely many one-types
• Conference in mathematical logic, London 1970
• Strong reducibilities
• The weak truth table degrees of recursively enumerable sets
• Recursively enumerable sets and degrees