Structural interactions of the recursively enumerable T- and W-degrees (Q1083447): Difference between revisions

This paper studies relationships between weak truth table and Turing reducibilities (and their applications to recursive model theory, r.e. sets etc.). Various ''interactions'' are discussed. A flavour is provided by the following typical theorems: there exist r.e. sets \(A\equiv_ TB\) with the infinum of the W-degrees of A and B not existing; there exist r.e. nonrecursive sets A and B with \(A\equiv_ TB\) and the W-degrees of A and B forming a minimal pair; and there exists a non-zero r.e. degree \(\underset \tilde{} a\) such that if A is an r.e. set of degree \(\underset \tilde{} a\) then there is an r.e. set B with \(\emptyset <_ TB<_ TA\) and the W- degrees of B and A forming a minimal pair.