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.

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.

Given a countable transitive model of set theory and a partial order contained in it, there is a natural countable Borel equivalence relation on generic filters over the model; two are equivalent if they yield the same generic extension. We examine the complexity of this equivalence relation for various partial orders, focusing on Cohen and random forcing. We prove, among other results, that the former is an increasing union of countably many hyperfinite Borel equivalence relations, and hence is amenable, while (...) the latter is neither amenable nor treeable. (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)

The Filter Dichotomy says that every uniform nonmeager filter on the integers is mapped by a finite-to-one function to an ultrafilter. The consistency of this principle was proved by Blass and Laflamme. A medial limit is a universally measurable function from [Formula: see text] to the unit interval [0, 1] which is finitely additive for disjoint sets, and maps singletons to 0 and ω to 1. Christensen and Mokobodzki independently showed that the Continuum Hypothesis implies the existence of medial limits. (...) We show that the Filter Dichotomy implies that there are no medial limits. (shrink)

We show that if add(null) = c, then the globally Baire and universally measurable chromatic numbers of the graph of any Borel function on a Polish space are equal and at most three. In particular, this holds for the graph of the unilateral shift on [N]N, although its Borel chromatic number is N₀. We also show that if add(null) = c, then the universally measurable chromatic number of every treeing of a measure amenable equivalence relation is at most three. In (...) particular, this holds for "the" minimum analytic graph G₀ with uncountable Borel (and Baire measurable) chromatic number. In contrast, we show that for all κ ∈ {2, 3...., N₀. c}, there is a treeing of E₀ with Borel and Baire measurable chromatic number κ. Finally, we use a Glimm—Effros style dichotomy theorem to show that every basis for a non-empty initial segment of the class of graphs of Borel functions of Borel chromatic number at least three contains a copy of (R<N, ⊇). (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.

We prove a number of results motivated by global questions of uniformity in computabi- lity theory, and universality of countable Borel equivalence relations. Our main technical tool is a game for constructing functions on free products of countable groups. We begin by investigating the notion of uniform universality, first proposed by Montalbán, Reimann and Slaman. This notion is a strengthened form of a countable Borel equivalence relation being universal, which we conjecture is equivalent to the usual notion. With this additional (...) uniformity hypothesis, we can answer many questions concerning how countable groups, probability measures, the subset relation, and increasing unions interact with universality. For many natural classes of countable Borel equivalence relations, we can also classify exactly which are uniformly universal. We also show the existence of refinements of Martin’s ultrafilter on Turing invariant Borel sets to the invariant Borel sets of equivalence relations that are much finer than Turing equivalence. For example, we construct such an ultrafilter for the orbit equivalence relation of the shift action of the free group on countably many generators. These ultrafilters imply a number of structural properties for these equivalence relations. (shrink)

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 (...) as of some new examples that we give. The third is to explore notions of definable map, embedding, and isomorphism, between these and related quotient objects. We also make some conjectures, the main one being roughly "smooth if and only if trivial". The possibility of a descriptive set-theoretic account of the complexity of spaces of Lascar strong types was touched on in the paper [E. Casanovas, D. Lascar, A. Pillay and M. Ziegler, Galois groups of first order theories, J. Math. Logic1 305–319], where the first example of a "non-G-compact theory" was given. The motivation for writing this paper is partly the discovery of new examples via definable groups, in [A. Conversano and A. Pillay, Connected components of definable groups and o-minimality I, Adv. Math.231 605–623; Connected components of definable groups and o-minimality II, to appear in Ann. Pure Appl. Logic] and the generalizations in [J. Gismatullin and K. Krupiński, On model-theoretic connected components in some group extensions, preprint, arXiv:1201.5221v1]. (shrink)

In "A proof of Vaught's conjecture for ω-stable theories," the notions of ENI-NDOP and eni-depth have been introduced, which are variants of the notions of NDOP and depth known from Shelah's classification theory. First, we show that for an ω-stable first-order complete theory, ENI-NDOP allows tree decompositions of countable models. Then we discuss the relationship between eni-depth and the complexity of the isomorphism relation for countable models of such a theory in terms of Borel reducibility as introduced by Friedman and (...) Stanley and construct, in particular, a sequence of complete first-order ω-stable theories $(T_\alpha)_{\alpha < \omega_1}$ with increasing and cofinal eni-depth and isomorphism relations which are strictly increasing with respect to Borel reducibility. (shrink)

We present a countable complete first order theory T which is model theoretically very well behaved: it eliminates quantifiers, is ω-stable, it has NDOP and is shallow of depth two. On the other hand, there is no countable bound on the Scott heights of its countable models, which implies that the isomorphism relation for countable models is not Borel.

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.

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space.For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, (...) such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models.This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that theBorel cardinalitiesof the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action.One of the first things to be addressed concerns the complexity of these equivalence relations. This question forappears in [1]. (shrink)

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 prove that if p ≠ q are distinct primes, then the classification problems for p-local and q-local torsion-free abelian groups of rank two are incomparable with respect to Borel reducibility.

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 we examine the effective (...) content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)

We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time generalization of the (...) countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions. (shrink)

Boykin and Jackson recently introduced a property of countable Borel equivalence relations called Borel boundedness, which they showed is closely related to the union problem for hyperfinite equivalence relations. In this paper, we introduce a family of properties of countable Borel equivalence relations which correspond to combinatorial cardinal characteristics of the continuum in the same way that Borel boundedness corresponds to the bounding number. We analyze some of the basic behavior of these properties, showing, e.g., that the property corresponding to (...) the splitting number coincides with smoothness. We then settle many of the implication relationships between the properties; these relationships turn out to be closely related to (but not the same as) the Borel Tukey ordering on cardinal characteristics. (shrink)

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)

In this paper we show that there are "E₀ many" orbit inequivalent free actions of the free groups Fn. 2 ≤ n ≤ ∞ by measure preserving transformations on a standard Borel probability space. In particular, there are uncountably many such actions.