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
recursively enumerable subspace
0 references
weak truth table reducibility
0 references
weak truth table degrees
0 references