The undecidability of the Π4-theory for the r.e. wtt and Turing degrees
Steffen Lempp, André Nies · Journal of Symbolic Logic · 1995
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.