The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees

Lempp, Steffen; Nies, Andre

J. Symbolic Logic, Tome 60 (1995) no. 1, p. 1118-1136 / Harvested from Project Euclid

Résumé

We show that the $\Pi_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.

Publié le : 1995-12-14
Classification:

@article{1183744866,
     author = {Lempp, Steffen and Nies, Andre},
     title = {The Undecidability of the II$^\_4$ Theory for the R. E. Wtt and Turing Degrees},
     journal = {J. Symbolic Logic},
     volume = {60},
     number = {1},
     year = {1995},
     pages = { 1118-1136},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744866}
}

Lempp, Steffen; Nies, Andre. The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees. J. Symbolic Logic, Tome 60 (1995) no. 1, pp.  1118-1136. http://gdmltest.u-ga.fr/item/1183744866/