Introduction A) This paper is a contribution to the theory of countable Borel equivalence relations on standard Borel spaces. As usual, by a standard Borel space we mean a Polish (complete separable metric) space equipped with its a-algebra of Borel sets. An equivalence relation ^ o n a standard Borel space X is Borel if it is a Borel subset of A 2 . Given two equivalence relations E,F on spaces A, Y, resp., we say that E is Borel reducible to F, in symbols, EBF, if there is a Borel map p : X — Y such that xEy&p(x)Fp(y). We also say that E is Borel bireducible to F, in symbols E~BF if E B F and F B E. Finally put E B F ^ E B F & F ^B E. We refer the reader to [Ke99] for a detailed discussion of the motivation for the study of the reducibility order on Borel (and more general definable) equivalence relations. On the one hand, this can be viewed as providing the basic underlying concept for the development of a theory of complexity of classification problems in mathematics. On the other hand, it can be understood as the basis of a theory of Borel (as opposed to the classical Cantor) cardinality of quotients of standard Borel spaces by Borel equivalence relations. One can view here E B F as expressing that XjE has Borel cardinality to that of Y/F, and E ~B F as expressing that X/Ej Y/F have the same Borel cardinality. In this paper, we will only discuss countable Borel equivalence relations. An equivalence relation E on a space X is called countable if every equivalence class [x]^,^ G A, is countable. These include many important examples, like, for in- stance, all equivalence relations induced by Borel actions of countable (discrete) groups on standard Borel spaces, and, up to bireducibility, even those induced by Borel actions of Polish locally compact groups, the isomorphism relation on various types of countable structures that have "finite type" (again this is up to bireducibility), Turing or arithmetical equivalence, etc. Their study is actually closely connected with ergodic theory and other areas in dynamical systems, since by a result of Feldman-Moore [FM], the countable Borel equivalence relations are in fact exactly those induced by Borel actions of countable groups on standard Borel spaces. 1

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2005 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.