Annals of Pure and Applied Logic 67 (1-3):61-112 (1994)

Abstract
In this paper, we study the lattice of r.e. subspaces of a recursively presented vector space V ∞ with regard to the various complexity-theoretic speed-up properties such as speedable, effectively speedable, levelable, and effectively levelable introduced by Blum and Marques. In particular, we study the interplay between an r.e. basis A for a subspace V of V ∞ and V with regard to these properties. We show for example that if A or V is speedable , then V is levelable . We also show that if A is an r.e. subset of a recursive basis for V ∞ , then A is levelable iff V is speedable while it is not the case that A is levelable iff V is speedable. We also provide several contrasts between the lattice of r.e. subspaces and the lattice of r.e. sets with respect to these speed-up properties. For example, every maximal set is levelable but we show that there exist supermaximal spaces which are nonspeedable in all possible r.e. degrees as well as supermaximal spaces which are levelable in all r.e. degrees which contain levelable sets
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(94)90008-6
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,160
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Computational Complexity, Speedable and Levelable Sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
Classifications of Degree Classes Associated with R.E. Subspaces.R. G. Downey & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 42 (2):105-124.
A Survey of Lattices of Re Substructures.Anil Nerode & Jeffrey Remmel - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--323.
On R.E. And CO-R.E. Vector Spaces with Nonextendible Bases.J. Remmel - 1980 - Journal of Symbolic Logic 45 (1):20-34.

View all 15 references / Add more references

Citations of this work BETA

Non-Splittings of Speedable Sets.Ellen S. Chih - 2015 - Journal of Symbolic Logic 80 (2):609-635.

Add more citations

Similar books and articles

Computational Complexity, Speedable and Levelable Sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
Model-Theory of Vector-Spaces Over Unspecified Fields.David Pierce - 2009 - Archive for Mathematical Logic 48 (5):421-436.
Simple and Hyperhypersimple Vector Spaces.Allen Retzlaff - 1978 - Journal of Symbolic Logic 43 (2):260-269.
Maximal and Cohesive Vector Spaces.J. B. Remmel - 1977 - Journal of Symbolic Logic 42 (3):400-418.
On R.E. And CO-R.E. Vector Spaces with Nonextendible Bases.J. Remmel - 1980 - Journal of Symbolic Logic 45 (1):20-34.
On Vector Spaces Over Specific Fields Without Choice.Paul Howard & Eleftherios Tachtsis - 2013 - Mathematical Logic Quarterly 59 (3):128-146.
The Bloch Gyrovector.Jing-Ling Chen & Abraham A. Ungar - 2002 - Foundations of Physics 32 (4):531-565.

Analytics

Added to PP index
2014-01-16

Total views
13 ( #766,098 of 2,499,305 )

Recent downloads (6 months)
1 ( #418,195 of 2,499,305 )

How can I increase my downloads?

Downloads

My notes