The structure of hyperfinite Borel equivalence relations

We study the structure of the equivalence relations induced by the orbits of a single Borel automorphism on a standard Borel space.We show that any two such equivalence relations which are not smooth, i.e., do not admit Borel selectors, are Borel embeddable into each other.(This utilizes among other things work of Effros and Weiss.)Using this and also results of Dye, Varadarajan, and recent work of Nadkarni, we show that the cardinality of the set of ergodic invariant measures is a complete invariant for Borel isomorphism of aperiodic nonsmooth such equivalence relations.In particular, since the only possible such cardinalities are the finite ones, countable infinity, and the cardinality of the continuum, there are exactly countably infinitely many isomorphism types.Canonical examples of each type are also discussed.This paper is a contribution to the study of Borel equivalence relations on standard Borel spaces.We concentrate here on the study of the hyperfinite ones.These are by definition the increasing unions of sequences of Borel equivalence relations with finite equivalence classes but equivalently they can be also described as the ones induced by the orbits of a single Borel automorphism.They include therefore a great variety of examples, some of them discussed in 6.For instance, the equivalence relations: Fn on 2N (where xE0y iff x, y are eventually equal, i.e., 3Vw > n(xm = ym)), Et on 2N (where xEty iff x, y have equal tails, i.e., 3n3mVk(xn+k = ym+k)), E(Z,2) on 2Z (where xE(Z,2)y iff x is a shift of y), Ea on the unit circle T (where a T and xEay iff x is the rotation of y by na, n %), F(R/Q) on R (the Vitali equivalence relation, i.e., xE(R/Q)y iff x -y Q), are all hyperfinite.Our main results in this paper provide a classification of hyperfinite Borel equivalence relations under two different notions of equivalence.The weaker one, which we call bi-embeddability, is the following: Given hyperfinite Borel equivalence relations E, F (on X, Y resp.)we say that E embeds into F, in symbols E C F, if there is a Borel injection /:I->7 such that xEy f(x)Ff(y).Then E, F are bi-embeddable, in symbols E F , if F C F and F E. As it turns out, except for the trivial class of smooth relations, i.e., those having Borel selectors, any two hyperfinite Borel equivalence relations are bi-embeddable; i.e., we have