Results for 'Computably enumerable reals'

998 found
Order:
  1.  33
    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  
  2.  20
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  3.  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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  17
    Approximation Representations for Reals and Their Wtt-Degrees.George Barmpalias - 2004 - Mathematical Logic Quarterly 50 (45):370-380.
    We study the approximation properties of computably enumerable reals. We deal with a natural notion of approximation representation and study their wtt-degrees. Also, we show that a single representation may correspond to a quite diverse variety of reals.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  10
    Regular Reals.Guohua Wu - 2005 - Mathematical Logic Quarterly 51 (2):111-119.
    Say that α is an n-strongly c. e. real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n-strongly c. e. for some n. Let Sn be the set of all n-strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then we have: S1 ⊂ S2 ⊂ · · · ⊂ Sn ⊂ · · (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  6.  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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  7.  68
    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   14 citations  
  8.  19
    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.
  9.  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   9 citations  
  10.  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  
  11.  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  
  12.  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  
  13.  8
    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   2 citations  
  14.  21
    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  
  15.  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  
  16.  46
    Bounding Computably Enumerable Degrees in the Ershov Hierarchy.Angsheng Li, Guohua Wu & Yue Yang - 2006 - Annals of Pure and Applied Logic 141 (1):79-88.
    Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  8
    A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
    We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees and the array noncomputable degrees. The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  18. 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  
  19.  40
    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  
  20.  64
    Dynamic Properties of Computably Enumerable Sets.Robert I. Soare - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. pp. 224--105.
  21.  8
    The Computably Enumerable Degrees Are Locally Non-Cappable.Matthew B. Giorgi - 2003 - Archive for Mathematical Logic -1 (1):1-1.
  22.  19
    Jumps of Computably Enumerable Equivalence Relations.Uri Andrews & Andrea Sorbi - 2018 - Annals of Pure and Applied Logic 169 (3):243-259.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  23.  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  
  24.  15
    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  
  25.  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  
  26.  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  
  27. 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  
  28.  33
    Definable Encodings in the Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2000 - Bulletin of Symbolic Logic 6 (2):185-196.
  29.  34
    Isomorphisms of Splits of Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2003 - Journal of Symbolic Logic 68 (3):1044-1064.
    We show that if A and $\widehat{A}$ are automorphic via Φ then the structures $S_{R}(A)$ and $S_{R}(\widehat{A})$ are $\Delta_{3}^{0}-isomorphic$ via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  30.  11
    A Computably Enumerable Vector Space with the Strong Antibasis Property.L. R. Galminas - 2000 - Archive for Mathematical Logic 39 (8):605-629.
    Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets $B<_{\rm T}A$ such (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  31.  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  
  32.  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   6 citations  
  33.  33
    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  
  34.  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  
  35.  15
    On Definable Filters in Computably Enumerable Degrees.Wei Wang & Decheng Ding - 2007 - Annals of Pure and Applied Logic 147 (1):71-83.
  36.  10
    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  
  37.  4
    Addendum to “Computably Enumerable Sets and Quasi-Reducibility”.R. Downey, G. LaForte & A. Nies - 1999 - Annals of Pure and Applied Logic 98 (1-3):295.
  38.  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  
  39.  29
    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  
  40.  41
    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.
  41.  28
    Relative Randomness and Real Closed Fields.Alexander Raichev - 2005 - Journal of Symbolic Logic 70 (1):319 - 330.
    We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field. With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  42.  14
    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 (4 more)  
     
    Export citation  
     
    Bookmark  
  43.  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  
  44.  23
    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  
  45.  33
    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  
  46.  16
    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  
  47.  46
    The Complexity of Orbits of Computably Enumerable Sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - Bulletin of Symbolic Logic 14 (1):69 - 87.
    The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  48.  15
    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  
  49.  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   1 citation  
  50.  10
    Weakly Precomplete Computably Enumerable Equivalence Relations.Serikzhan Badaev & Andrea Sorbi - 2016 - Mathematical Logic Quarterly 62 (1-2):111-127.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 998