Switch to: References

Add citations

You must login to add citations.
  1. Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - forthcoming - Journal of Symbolic Logic:1-27.
    The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Torsion-free abelian groups with optimal Scott families.Alexander G. Melnikov - 2018 - Journal of Mathematical Logic 18 (1):1850002.
    We prove that for any computable successor ordinal of the form α = δ + 2k there exists computable torsion-free abelian group that is relatively Δα0 -categorical and not Δα−10 -categorical. Equivalently, for any such α there exists a computable TFAG whose initial segments are uniformly described by Σαc infinitary computable formulae up to automorphism, and there is no syntactically simpler family of formulae that would capture these orbits. As far as we know, the problem of finding such optimal examples (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Computable Abelian groups.Alexander G. Melnikov - 2014 - Bulletin of Symbolic Logic 20 (3):315-356,.
    We provide an introduction to methods and recent results on infinitely generated abelian groups with decidable word problem.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Graphs realised by r.e. equivalence relations.Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan - 2014 - Annals of Pure and Applied Logic 165 (7-8):1263-1290.
    We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Bi‐embeddability spectra and bases of spectra.Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Mathematical Logic Quarterly 65 (2):228-236.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Agreement reducibility.Rachel Epstein & Karen Lange - 2020 - Mathematical Logic Quarterly 66 (4):448-465.
    We introduce agreement reducibility and highlight its major features. Given subsets A and B of, we write if there is a total computable function satisfying for all,.We shall discuss the central role plays in this reducibility and its connection to strong‐hyper‐hyper‐immunity. We shall also compare agreement reducibility to other well‐known reducibilities, in particular s1‐ and s‐reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on based on set‐agreement. We end by describing the (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Computable Reducibility of Equivalence Relations and an Effective Jump Operator.John D. Clemens, Samuel Coskey & Gianni Krakoff - forthcoming - Journal of Symbolic Logic:1-22.
    We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Structural Highness Notions.Wesley Calvert, Johanna N. Y. Franklin & Dan Turetsky - 2023 - Journal of Symbolic Logic 88 (4):1692-1724.
    We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - 2020 - Archive for Mathematical Logic 59 (7-8):835-864.
    Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • 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   3 citations  
  • On the Structure of Computable Reducibility on Equivalence Relations of Natural Numbers.Uri Andrews, Daniel F. Belin & Luca San Mauro - 2023 - Journal of Symbolic Logic 88 (3):1038-1063.
    We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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   3 citations