§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this theory sets are (...) classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (shrink)

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 announce two new dichotomy theorems for Borel equivalence relations, and present the results in context by giving an overview of related recent developments.§1. Introduction. For X a Polish space and E a Borel equivalence relation on X, a classification of X up to E-equivalence consists of finding a set of invariants I and a map c : X → I such that xEy ⇔ c = c. To be of any value we would expect I and c to be (...) “explicit” or “definable”. The theory of Borel equivalence relations investigates the nature of possible invariants and provides a hierarchy of notions of classification.The following partial ordering is fundamental in organizing this study. Given equivalence relations E and F on X and Y, resp., we say that E can be Borel reduced to F, in symbolsif there is a Borel map f : X → Y with xEy ⇔ fFf. Then if is an embedding of X/E into Y/F, which is “Borel”.Intuitively, E ≤BF might be interpreted in any one of the following ways: The classi.cation problem for E is simpler than that of F: any invariants for F work as well for E. One can classify E by using as invariants F-equivalence classes. The quotient space X/E has “Borel cardinality” less than or equal to that of Y/F, in the sense that there is a “Borel” embedding of X/E into Y/F. (shrink)

We announce two new dichotomy theorems for Borel equivalence relations, and present the results in context by giving an overview of related recent developments.§1. Introduction. For X a Polish space and E a Borel equivalence relation on X, a classification of X up to E-equivalence consists of finding a set of invariants I and a map c : X → I such that xEy ⇔ c = c. To be of any value we would expect I and c to be (...) “explicit” or “definable”. The theory of Borel equivalence relations investigates the nature of possible invariants and provides a hierarchy of notions of classification.The following partial ordering is fundamental in organizing this study. Given equivalence relations E and F on X and Y, resp., we say that E can be Borel reduced to F, in symbolsif there is a Borel map f : X → Y with xEy ⇔ fFf. Then if is an embedding of X/E into Y/F, which is “Borel”.Intuitively, E ≤BF might be interpreted in any one of the following ways: The classi.cation problem for E is simpler than that of F: any invariants for F work as well for E. One can classify E by using as invariants F-equivalence classes. The quotient space X/E has “Borel cardinality” less than or equal to that of Y/F, in the sense that there is a “Borel” embedding of X/E into Y/F. (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 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)