Switch to: Citations

Add references

You must login to add references.
  1. A borel reducibility theory for classes of countable structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
    We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of as a (...)
    Download  
     
    Export citation  
     
    Bookmark   52 citations  
  • (1 other version)A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Mathematical Logic Quarterly 33 (1):43-46.
    Download  
     
    Export citation  
     
    Bookmark   14 citations  
  • Classifying positive equivalence relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
    Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). This (...)
    Download  
     
    Export citation  
     
    Bookmark   27 citations  
  • (1 other version)A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):43-46.
    Download  
     
    Export citation  
     
    Bookmark   14 citations  
  • Recursively Enumerable Equivalence Relations Modulo Finite Differences.André Nies - 1994 - Mathematical Logic Quarterly 40 (4):490-518.
    We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • On Group-theoretic Decision Problems and Their Classification.Charles F. Miller - 1971 - Princeton University Press.
    Part exposition and part presentation of new results, this monograph deals with that area of mathematics which has both combinatorial group theory and mathematical logic in common. Its main topics are the word problem for groups, the conjugacy problem for groups, and the isomorphism problem for groups. The presentation depends on previous results of J. L. Britton, which, with other factual background, are treated in detail.
    Download  
     
    Export citation  
     
    Bookmark   3 citations