Results for 'Invariant equivalence relations'

999 found
Order:
  1.  26
    Smoothness of Bounded Invariant Equivalence Relations.Krzysztof Krupiński & Tomasz Rzepecki - 2016 - Journal of Symbolic Logic 81 (1):326-356.
  2.  10
    Equivalence Relations Invariant Under Group Actions.Tomasz Rzepecki - 2018 - Journal of Symbolic Logic 83 (2):683-702.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  39
    Simultaneity as an Invariant Equivalence Relation.Marco Mamone-Capria - 2012 - Foundations of Physics 42 (11):1365-1383.
    This paper deals with the concept of simultaneity in classical and relativistic physics as construed in terms of group-invariant equivalence relations. A full examination of Newton, Galilei and Poincaré invariant equivalence relations in ℝ4 is presented, which provides alternative proofs, additions and occasionally corrections of results in the literature, including Malament’s theorem and some of its variants. It is argued that the interpretation of simultaneity as an invariant equivalence relation, although interesting for (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  41
    Amenable Versus Hyperfinite Borel Equivalence Relations.Alexander S. Kechris - 1993 - Journal of Symbolic Logic 58 (3):894-907.
    LetXbe a standard Borel space, and letEbe acountableBorel equivalence relation onX, i.e., a Borel equivalence relationEfor which every equivalence class [x]Eis countable. By a result of Feldman-Moore [FM],Eis induced by the orbits of a Borel action of a countable groupGonX.The structure of general countable Borel equivalence relations is very little understood. However, a lot is known for the particularly important subclass consisting of hyperfinite relations. A countable Borel equivalence relation is calledhyperfiniteif it is (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  11
    Relative Exchangeability with Equivalence Relations.Harry Crane & Henry Towsner - 2018 - Archive for Mathematical Logic 57 (5-6):533-556.
    We describe an Aldous–Hoover-type characterization of random relational structures that are exchangeable relative to a fixed structure which may have various equivalence relations. Our main theorem gives the common generalization of the results on relative exchangeability due to Ackerman \)-invariant measures: part I, 2015. arXiv:1509.06170) and Crane and Towsner and hierarchical exchangeability results due to Austin and Panchenko :809–823, 2014).
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  18
    Linearization of Definable Order Relations.Vladimir Kanovei - 2000 - Annals of Pure and Applied Logic 102 (1-2):69-100.
    We prove that if ≼ is an analytic partial order then either ≼ can be extended to a Δ 2 1 linear order similar to an antichain in 2 ω 1 , ordered lexicographically, or a certain Borel partial order ⩽ 0 embeds in ≼. Similar linearization results are presented, for κ -bi-Souslin partial orders and real-ordinal definable orders in the Solovay model. A corollary for analytic equivalence relations says that any Σ 1 1 equivalence relation E (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  15
    Analytic Equivalence Relations and the Forcing Method.Jindřich Zapletal - 2013 - Bulletin of Symbolic Logic 19 (4):473-490.
    I describe several ways in which forcing arguments can be used to yield clean and conceptual proofs of nonreducibility, ergodicity and other results in the theory of analytic equivalence relations. In particular, I present simple Borel equivalence relations $E, F$ such that a natural proof of nonreducibility of $E$ to $F$ uses the independence of the Singular Cardinal Hypothesis at $\aleph_\omega$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  9
    Borel Equivalence Relations and Classifications of Countable Models.Greg Hjorth & Alexander S. Kechris - 1996 - Annals of Pure and Applied Logic 82 (3):221-272.
    Using the theory of Borel equivalence relations we analyze the isomorphism relation on the countable models of a theory and develop a framework for measuring the complexity of possible complete invariants for isomorphism.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  9.  8
    Borel Equivalence Relations Induced by Actions of the Symmetric Group.Greg Hjorth, Alexander S. Kechris & Alain Louveau - 1998 - Annals of Pure and Applied Logic 92 (1):63-112.
    We consider Borel equivalence relations E induced by actions of the infinite symmetric group, or equivalently the isomorphism relation on classes of countable models of bounded Scott rank. We relate the descriptive complexity of the equivalence relation to the nature of its complete invariants. A typical theorem is that E is potentially Π03 iff the invariants are countable sets of reals, it is potentially Π04 iff the invariants are countable sets of countable sets of reals, and so (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  10.  6
    Analytic Equivalence Relations and Bi-Embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.
    Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs (or on any class of countable structures consisting of the models of a sentence of L ω ₁ ω ) is far from complete (see (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  7
    Analytic Equivalence Relations and Bi-Embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243-266.
    Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs is far from complete.In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  12. Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
    Let E be a Σ1 1 equivalence relation for which there does not exist a perfect set of inequivalent reals. If 0# exists or if V is a forcing extension of L, then there is a good ▵1 2 well-ordering of the equivalence classes.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  13.  12
    Analytic Equivalence Relations and the Forcing Method.Jindřich Zapletal - 2013 - Bulletin of Symbolic Logic 19 (4):473-490.
    I describe several ways in which forcing arguments can be used to yield clean and conceptual proofs of nonreducibility, ergodicity and other results in the theory of analytic equivalence relations. In particular, I present simple Borel equivalence relationsE, Fsuch that a natural proof of nonreducibility ofEtoFuses the independence of the Singular Cardinal Hypothesis at ℵω.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  15
    Superrigidity and Countable Borel Equivalence Relations.Simon Thomas - 2003 - Annals of Pure and Applied Logic 120 (1-3):237-262.
    We formulate a Borel version of a corollary of Furman's superrigidity theorem for orbit equivalence and present a number of applications to the theory of countable Borel equivalence relations. In particular, we prove that the orbit equivalence relations arising from the natural actions of on the projective planes over the various p-adic fields are pairwise incomparable with respect to Borel reducibility.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  15.  25
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  16.  21
    Borel Equivalence Relations and Lascar Strong Types.Krzysztof Krupiński, Anand Pillay & Sławomir Solecki - 2013 - Journal of Mathematical Logic 13 (2):1350008.
    The "space" of Lascar strong types, on some sort and relative to a given complete theory T, is in general not a compact Hausdorff topological space. We have at least three aims in this paper. The first is to show that spaces of Lascar strong types, as well as other related spaces and objects such as the Lascar group Gal L of T, have well-defined Borel cardinalities. The second is to compute the Borel cardinalities of the known examples as well (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  17.  47
    Amenable Equivalence Relations and Turing Degrees.Alexander S. Kechris - 1991 - Journal of Symbolic Logic 56 (1):182-194.
  18.  27
    Analytic Equivalence Relations and Ulm-Type Classifications.Greg Hjorth & Alexander S. Kechris - 1995 - Journal of Symbolic Logic 60 (4):1273-1300.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  19. 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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  20.  13
    Borel Equivalence Relations Which Are Highly Unfree.Greg Hjorth - 2008 - Journal of Symbolic Logic 73 (4):1271-1277.
    There is an ergodic, measure preserving, countable Borel equivalence relation E on a standard Borel probability space (X, µ) such that E\c is not essentially free on any conull C ⊂ X.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  21.  46
    Countable Borel Equivalence Relations.S. Jackson, A. S. Kechris & A. Louveau - 2002 - Journal of Mathematical Logic 2 (01):1-80.
    This paper develops the foundations of the descriptive set theory of countable Borel equivalence relations on Polish spaces with particular emphasis on the study of hyperfinite, amenable, treeable and universal equivalence relations.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  22.  69
    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   15 citations  
  23.  64
    Residuated Lattices Arising From Equivalence Relations on Boolean and Brouwerian Algebras.Thomas Vetterlein - 2008 - Mathematical Logic Quarterly 54 (4):350-367.
    Logics designed to deal with vague statements typically allow algebraic semantics such that propositions are interpreted by elements of residuated lattices. The structure of these algebras is in general still unknown, and in the cases that a detailed description is available, to understand its significance for logics can be difficult. So the question seems interesting under which circumstances residuated lattices arise from simpler algebras in some natural way. A possible construction is described in this paper.Namely, we consider pairs consisting of (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  24.  15
    On Bounded Type-Definable Equivalence Relations.Ludomir Newelski & Krzysztof Krupi?Ski - 2002 - Notre Dame Journal of Formal Logic 43 (4):231-242.
    We investigate some topological properties of the spaces of classes of bounded type-definable equivalence relations.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  25.  10
    Constructive Equivalence Relations on Computable Probability Measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
    A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  26.  34
    Une Méthode Arithmétique de Décision Pour le Système Modal S5 Par Des Invariants Numériques de Ses Classes D'Équivalence.Miguel Sánchez-Mazas - 1989 - Theoria 4 (2):491-513.
    Il s’agit d’une methode qui permet d’associer à chaque formule bien formée du système S5 de logique modale un nombre naturel invariant pour toutes les formules qui appartiennent a la même classe d’equivalence que la première.En particulier, étant donné que la méthode associe à toutes les tautologies du système le nombre o et a toutes les contradictions du système un certain nombre Φ, il suffit de calculer le nombre qui, en vertu des associations fondamentales, reste associé à n’importe (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  27.  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.
  28.  44
    On Borel Equivalence Relations in Generalized Baire Space.Sy-David Friedman & Tapani Hyttinen - 2012 - Archive for Mathematical Logic 51 (3-4):299-304.
    We construct two Borel equivalence relations on the generalized Baire space κ κ , κ <κ = κ > ω, with the property that neither of them is Borel reducible to the other. A small modification of the construction shows that the straightforward generalization of the Glimm-Effros dichotomy fails.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  29.  7
    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 \ (...)
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  30.  23
    Cofinal Families of Borel Equivalence Relations and Quasiorders.Christian Rosendal - 2005 - Journal of Symbolic Logic 70 (4):1325-1340.
    Families of Borel equivalence relations and quasiorders that are cofinal with respect to the Borel reducibility ordering, ≤B, are constructed. There is an analytic ideal on ω generating a complete analytic equivalence relation and any Borel equivalence relation reduces to one generated by a Borel ideal. Several Borel equivalence relations, among them Lipschitz isomorphism of compact metric spaces, are shown to be Kσ complete.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  31.  19
    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.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  32.  29
    Mathematical Objects Arising From Equivalence Relations and Their Implementation in Quine's NF.Thomas Forster - 2016 - Philosophia Mathematica 24 (1):nku005.
    Many mathematical objects arise from equivalence classes and invite implementation as those classes. Set-existence principles that would enable this are incompatible with ZFC's unrestricted aussonderung but there are set theories which admit more instances than does ZF. NF provides equivalence classes for stratified relations only. Church's construction provides equivalence classes for “low” sets, and thus, for example, a set of all ordinals. However, that set has an ordinal in turn which is not a member of the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  33. On Σ1 1 Equivalence Relations with Borel Classes of Bounded Rank.Ramez L. Sami - 1984 - Journal of Symbolic Logic 49 (4):1273 - 1283.
    In Baire space N = ω ω we define a sequence of equivalence relations $\langle E_\nu| \nu , each E v being Σ 1 1 with classes in Π 0 1 + ν + 1 and such that (i) E ν does not have perfectly many classes, and (ii) N/E ν is countable iff $\omega^L_\nu . This construction can be extended cofinally in (δ 1 3 ) L . A new proof is given of a theorem of Hausdorff (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  34.  19
    A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):43-46.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  35.  11
    Mathematical Objects Arising From Equivalence Relations and Their Implementation in Quine's NF.Thomas Forster - 2016 - Philosophia Mathematica 24 (1):50-59.
    Many mathematical objects arise from equivalence classes and invite implementation as those classes. Set-existence principles that would enable this are incompatible with ZFC's unrestricted _aussonderung_ but there are set theories which admit more instances than does ZF. NF provides equivalence classes for stratified relations only. Church's construction provides equivalence classes for "low" sets, and thus, for example, a set of all ordinals. However, that set has an ordinal in turn which is not a member of the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  36. Some Remarks on Definable Equivalence Relations in o-Minimal Structures.Anand Pillay - 1986 - Journal of Symbolic Logic 51 (3):709-714.
  37.  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  
  38.  3
    A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Mathematical Logic Quarterly 33 (1):43-46.
  39.  27
    Definable Equivalence Relations on Algebraically Closed Fields.Lou van den Dries, David Marker & Gary Martin - 1989 - Journal of Symbolic Logic 54 (3):928-935.
  40.  21
    New Dichotomies for Borel Equivalence Relations.Greg Hjorth & Alexander S. Kechris - 1997 - Bulletin of Symbolic Logic 3 (3):329-346.
  41.  14
    On Σ11-Complete Equivalence Relations on the Generalized Baire Space.Tapani Hyttinen & Vadim Kulikov - 2015 - Mathematical Logic Quarterly 61 (1-2):66-81.
  42.  19
    Theory of Equivalence Relations.Oystein Ore - 1943 - Journal of Symbolic Logic 8 (1):55-56.
    Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  43.  10
    Popa Superrigidity and Countable Borel Equivalence Relations.Simon Thomas - 2009 - Annals of Pure and Applied Logic 158 (3):175-189.
    We present some applications of Popa’s Superrigidity Theorem to the theory of countable Borel equivalence relations. In particular, we show that the universal countable Borel equivalence relation E∞ is not essentially free.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  44.  11
    A Note on Equivalence Relations ℓp.Su Gao & Zhi Yin - 2015 - Mathematical Logic Quarterly 61 (6):516-523.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  45.  15
    Abstraction Principles and the Classification of Second-Order Equivalence Relations.Sean C. Ebels-Duggan - 2019 - Notre Dame Journal of Formal Logic 60 (1):77-117.
    This article improves two existing theorems of interest to neologicist philosophers of mathematics. The first is a classification theorem due to Fine for equivalence relations between concepts definable in a well-behaved second-order logic. The improved theorem states that if an equivalence relation E is defined without nonlogical vocabulary, then the bicardinal slice of any equivalence class—those equinumerous elements of the equivalence class with equinumerous complements—can have one of only three profiles. The improvements to Fine’s theorem (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  46.  43
    The Effective Theory of Borel Equivalence Relations.Ekaterina B. Fokina, Sy-David Friedman & Asger Törnquist - 2010 - Annals of Pure and Applied Logic 161 (7):837-850.
    The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . In this article (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  47.  3
    On the Degree Structure of Equivalence Relations Under Computable Reducibility.Keng Meng Ng & Hongyuan Yu - 2019 - Notre Dame Journal of Formal Logic 60 (4):733-761.
    We study the degree structure of the ω-c.e., n-c.e., and Π10 equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the ω-c.e. and n-computably enumerable equivalence relations. We provide computable enumerations of the degrees of ω-c.e., n-c.e., and Π10 equivalence relations. We prove that for all (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  48.  10
    Thin Equivalence Relations in Scaled Pointclasses.Ralf Schindler & Philipp Schlicht - 2011 - Mathematical Logic Quarterly 57 (6):615-620.
    For ordinals α beginning a Σ1 gap in equation image, where equation image is closed under number quantification, we give an inner model-theoretic proof that every thin equation image equivalence relation is equation image in a real parameter from the hypothesis equation image.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  49.  25
    Treeable Equivalence Relations.Greg Hjorth - 2012 - Journal of Mathematical Logic 12 (1):1250003-.
    There are continuum many ≤B-incomparable equivalence relations induced by a free, Borel action of a countable non-abelian free group — and hence, there are 2α0 many treeable countable Borel equivalence relations which are incomparable in the ordering of Borel reducibility.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  50.  36
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
1 — 50 / 999