Results for 'Computably enumerable set'

998 found
Order:
  1. On the Filter of Computably Enumerable Supersets of an R-Maximal Set.Steffen Lempp, André Nies & D. Reed Solomon - 2001 - Archive for Mathematical Logic 40 (6):415-423.
    We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  20
    Asymptotic Density and Computably Enumerable Sets.Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp - 2013 - Journal of Mathematical Logic 13 (2):1350005.
    We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  3.  7
    Computably Enumerable Sets Below Random Sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
    We use Demuth randomness to study strong lowness properties of computably enumerable sets, and sometimes of Δ20 sets. A set A⊆N is called a base for Demuth randomness if some set Y Turing above A is Demuth random relative to A. We show that there is an incomputable, computably enumerable base for Demuth randomness, and that each base for Demuth randomness is strongly jump-traceable. We obtain new proofs that each computably enumerable set below all (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  32
    Definable Properties of the Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.
    Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  22
    Ramsey's Theorem for Computably Enumerable Colorings.Tamara J. Hummel & Carl G. Jockusch - 2001 - Journal of Symbolic Logic 66 (2):873-880.
    It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  6.  15
    Orbits of Computably Enumerable Sets: Low Sets Can Avoid an Upper Cone.Russell Miller - 2002 - Annals of Pure and Applied Logic 118 (1-2):61-85.
    We investigate the orbit of a low computably enumerable set under automorphisms of the partial order of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of mapping A to a set B such that CTB. Thus, the orbit in of the low set A cannot be contained in the upper cone above C. This complements a result (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  7.  31
    On the Definability of the Double Jump in the Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2002 - Journal of Mathematical Logic 2 (02):261-296.
    We show that the double jump is definable in the computably enumerable sets. Our main result is as follows: let [Formula: see text] is the Turing degree of a [Formula: see text] set J ≥T0″}. Let [Formula: see text] such that [Formula: see text] is upward closed in [Formula: see text]. Then there is an ℒ property [Formula: see text] such that [Formula: see text] if and only if there is an A where A ≡T F and [Formula: (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  15
    Codable Sets and Orbits of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1998 - Journal of Symbolic Logic 63 (1):1-28.
    A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$ . We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show first that (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  9.  6
    On Isomorphism Classes of Computably Enumerable Equivalence Relations.Uri Andrews & Serikzhan A. Badaev - 2020 - Journal of Symbolic Logic 85 (1):61-86.
    We examine how degrees of computably enumerable equivalence relations under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  26
    On Orbits, of Prompt and Low Computably Enumerable Sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.
    This paper concerns automorphisms of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the property of effective simplicity is not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. A major technique used in these proofs is a modification of the Harrington-Soare version of the (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  19
    Computably Enumerable Reals and Uniformly Presentable Ideals.S. A. Terwijn & R. Downey - 2002 - Mathematical Logic Quarterly 48 (S1):29-40.
    We study the relationship between a computably enumerable real and its presentations. A set A presents a computably enumerable real α if A is a computably enumerable prefix-free set of strings such that equation image. Note that equation image is precisely the measure of the set of reals that have a string in A as an initial segment. So we will simply abbreviate equation image by μ. It is known that whenever A so presents (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  8
    1-Generic Splittings of Computably Enumerable Degrees.Guohua Wu - 2006 - Annals of Pure and Applied Logic 138 (1):211-219.
    Say a set Gω is 1-generic if for any eω, there is a string σG such that {e}σ↓ or τσ↑). It is known that can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  13.  37
    There is No Low Maximal D.C.E. Degree.Marat Arslanov, S. Barry Cooper & Angsheng Li - 2000 - Mathematical Logic Quarterly 46 (3):409-416.
    We show that for any computably enumerable set A and any equation image set L, if L is low and equation image, then there is a c.e. splitting equation image such that equation image. In Particular, if L is low and n-c.e., then equation image is n-c.e. and hence there is no low maximal n-c.e. degree.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  14.  10
    An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
    We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  15.  63
    On Lachlan’s Major Sub-Degree Problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.
    The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, ${{\bf 0' = b \lor x}}$ if and (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  16.  32
    Relatively Computably Enumerable Reals.Bernard A. Anderson - 2011 - Archive for Mathematical Logic 50 (3-4):361-365.
    A real X is defined to be relatively c.e. if there is a real Y such that X is c.e.(Y) and ${X \not\leq_T Y}$ . A real X is relatively simple and above if there is a real Y < T X such that X is c.e.(Y) and there is no infinite set ${Z \subseteq \overline{X}}$ such that Z is c.e.(Y). We prove that every nonempty ${\Pi^0_1}$ class contains a member which is not relatively c.e. and that every 1-generic real (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  15
    Traces, Traceability, and Lattices of Traces Under the Set Theoretic Inclusion.Gunther Mainhardt - 2013 - Archive for Mathematical Logic 52 (7-8):847-869.
    Let a trace be a computably enumerable set of natural numbers such that ${V^{[m]} = \{n : \langle n, m\rangle \in V \}}$ is finite for all m, where ${\langle^{.},^{.}\rangle}$ denotes an appropriate pairing function. After looking at some basic properties of traces like that there is no uniform enumeration of all traces, we prove varied results on traceability and variants thereof, where a function ${f : \mathbb{N} \rightarrow \mathbb{N}}$ is traceable via a trace V if for all (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  18.  13
    Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
    We consider the ower semilattice [MATHEMATICAL SCRIPT CAPITAL D] of differences of c.e. sets under inclusion. It is shown that [MATHEMATICAL SCRIPT CAPITAL D] is not distributive as a semilattice, and that the c.e. sets form a definable subclass.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  19.  15
    The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5‐Complete.Stephan Wehner - 1994 - Mathematical Logic Quarterly 40 (1):87-94.
    I introduce an effective enumeration of all effective enumerations of classes of r. e. sets and define with this the index set IE of injectively enumerable classes. It is easy to see that this set is ∑5 in the Arithmetical Hierarchy and I describe a proof for the ∑5-hardness of IE.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20.  25
    On Σ‐Definability Without Equality Over the Real Numbers.Andrei S. Morozov & Margarita V. Korovina - 2008 - Mathematical Logic Quarterly 54 (5):535-544.
    In [5] it has been shown that for first-order definability over the reals there exists an effective procedure which by a finite formula with equality defining an open set produces a finite formula without equality that defines the same set. In this paper we prove that there exists no such procedure for Σ-definability over the reals. We also show that there exists even no uniform effective transformation of the definitions of Σ-definable sets into new definitions of Σ-definable sets in such (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  57
    There is No Low Maximal D. C. E. Degree– Corrigendum.M. Arslanov & S. B. Cooper - 2004 - Mathematical Logic Quarterly 50 (6):628.
    We give a corrected proof of an extension of the Robinson Splitting Theorem for the d. c. e. degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  12
    On a Conjecture of Kleene and Post.S. Barry Cooper - 2001 - Mathematical Logic Quarterly 47 (1):3-34.
    A proof is given that 0′ is definable in the structure of the degrees of unsolvability. This answers a long-standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  23.  38
    A Splitting with Infimum in the D-C. E. Degrees.Q. Lei, L. Hong & D. Decheng - 2000 - Mathematical Logic Quarterly 46 (1):53-76.
    In this paper we prove that any c. e. degree is splittable with an c. e. infimum over any lesser c. e. degree in the class of d-c. e. degrees.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  24.  6
    On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
    It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ2 sets. Different equivalent characterisations of 1-genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1-genericity: in terms of sets of strings and in terms of density functions, as we (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  33
    Degrees of D. C. E. Reals.Rod Downey, Guohua Wu & Xizhong Zheng - 2004 - Mathematical Logic Quarterly 50 (45):345-350.
    A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of the form (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  26.  18
    On the Universal Splitting Property.Rod Downey - 1997 - Mathematical Logic Quarterly 43 (3):311-320.
    We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low2. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  27.  4
    The ibT Degrees of Computably Enumerable Sets Are Not Dense.George Barmpalias & Andrew E. M. Lewis - 2006 - Annals of Pure and Applied Logic 141 (1-2):51-60.
    We show that the identity bounded Turing degrees of computably enumerable sets are not dense.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  28.  67
    Computably Enumerable Equivalence Relations.Su Gao & Peter Gerdes - 2001 - Studia Logica 67 (1):27-59.
    We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  29. Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
    We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  30.  21
    The Computable Lipschitz Degrees of Computably Enumerable Sets Are Not Dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
    The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  31.  12
    Computably Enumerable Sets and Quasi-Reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
    We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  32.  12
    A Necessary and Sufficient Condition for Embedding Ranked Finite Partial Lattices Into the Computably Enumerable Degrees.M. Lerman - 1998 - Annals of Pure and Applied Logic 94 (1-3):143-180.
    We define a class of finite partial lattices which admit a notion of rank compatible with embedding constructions, and present a necessary and sufficient condition for the embeddability of a finite ranked partial lattice into the computably enumerable degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  33.  32
    Upper Bounds on Ideals in the Computably Enumerable Turing Degrees.George Barmpalias & André Nies - 2011 - Annals of Pure and Applied Logic 162 (6):465-473.
    We study ideals in the computably enumerable Turing degrees, and their upper bounds. Every proper ideal in the c.e. Turing degrees has an incomplete upper bound. It follows that there is no prime ideal in the c.e. Turing degrees. This answers a question of Calhoun [2]. Every proper ideal in the c.e. Turing degrees has a low2 upper bound. Furthermore, the partial order of ideals under inclusion is dense.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  34.  9
    A Necessary and Sufficient Condition for Embedding Principally Decomposable Finite Lattices Into the Computably Enumerable Degrees.M. Lerman - 2000 - Annals of Pure and Applied Logic 101 (2-3):275-297.
    We present a necessary and sufficient condition for the embeddability of a principally decomposable finite lattice into the computably enumerable degrees. This improves a previous result which required that, in addition, the lattice be ranked. The same condition is also necessary and sufficient for a finite lattice to be embeddable below every non-zero computably enumerable degree.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  35.  6
    The Computably Enumerable Degrees Are Locally Non-Cappable.Matthew B. Giorgi - 2003 - Archive for Mathematical Logic 43 (1):121-139.
    We prove that every non-computable incomplete computably enumerable degree is locally non-cappable, and use this result to show that there is no maximal non-bounding computably enumerable degree.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  36.  12
    Interpreting N in the Computably Enumerable Weak Truth Table Degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
    We give a first-order coding without parameters of a copy of in the computably enumerable weak truth table degrees. As a tool, we develop a theory of parameter definable subsets.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  37.  20
    Prime Models of Computably Enumerable Degree.Rachel Epstein - 2008 - Journal of Symbolic Logic 73 (4):1373-1388.
    We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree d if d is the degree of its elementary diagram. We show that if a CAD theory T has a prime model of c.e. degree c, then T has a prime model of strictly lower c.e. degree b, where, in addition, b is low (b' = 0'). This extends Csima's result that every CAD theory has a low prime (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  38.  12
    Undecidability and 1-Types in Intervals of the Computably Enumerable Degrees.Klaus Ambos-Spies, Denis R. Hirschfeldt & Richard A. Shore - 2000 - Annals of Pure and Applied Logic 106 (1-3):1-47.
    We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  39.  24
    Every Incomplete Computably Enumerable Truth-Table Degree is Branching.Peter A. Fejer & Richard A. Shore - 2001 - Archive for Mathematical Logic 40 (2):113-123.
    If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  40.  29
    Bounding Minimal Degrees by Computably Enumerable Degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
    In this paper, we prove that there exist computably enumerable degrees a and b such that $\mathbf{a} > \mathbf{b}$ and for any degree x, if x ≤ a and x is a minimal degree, then $\mathbf{x}.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  41.  15
    On Definable Filters in Computably Enumerable Degrees.Wei Wang & Decheng Ding - 2007 - Annals of Pure and Applied Logic 147 (1):71-83.
  42.  11
    Embedding Finite Lattices Into the Ideals of Computably Enumerable Turing Degrees.William C. Calhoun & Manuel Lerman - 2001 - Journal of Symbolic Logic 66 (4):1791-1802.
    We show that the lattice L 20 is not embeddable into the lattice of ideals of computably enumerable Turing degrees (J). We define a structure called a pseudolattice that generalizes the notion of a lattice, and show that there is a Π 2 necessary and sufficient condition for embedding a finite pseudolattice into J.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  43.  10
    The Partial Orderings of the Computably Enumerable ibT-Degrees and Cl-Degrees Are Not Elementarily Equivalent.Klaus Ambos-Spies, Philipp Bodewig, Yun Fan & Thorsten Kräling - 2013 - Annals of Pure and Applied Logic 164 (5):577-588.
    We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1-shift a+1a+1 of a where a+1 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  44.  7
    Every Computably Enumerable Random Real is Provably Computably Enumerable Random.Cristian Calude & Nicholas Hay - 2009 - Logic Journal of the IGPL 17 (4):351-374.
    We prove that every computably enumerable random real is provable in Peano Arithmetic to be c.e. random. A major step in the proof is to show that the theorem stating that “a real is c.e. and random iff it is the halting probability of a universal prefix-free Turing machine” can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem. Our positive result can be contrasted with the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  45.  7
    A Necessary and Sufficient Condition for Embedding Principally Decomposable Finite Lattices Into the Computably Enumerable Degrees Preserving Greatest Element.Burkhard Englert - 2001 - Annals of Pure and Applied Logic 112 (1):1-26.
    We present a necessary and sufficient condition for the embeddability of a finite principally decomposable lattice into the computably enumerable degrees preserving greatest element.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  46.  18
    Universal Computably Enumerable Equivalence Relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
  47.  49
    Computability, Enumerability, Unsolvability, Directions in Recursion Theory, Edited by S. B. Cooper, T. A. Slaman, and S. S. Wainer, London Mathematical Society Lecture Note Series, No. 224, Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1996, Vii + 347 Pp. - Leo Harrington and Robert I. Soare, Dynamic Properties of Computably Enumerable Sets, Pp. 105–121. - Eberhard Herrmann, On the ∀∃-Theory of the Factor Lattice by the Major Subset Relation, Pp. 139–166. - Manuel Lerman, Embeddings Into the Recursively Enumerable Degrees, Pp. 185–204. - Xiaoding Yi, Extension of Embeddings on the Recursively Enumerable Degrees Modulo the Cappable Degrees, Pp. 313–331. - André Nies, Relativization of Structures Arising From Computability Theory. Pp. 219–232. - Klaus Ambos-Spies, Resource-Bounded Genericity. Pp. 1–59. - Rod Downey, Carl G. Jockusch, and Michael Stob. Array Nonrecursive Degrees and Genericity, Pp. 93–104. - Masahiro Kumabe, Degrees of Generic Sets, Pp. 167–183. [REVIEW]C. T. Chong - 1999 - Journal of Symbolic Logic 64 (3):1362-1365.
  48.  40
    The Http://Ars. Els-Cdn. Com/Content/Image/Http://Origin-Ars. Els-Cdn. Com/Content/Image/1-S2. 0-S0168007205001429-Si1. Gif"/> Degrees of Computably Enumerable Sets Are Not Dense. [REVIEW]George Barmpalias & Andrew Em Lewis - 2006 - Annals of Pure and Applied Logic 141 (1):51-60.
  49.  74
    Totally Ω-Computably Enumerable Degrees and Bounding Critical Triples.Rod Downey, Noam Greenberg & Rebecca Weber - 2007 - Journal of Mathematical Logic 7 (2):145-171.
    We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  50. Decomposition and Infima in the Computably Enumerable Degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
    Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
1 — 50 / 998