Given a Polish groupG, let$E(G)$be the right coset equivalence relation$G^{\omega }/c(G)$, where$c(G)$is the group of all convergent sequences inG. The connected component of the identity of a Polish groupGis denoted by$G_0$.Let$G,H$be locally compact abelian Polish groups. If$E(G)\leq _B E(H)$, then there is a continuous homomorphism$S:G_0\rightarrow H_0$such that$\ker (S)$is non-archimedean. The converse is also true whenGis connected and compact.For$n\in {\mathbb {N}}^+$, the partially ordered set$P(\omega )/\mbox {Fin}$can be embedded into Borel equivalence relations between$E({\mathbb {R}}^n)$and$E({\mathbb {T}}^n)$.

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.

We introduce the notion of -determinacy for Γ a pointclass and E an equivalence relation on a Polish space X. A case of particular interest is the case when E = EG is the shift-action o...

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 \ (...) class='Hi'>equivalence relations. A special focus of our work is on the existence of infima and suprema of c-degrees. (shrink)

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.

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.

We study the complexity of isomorphism of classes of metric structures using methods from infinitary continuous logic. For Borel classes of locally compact structures, we prove that if the equivalence relation of isomorphism is potentially $\mathbf {\Sigma }^0_2$, then it is essentially countable. We also provide an equivalent model-theoretic condition that is easy to check in practice. This theorem is a common generalization of a result of Hjorth about pseudo-connected metric spaces and a result of Hjorth–Kechris about discrete (...) structures. As a different application, we also give a new proof of Kechris’s theorem that orbit equivalence relations of actions of Polish locally compact groups are essentially countable. (shrink)

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 [5, 2]). In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of ω ₁ ω , but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids. (shrink)

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 ℵω.

The following will be shown: Let I be a σ-ideal on a Polish space X so that the associated forcing of I+${\bf{\Delta }}_1^1$ sets ordered by ⊆ is a proper forcing. Let E be a ${\bf{\Sigma }}_1^1$ or a ${\bf{\Pi }}_1^1$ equivalence relation on X with all equivalence classes ${\bf{\Delta }}_1^1$. If for all $z \in {H_{{{\left}^ + }}}$, z♯ exists, then there exists an I+${\bf{\Delta }}_1^1$ set C ⊆ X such that E ↾ C is a (...) ${\bf{\Delta }}_1^1$ equivalence relation. (shrink)

I examine notions of equivalence between logics (understood as languages interpreted model-theoretically) and develop two new ones that invoke not only the algebraic but also the string-theoretic structure of the underlying language. As an application, I show how to construe modal operator languages as what might be called typographical notational variants of _bona fide_ first-order languages.

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).

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.

Let E be an equivalence relation on the powerset of an uncountable set, which is reasonably definable. We assume that any two subsets with symmetric difference of size exactly 1 are not equivalent. We investigate whether for E there are many pairwise non equivalent sets.

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 its own sake, does (...) not cut in the debate concerning the conventionality of simultaneity in special relativity. (shrink)

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 on. The proofs use various techniques, including Vaught transforms, changing topologies, and the Scott analysis of countable models. (shrink)

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.

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.

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 follows, we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general. (shrink)

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.

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, (...) such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous. (shrink)

We consider the equivalence relations on induced by the Banach subspaces. We show that if, then there is no Borel reduction from the equivalence relation, where X is a Banach space, to.

The lattice of r.e. equivalence relations has not been carefully examined even though r.e. equivalence relations have proved useful in logic. A maximal r.e. equivalence relation has the expected lattice theoretic definition. It is proved that, in every pair of r.e. nonrecursive Turing degrees, there exist maximal r.e. equivalence relations which intersect trivially. This is, so far, unique among r.e. submodel lattices.

In this paper we study the reducibility order m (defined in a natural way) over n 0 -equivalence relations. In particular, for every n> 0 we exhibit n 0 -equivalence relations which are complete with respect to m and investigate some consequences of this fact (see Introduction).

We study Schauder equivalence relations, which are Borel equivalence relations induced by actions of Banach spaces with Schauder bases. Firstly, we show that and are minimal Schauder equivalence relations. Then, we prove that neither of them is Borel reducible to the quotient where T is the Tsirelson space. This implies that they cannot form a basis for the Schauder equivalence relations. In addition, we apply an argument of Farah to show that every basis for the Schauder (...) equivalence relations, if such exist, has to be of cardinality. (shrink)

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 on (...) partitions of R into ω 1 many Π 0 3 sets. (shrink)

Working under large cardinal assumptions such as supercompactness, we study the Borel reducibility between equivalence relations modulo restrictions of the nonstationary ideal on some fixed cardinal κ. We show the consistency of Eλ-clubλ++,λ++, the relation of equivalence modulo the nonstationary ideal restricted to Sλλ++ in the space λ++, being continuously reducible to Eλ+-club2,λ++, the relation of equivalence modulo the nonstationary ideal restricted to Sλ+λ++ in the space 2λ++. Then we show that for κ ineffable Ereg2,κ, (...) the relation of equivalence modulo the nonstationary ideal restricted to regular cardinals in the space 2κ is Σ11-complete. We finish by showing that, for Π21-indescribable κ, the isomorphism relation between dense linear orders of cardinality κ is Σ11-complete. (shrink)

