Structural interactions of the recursively enumerable T- and W-degrees

From MaRDI portal





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.



Cites work









This page was built for publication: Structural interactions of the recursively enumerable T- and W-degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083447)