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

From MaRDI portal
Revision as of 20:13, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
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