We propose a canonization scheme for smooth equivalence relations on Rω modulo restriction to E0-large infinite products. It shows that, given a pair of Borel smooth equivalence relations E, F on Rω, there is an infinite E0-large perfect product P⊆Rω such that either F⊆E on P, or, for some ℓ<ω, the following is true for all x,y∈P: xEy implies x(ℓ)=y(ℓ), and x↾(ω∖{ℓ})=y↾(ω∖{ℓ}) implies xFy.

We make some beginning observations about the category Eq of equivalence relations on the set of natural numbers, where a morphism between two equivalence relations R and S is a mapping from the set of R-equivalence classes to that of S-equivalence classes, which is induced by a computable function. We also consider some full subcategories of Eq, such as the category Eq(Σ01) of computably enumerable equivalence relations (called ceers), the category Eq(Π01) of co-computably enumerable (...) class='Hi'>equivalence relations, and the category Eq(Dark*) whose objects are the so-called dark ceers plus the ceers with finitely many equivalence classes. Although in all these categories the monomorphisms coincide with the injective morphisms, we show that in Eq(Σ01) the epimorphisms coincide with the onto morphisms, but in Eq(Π01) there are epimorphisms that are not onto. Moreover, Eq, Eq(Σ01), and Eq(Dark*) are closed under finite products, binary coproducts, and coequalizers, but we give an example of two morphisms in Eq(Π01) whose coequalizer in Eq is not an object of Eq(Π01). (shrink)

We prove Borel superrigidity results for suitably chosen actions of groups of the form SL2, where {p1, …, pt} is a finite nonempty set of primes, and present a number of applications to the theory of countable Borel equivalence relations. In particular, for each prime q, we prove that the orbit equivalence relations arising from the natural actions of SL2 on the projective lines ℚp ∪ {∞}, p ≠ q, over the various p-adic fields are pairwise incomparable with (...) respect to Borel reducibility. (shrink)

We establish Hjorth's theorem that there is a family of continuum-many pairwise strongly incomparable free actions of free groups, and therefore a family of continuum-many pairwise incomparable treeable equivalence relations.

Let X, Y be Polish spaces,,. We say A is universal for Γ provided that each x‐section of A is in Γ and each element of Γ occurs as an x‐section of A. An equivalence relation generated by a set is denoted by, where. The following results are shown: If A is a set universal for all nonempty closed subsets of Y, then is a equivalence relation and. If A is a set universal for all countable (...) subsets of Y, then is a equivalence relation, and and ; if, then ; if every set is Lebesgue measurable or has the Baire property, then. for, if every set has the Baire property, and E is any equivalence relation, then. (shrink)

It is known that every Borel hypersmooth but non-smooth equivalence relation is Borel bi-reducible to E1. We prove a ROD version of this result in the Solovay model.

We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

Assuming every real has a sharp, we prove that for any $\mathop \prod \limits_\~ _1^1 $ equivalence relation either Borel reduces E₀ or in a $\mathop \Delta \limits_\~ _3^1 $ manner allows the assignment of bounded subsets of ω₁ as complete invariants.

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.

We introduce a new family of jump operators on Borel equivalence relations; specifically, for each countable group [Formula: see text] we introduce the [Formula: see text]-jump. We study the elementary properties of the [Formula: see text]-jumps and compare them with other previously studied jump operators. One of our main results is to establish that for many groups [Formula: see text], the [Formula: see text]-jump is proper in the sense that for any Borel equivalence relation [Formula: see text] (...) the [Formula: see text]-jump of [Formula: see text] is strictly higher than [Formula: see text] in the Borel reducibility hierarchy. On the other hand, there are examples of groups [Formula: see text] for which the [Formula: see text]-jump is not proper. To establish properness, we produce an analysis of Borel equivalence relations induced by continuous actions of the automorphism group of what we denote the full [Formula: see text]-tree, and relate these to iterates of the [Formula: see text]-jump. We also produce several new examples of equivalence relations that arise from applying the [Formula: see text]-jump to classically studied equivalence relations and derive generic ergodicity results related to these. We apply our results to show that the complexity of the isomorphism problem for countable scattered linear orders properly increases with the rank. (shrink)

Infants' knowledge need not have the same structure as the mature knowledge that develops from it. Fundamental to an understanding of number are concepts of equivalence and less-than and greater-than relations. These concepts, together with the concept of unit, are posited to be the starting points for the development of numerical knowledge.

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 equivalence relations and show that existence of infinitely many properly Σ11 equivalence classes that are complete as Σ11 sets is necessary but not sufficient for a relation to be complete in the context of Σ11 equivalence relations. (shrink)