In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of (...) P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞. (shrink)

In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. In all (...) of these models, the algebraic closure of a set is nontrivial., is given in §1, however in vector spaces, cl is just the subspace generated byS, in Boolean algebras, cl is just the subalgebra generated byS, and in algebraically closed fields, cl is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings. (shrink)

In this paper we develop a point-free approach to the study of topological spaces and functions on them, establish platforms for both and present some findings on recursive points. In the first sections of the paper, we obtain conditions under which our approach leads to the generation of ideal objects with which mathematicians work. Next, we apply the effective version of our approach to the real numbers, and make exact connections to the classical approach to recursive reals. In the succeeding (...) sections of the paper, we introduce machinery to produce functions on topological spaces and find succinct conditions which will be effectivized in our sequel. (shrink)

In [5], Metakides and Nerode introduced the study of recursively enumerable substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for (...) Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff consideredX, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets ofωgive rise to r.e. subsets ofX. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset ofX? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that givenAany r.e. set andany r.e. open subset ofX, there exists an r.e. open set ℋ which is a subset ofand is dense in and in whichAis coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree ofA. We then go on and establish various results on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2. (shrink)

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This led (...) to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures. (shrink)

We show that the first order theory of the lattice $\mathscr{L}^{ (S) of finite dimensional closed subsets of any nontrivial infinite dimensional Steinitz Exhange System S has logical complexity at least that of first order number theory and that the first order theory of the lattice L(S ∞ ) of computably enumerable closed subsets of any nontrivial infinite dimensional computable Steinitz Exchange System S ∞ has logical complexity exactly that of first order number theory. Thus, for example, the lattice of (...) finite dimensional subspaces of a standard copy of $\bigoplus_\omega$ Q interprets first order arithmetic and is therefore as complicated as possible. In particular, our results show that the first order theories of the lattice L(V ∞ ) of c.e. subspaces of a fully effective ℵ 0 -dimensional vector space V∞ and the lattice of c.e. algebraically closed subfields of a fully effective algebraically closed field F ∞ of countably infinite transcendence degree each have logical complexity that of first order number theory. (shrink)

The paper presents a brief survey of recent work by Metakides, Nerode and others in the area of effective algebra and makes some comments on the relation between formal presentations, characterizations, etc. of sets and of algebraic structures and their practical presentations.

Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that no (...) set of degree ≥0” can be a member of any thin Π01 class. An r.e. degree d is constructed such that no set of degree d can be a member of any thin Π01 class. It is also shown that between any two distinct comparable r.e. degrees, there is a degree that contains a set which is of rank one in some thin Π01 class. It is shown that no maximal set can have rank one in any Π01 class, while there exist maximal sets of rank 2. The connection between Π01 classes, propositional theories and recursive Boolean algebras is explored, producing several corollaries to the results on Π01 classes. For example, call a recursive Boolean algebra thin if it has no proper nonprincipal recursive ideals. Then no thin recursive Boolean algebra can have a maximal ideal of degree ≥0”. (shrink)