Switch to: References

Add citations

You must login to add citations.
  1. Implicit Definability in Arithmetic.Stephen G. Simpson - 2016 - Notre Dame Journal of Formal Logic 57 (3):329-339.
    We consider implicit definability over the natural number system $\mathbb{N},+,\times,=$. We present a new proof of two theorems of Leo Harrington. The first theorem says that there exist implicitly definable subsets of $\mathbb{N}$ which are not explicitly definable from each other. The second theorem says that there exists a subset of $\mathbb{N}$ which is not implicitly definable but belongs to a countable, explicitly definable set of subsets of $\mathbb{N}$. Previous proofs of these theorems have used finite- or infinite-injury priority constructions. (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The Borel complexity of von Neumann equivalence.Inessa Moroz & Asger Törnquist - 2021 - Annals of Pure and Applied Logic 172 (5):102913.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Finitary reducibility on equivalence relations.Russell Miller & Keng Meng Ng - 2016 - Journal of Symbolic Logic 81 (4):1225-1254.
    We introduce the notion of finitary computable reducibility on equivalence relations on the domainω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be${\rm{\Pi }}_{n + 2}^0$-complete under computable reducibility, we show that, for everyn, there does exist a natural equivalence relation which is${\rm{\Pi }}_{n + 2}^0$-complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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   7 citations  
  • On Σ1 1 equivalence relations over the natural numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
    We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h-reducibility and FF-reducibility, respectively. We show that the structure is rich even when one fixes the number of properly equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Isomorphism relations on computable structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
    We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   12 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  
    		•
  • On Δ 2 0 -categoricity of equivalence relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 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  
  • 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10.Uri Abraham & Ted Slaman - 2011 - Bulletin of Symbolic Logic 17 (2):272-329.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•