21 found
Order:
  1.  21
    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.
  2.  14
    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 in the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  11
    Separable Models of Randomizations.Uri Andrews & H. Jerome Keisler - 2015 - Journal of Symbolic Logic 80 (4):1149-1181.
  4.  10
    Definable Closure in Randomizations.Uri Andrews, Isaac Goldbring & H. Jerome Keisler - 2015 - Annals of Pure and Applied Logic 166 (3):325-341.
  5.  6
    Effective Inseparability, Lattices, and Preordering Relations.Uri Andrews & Andrea Sorbi - forthcoming - Review of Symbolic Logic:1-28.
    We study effectively inseparable prelattices $\wedge, \vee$ are binary computable operations; ${ \le _L}$ is a computably enumerable preordering relation, with $0{ \le _L}x{ \le _L}1$ for every x; the equivalence relation ${ \equiv _L}$ originated by ${ \le _L}$ is a congruence on L such that the corresponding quotient structure is a nontrivial bounded lattice; the ${ \equiv _L}$ -equivalence classes of 0 and 1 form an effectively inseparable pair of sets). Solving a problem in we show, that if (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  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  
  7.  18
    New Spectra of Strongly Minimal Theories in Finite Languages.Uri Andrews - 2011 - Annals of Pure and Applied Logic 162 (5):367-372.
    We describe strongly minimal theories Tn with finite languages such that in the chain of countable models of Tn, only the first n models have recursive presentations. Also, we describe a strongly minimal theory with a finite language such that every non-saturated model has a recursive presentation.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8.  11
    The Degrees of Bi-Hyperhyperimmune Sets.Uri Andrews, Peter Gerdes & Joseph S. Miller - 2014 - Annals of Pure and Applied Logic 165 (3):803-811.
    We study the degrees of bi-hyperhyperimmune sets. Our main result characterizes these degrees as those that compute a function that is not dominated by any ∆02 function, and equivalently, those that compute a weak 2-generic. These characterizations imply that the collection of bi-hhi Turing degrees is closed upwards.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  20
    A New Spectrum of Recursive Models Using an Amalgamation Construction.Uri Andrews - 2011 - Journal of Symbolic Logic 76 (3):883 - 896.
    We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds a new spectrum to the list of known possible spectra. The second result, that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in a finite language.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  15
    The Theory of Ceers Computes True Arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
    We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  5
    Computability and the Symmetric Difference Operator.Uri Andrews, Peter M. Gerdes, Steffen Lempp, Joseph S. Miller & Noah D. Schweber - forthcoming - Logic Journal of the IGPL.
    Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  3
    Decidable Models of Ω-Stable Theories.Uri Andrews - 2014 - Journal of Symbolic Logic 79 (1):186-192.
  13. Initial Segments of the Degrees of Ceers.Uri Andrews & Andrea Sorbi - forthcoming - Journal of Symbolic Logic:1-23.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  13
    Independence in Randomizations.Uri Andrews, Isaac Goldbring & H. Jerome Keisler - 2019 - Journal of Mathematical Logic 19 (1):1950005.
    The randomization of a complete first-order theory [Formula: see text] is the complete continuous theory [Formula: see text] with two sorts, a sort for random elements of models of [Formula: see text] and a sort for events in an underlying atomless probability space. We study independence relations and related ternary relations on the randomization of [Formula: see text]. We show that if [Formula: see text] has the exchange property and [Formula: see text], then [Formula: see text] has a strict independence (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  6
    The Property “Arithmetic-is-Recursive” on a Cone.Uri Andrews, Matthew Harrison-Trainor & Noah Schweber - 2021 - Journal of Mathematical Logic 21 (3):2150021.
    We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  16.  1
    On the Structure of Computable Reducibility on Equivalence Relations of Natural Numbers.Uri Andrews, Daniel F. Belin & Luca San Mauro - forthcoming - Journal of Symbolic Logic:1-30.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  3
    The Property “Arithmetic-is-Recursive” on a Cone.Uri Andrews, Matthew Harrison-Trainor & Noah Schweber - 2021 - Journal of Mathematical Logic 21 (3).
    We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  18.  3
    Scattered sentences have few separable randomizations.Uri Andrews, Isaac Goldbring, Sherwood Hachtman, H. Jerome Keisler & David Marker - 2020 - Archive for Mathematical Logic 59 (5-6):743-754.
    In the paper Randomizations of Scattered Sentences, Keisler showed that if Martin’s axiom for aleph one holds, then every scattered sentence has few separable randomizations, and asked whether the conclusion could be proved in ZFC alone. We show here that the answer is “yes”. It follows that the absolute Vaught conjecture holds if and only if every \-sentence with few separable randomizations has countably many countable models.
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  19.  3
    Spectra of Atomic Theories.Uri Andrews & Julia F. Knight - 2009 - Journal of Symbolic Logic 78 (4):1189-1198.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  20.  2
    Is a Spectrum of a Non-Disintegrated Flat Strongly Minimal Model Complete Theory in a Language with Finite Signature.Uri Andrews & Omer Mermelstein - 2021 - Journal of Symbolic Logic 86 (4):1632-1656.
    We build a new spectrum of recursive models (SRM(T)) of a strongly minimal theory. This theory is non-disintegrated, flat, model complete, and in a language with a finite structure.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  1
    The Complexity of Index Sets of Classes of Computably Enumerable Equivalence Relations.Uri Andrews & Andrea Sorbi - 2016 - Journal of Symbolic Logic 81 (4):1375-1395.
    Let$ \le _c $be computable the reducibility on computably enumerable equivalence relations. We show that for every ceerRwith infinitely many equivalence classes, the index sets$\left\{ {i:R_i \le _c R} \right\}$,$\left\{ {i:R_i \ge _c R} \right\}$, and$\left\{ {i:R_i \equiv _c R} \right\}$are${\rm{\Sigma }}_3^0$complete, whereas in caseRhas only finitely many equivalence classes, we have that$\left\{ {i:R_i \le _c R} \right\}$is${\rm{\Pi }}_2^0$complete, and$\left\{ {i:R \ge _c R} \right\}$ is${\rm{\Sigma }}_2^0$complete. Next, solving an open problem from [1], we prove that the index set of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark