The undecidability of the Π4-theory for the r.e. wtt and Turing degrees

Publisher： Cambridge University Press

E-ISSN： 1943-5886|60|4|1118-1136

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.60, Iss.4, 1995-12, pp. : 1118-1136

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.

Related content

Wtt-degrees and T-degrees of r.e. sets

By  

The Journal of Symbolic Logic, Vol. 48, Iss. 4, 1983-12 ,pp. : 921-930 (10)

Cambridge University Press

Access to resources Recommend Favorite

Undecidability and initial segments of the (r.e.) tt-degrees

By  

The Journal of Symbolic Logic, Vol. 55, Iss. 3, 1990-09 ,pp. : 987-1006 (20)

Cambridge University Press

Access to resources Recommend Favorite

The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility

By  

The Journal of Symbolic Logic, Vol. 57, Iss. 3, 1992-09 ,pp. : 1120-1130 (11)

Cambridge University Press

Access to resources Recommend Favorite

On the Σ 2-theory of the upper semilattice of Turing degrees

By  

The Journal of Symbolic Logic, Vol. 58, Iss. 1, 1993-03 ,pp. : 193-204 (12)

Cambridge University Press

Access to resources Recommend Favorite

Priority arguments in the continuous r.e. degrees 1

By  

The Journal of Symbolic Logic, Vol. 50, Iss. 3, 1985-09 ,pp. : 661-667 (7)

Cambridge University Press

Access to resources Recommend Favorite