The undecidability of the II4 theory for the R. E. wtt and Turing degrees

&
Journal of Symbolic Logic 60 (4):1118 - 1136 (1995)
  Copy   BIBTEX

Abstract

We show that the Π 4 -theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters

Categories

Keywords

Reprint years

DOI

10.2307/2275877

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,098

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118-1136.
The theory of the recursively enumerable weak truth-table degrees is undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
Infima in the Recursively Enumerable Weak Truth Table Degrees.Rich Blaylock, Rod Downey & Steffen Lempp - 1997 - Notre Dame Journal of Formal Logic 38 (3):406-418.
Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
Undecidability and 1-types in the recursively enumerable degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices.Klaus Ambos-Spies, Peter Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (2):880-905.
Interpreting N in the computably enumerable weak truth table degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
On the Jumps of the Degrees Below a Recursively Enumerable Degree.David R. Belanger & Richard A. Shore - 2018 - Notre Dame Journal of Formal Logic 59 (1):91-107.
Weak Truth Table Degrees of Structures.David R. Belanger - 2015 - Notre Dame Journal of Formal Logic 56 (2):263-285.
The existential theory of the poset of R.e. Degrees with a predicate for single jump reducibility.Steffen Lempp & Manuel Lerman - 1992 - Journal of Symbolic Logic 57 (3):1120-1130.

Analytics

Added to PP
2009-01-28

Downloads
83 (#207,822)

6 months
25 (#118,899)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Interpreting N in the computably enumerable weak truth table degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
Continuity of capping in C bT.Paul Brodhead, Angsheng Li & Weilin Li - 2008 - Annals of Pure and Applied Logic 155 (1):1-15.

Add more citations

References found in this work

No references found.

Add more references