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

From MaRDI portal
Revision as of 20:01, 12 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    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