Classification of degree classes associated with r.e. subspaces (Q1092898)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Classification of degree classes associated with r.e. subspaces
scientific article

    Statements

    Classification of degree classes associated with r.e. subspaces (English)
    0 references
    1989
    0 references
    Let B be an r.e. basis of an r.e. subspace V of \(V_{\infty}\). Then \(B\leq _ WV\) where \(\leq _ W\) denotes weak truth table reducibility. We show that all weak truth table degrees are coded into the structure of V: Theorem. For any r.e. set \(A\leq _ WV\) there exists an r.e. basis B of V with \(B\equiv _ WA\). Similar results hold for splittings and complements. We also examine the degrees of pairs of summands of V. We construct r.e. spaces V and W such that \(V<_ TW\) and such that for all r.e. subspaces \(V_ 1,V_ 2\) of W, if \(V_ 1\equiv _ TV\) and \(V_ 1\oplus V_ 2=W\) then \(V_ 2\equiv _ T\emptyset\), and indeed, \(V_ 2\) has dependence degree \(\underset \tilde{} 0\).
    0 references
    0 references
    recursively enumerable subspace
    0 references
    weak truth table reducibility
    0 references
    weak truth table degrees
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references