On speedable and levelable vector spaces

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


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



    Upload a copy of this work     Papers currently archived: 84,108

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.


Added to PP

15 (#736,504)

6 months
1 (#511,561)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Non-splittings of speedable sets.Ellen S. Chih - 2015 - Journal of Symbolic Logic 80 (2):609-635.

Add more citations

References found in this work

Computational complexity, speedable and levelable sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
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.
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.
On complexity properties of recursively enumerable sets.M. Blum & I. Marques - 1973 - Journal of Symbolic Logic 38 (4):579-593.

View all 15 references / Add more references