Let $V_\propto$ be a fixed, fully effective, infinite dimensional vector space. Let $\mathscr{L}(V_\propto)$ be the lattice consisting of the recursively enumerable (r.e.) subspaces of $V_\propto$ , under the operations of intersection and weak sum (see § 1 for precise definitions). In this article we examine the algebraic properties of $\mathscr{L}(V_\propto)$ . Early research on recursively enumerable algebraic structures was done by Rabin [14], Frolich and Shepherdson [5], Dekker [3], Hamilton [7], and Guhl [6]. Our results are based upon the more (...) recent work concerning vector spaces of Metakides and Nerode [12], Crossley and Nerode [2], Remmel [15], [16], and Kalantari [8]. In the main theorem below, we extend a result of Lachlan from the lattice E of r.e. sets to $\mathscr{L}(V_\propto)$ . We define hyperhypersimple vector spaces, discuss some of their properties and show if $A, B \in \mathscr{L}(V_\propto)$ , and A is a hyperhypersimple subspace of B then there is a recursive space C such that A + C = B. It will be proven that if $V \in \mathscr{L}(V_\propto)$ and the lattice of superspaces of V is a complemented modular lattice then V is hyperhypersimple. The final section contains a summary of related results concerning maximality and simplicity. (shrink)

This paper contributes to the question of under which conditions recursively enumerable sets with isomorphic lattices of recursively enumerable supersets are automorphic in the lattice of all recursively enumerable sets. We show that hyperhypersimple sets (i.e. sets where the recursively enumerable supersets form a Boolean algebra) are automorphic if there is a Σ 0 3 -definable isomorphism between their lattices of supersets. Lerman, Shore and Soare have shown that this is not true if one replaces Σ 0 3 by (...) Σ 0 4. (shrink)

It will be shown that in the lattice of recursively enumerable sets all lattices $\underline{L}(X)$ are elementarily definable with parameters, where X is Σ 0 3 and $\underline{L}^3(X)$ consists of all Σ 0 3 sets containing X.

Semi-hyperhypersimple c.e. sets, also known as diagonals, were introduced by Kummer. He showed that by considering an analogue of hyperhypersimplicity, one could characterize the sets which are the Halting problem relative to arbitrary computable numberings. One could also consider half of splittings of maximal or hyperhypersimple sets and get another variant of maximality and hyperhypersimplicity, which are closely related to the study of automorphisms of the c.e. sets. We investigate the Turing degrees of these classes of c.e. sets. (...) In particular, we show that the analogue of a theorem of Martin fails for these classes. (shrink)

We show that the Q-degree of a hyperhypersimple set includes an infinite collection of Q1-degrees linearly ordered under \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\leq_{Q_1}}$$\end{document} with order type of the integers and consisting entirely of hyperhypersimple sets. Also, we prove that the c.e. Q1-degrees are not an upper semilattice. The main result of this paper is that the Q1-degree of a hemimaximal set contains only one c.e. 1-degree. Analogous results are valid for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} (...) \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi_1^0}$$\end{document}s1-degrees. (shrink)

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets . In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of (...) simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that A has no dense simple superset, the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with , and A [TRIPLE BOND]TB if B is high, and A ≥TB otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail. (shrink)

We show that if M is an r‐maximal set, A is a major subset of M, B is an arbitrary set and, then. We prove that the c.e. ‐degrees are not dense. We also show that there exist infinite collections of ‐degrees and such that the following hold: (i) for every i, j,, and,(ii) each consists entirely of r‐maximal sets, and(iii) each consists entirely of non‐r‐maximal hyperhypersimple sets.

We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.