Switch to: References

Citations of:

A survey of lattices of re substructures

Anil Nerode & Jeffrey Remmel

In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--323 (1985)

Add citations

You must login to add citations.

The undecidability of the lattice of R.E. closed subsets of an effective topological space.Sheryl Silibovsky Brady & Jeffrey B. Remmel - 1987 - Annals of Pure and Applied Logic 35 (C):193-203.details The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using (...) Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark
Effectively inseparable Boolean algebras in lattices of sentences.V. Yu Shavrukov - 2010 - Archive for Mathematical Logic 49 (1):69-89.details We show the non-arithmeticity of 1st order theories of lattices of Σ n sentences modulo provable equivalence in a formal theory, of diagonalizable algebras of a wider class of arithmetic theories than has been previously known, and of the lattice of degrees of interpretability over PA. The first two results are applications of Nies’ theorem on the non-arithmeticity of the 1st order theory of the lattice of r.e. ideals on any effectively dense r.e. Boolean algebra. The theorem on degrees of (...) Areas of Mathematics in Philosophy of Mathematics Direct download (3 more) Export citation Bookmark 3 citations
Recursively Enumerable Equivalence Relations Modulo Finite Differences.André Nies - 1994 - Mathematical Logic Quarterly 40 (4):490-518.details We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq, thereby showing that Th has the same computational complexity as the true first-order arithmetic. Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download Export citation Bookmark 5 citations
Generic objects in recursion theory II: Operations on recursive approximation spaces.A. Nerode & J. B. Remmel - 1986 - Annals of Pure and Applied Logic 31:257-288.details Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (3 more) Export citation Bookmark
Recursive unary algebras and trees.Bakhadyr Khoussainov - 1994 - Annals of Pure and Applied Logic 67 (1-3):213-268.details A unary algebra is an algebraic system A = , where ƒ 0 ,…,ƒ n are unary operations on A and n ∈ ω. In the paper we develop the theory of effective unary algebras. We investigate well-known questions of constructive model theory with respect to the class of unary algebras. In the paper we construct unary algebras with a finite number of recursive isomorphism types. We give the notions of program, uniform, and algebraic dimensions of models, and then we (...) Logic and Philosophy of Logic Nonclassical Logics in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 1 citation
Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis. I.Iraj Kalantari & Lawrence Welch - 1998 - Annals of Pure and Applied Logic 93 (1-3):125-151.details 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 (...) Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 7 citations
Recursive properties of relations on models.Geoffrey R. Hird - 1993 - Annals of Pure and Applied Logic 63 (3):241-269.details Hird, G.R., Recursive properties of relations on models, Annals of Pure and Applied Logic 63 241–269. We prove general existence theorems for recursive models on which various relations have specified recursive properties. These capture common features of results in the literature for particular algebraic structures. For a useful class of models with new relations R, S, where S is r.e., we characterize those for which there is a recursive model isomorphic to on which the relation corresponding to S remains r.e., (...) Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 6 citations
Turing degrees of hypersimple relations on computable structures.Valentina S. Harizanov - 2003 - Annals of Pure and Applied Logic 121 (2-3):209-226.details Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose (...) Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark
Undecidability of L(F∞) and other lattices of r.e. substructures.R. G. Downey - 1986 - Annals of Pure and Applied Logic 32:17-26.details Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 8 citations
Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.details A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 18 citations
Recursion theory and ordered groups.R. G. Downey & Stuart A. Kurtz - 1986 - Annals of Pure and Applied Logic 32:137-151.details Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 10 citations
Structural interactions of the recursively enumerable T- and W-degrees.R. G. Downey & M. Stob - 1986 - Annals of Pure and Applied Logic 31:205-236.details Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Model Theory in Logic and Philosophy of Logic Direct download (3 more) Export citation Bookmark 12 citations
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.details In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces. Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 9 citations
Bases of Supermaximal Subspaces and Steinitz Systems II.R. G. Downey - 1986 - Mathematical Logic Quarterly 32 (13‐16):203-210.details Nonclassical Logics in Logic and Philosophy of Logic Direct download (2 more) Export citation Bookmark
On speedable and levelable vector spaces.Frank A. Bäuerle & Jeffrey B. Remmel - 1994 - Annals of Pure and Applied Logic 67 (1-3):61-112.details 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 (...) Logic and Philosophy of Logic Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic Direct download (4 more) Export citation Bookmark 3 citations

1