B. Miller

We show that if an equivalence relation E on a Polish space is a countable union of smooth Borel subequivalence relations, then there is either a Borel reduction of E to a countable Borel equivalence relation on a Polish space or a continuous embedding of 𝔼₁ into E. We also establish related results concerning countable unions of more general Borel equivalence relations.

We establish generalizations of the Feldman–Moore theorem, the Glimm–Effros dichotomy, and the Lusin–Novikov uniformization theorem from Polish spaces to their quotients by Borel orbit equivalence relations.

We establish a generalization and strengthening of the marker lemma for Borel automorphisms that can also be viewed as a measureless strengthening of Dowker's ratio ergodic theorem.

We generalize the 𝔾₀ dichotomy to doubly-indexed sequences of analytic digraphs. Under a mild definability assumption, we use this generalization to characterize the family of Borel actions of tsi Polish groups on Polish spaces that can be decomposed into countably-many Borel actions admitting complete Borel sets that are lacunary with respect to an open neighborhood of the identity. We also show that if the group in question is non-archimedean, then the inexistence of such a decomposition yields a special kind of continuous embedding of 𝔼₃ into the corresponding orbit equivalence relation.

We show that Li–Yorke chaos ensures the existence of a scrambled Cantor set.

We generalize Kada's definable strengthening of Dilworth's characterization of the class of quasi-orders admitting an antichain of a given finite cardinality.

We show that recurrence conditions do not yield invariant Borel probability measures in the descriptive set-theoretic milieu, in the strong sense that if a Borel action of a locally compact Polish group on a standard Borel space satisfies such a condition but does not have an orbit supporting an invariant Borel probability measure, then there is an invariant Borel set on which the action satisfies the condition but does not have an invariant Borel probability measure.

We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel chromatic number at least three. Moreover, we characterize the Borel graphs on standard Borel spaces of vertex-degree at most two with this property, and show that the analogous result for digraphs fails.

We show that a natural generalization of compressibility is the sole obstruction to the existence of a cocycle-invariant Borel probability measure.

We provide a finite basis for the class of Borel functions that are not in the first Baire class, as well as the class of Borel functions that are not σ-continuous with closed witnesses.

We show that several dichotomy theorems concerning the second level of the Borel hierarchy are special cases of the ℵ₀-dimensional generalization of the open graph dichotomy, which itself follows from the usual proof(s) of the perfect set theorem. Under the axiom of determinacy, we obtain the generalizations of these results from analytic to separable metric spaces. We also consider connections between cardinal invariants and the chromatic numbers of the corresponding dihypergraphs.

We simultaneously generalize Silver's perfect set theorem for co-analytic equivalence relations and Harrington–Marker–Shelah's Dilworth-style perfect set theorem for Borel quasi-orders, establish the analogous theorem at the next definable cardinal, and give further generalizations under weaker definability conditions.

Suppose that X is a Polish space, E is a countable Borel equivalence relation on X, and μ is an E-invariant Borel probability measure on X. We consider the circumstances under which for every countable non-abelian free group Γ, there is a Borel sequence (·_r)_r∈ℝ of free actions of Γ on X, generating subequivalence relations E_r of E with respect to which μ is ergodic, with the further property that (E_r)_r∈ℝ is an increasing sequence of relations which are pairwise incomparable under μ-reducibility. In particular, we show that if E satisfies a natural separability condition, then this is the case as long as there exists a free Borel action of a countable non-abelian free group on X, generating a subequivalence relation of E with respect to which μ is ergodic.

We use variants of the 𝔾₀ dichotomy to establish a refinement of Solecki's basis theorem for the family of Baire-class one functions which are not σ-continuous with closed witnesses.

We characterize the structural impediments to the existence of Borel perfect matchings for acyclic locally countable Borel graphs admitting a Borel selection of finitely many ends from their connected components. In particular, this yields the existence of Borel matchings for such graphs of degree at least three. As a corollary, it follows that acyclic locally countable Borel graphs of degree at least three generating μ-hyperfinite equivalence relations admit μ-measurable matchings. We establish the analogous result for Baire measurable matchings in the locally finite case, and provide a counterexample in the locally countable case.

We prove that for every Borel equivalence relation E, either E is Borel reducible to 𝔼₀, or the family of Borel equivalence relations incompatible with E has cofinal essential complexity. It follows that if F is a Borel equivalence relation and ℱ is a family of Borel equivalence relations of non-cofinal essential complexity which together satisfy the dichotomy that for every Borel equivalence relation E, either E ∈ ℱ or F is Borel reducible to E, then ℱ consists solely of smooth equivalence relations, thus the dichotomy is equivalent to a known theorem.

Burgess–Mauldin have proven the Ramsey-theoretic result that continuous sequences (μ_c)_c∈2^ℕ of pairwise orthogonal Borel probability measures admit continuous orthogonal subsequences. We establish an analogous result for sequences indexed by 2^ℕ/𝔼₀, the next Borel cardinal. As a corollary, we obtain a strengthening of the Harrington–Kechris–Louveau 𝔼₀ dichotomy for restrictions of measure equivalence. We then use this to characterize the family of countable Borel equivalence relations which are non-hyperfinite with respect to an ergodic Borel probability measure that is not strongly ergodic.

We show that every basis for the countable Borel equivalence relations strictly above 𝔼₀ under measure reducibility is uncountable, thereby ruling out natural generalizations of the Glimm–Effros dichotomy. We also push many known results concerning the abstract structure of the measure reducibility hierarchy to its base, using arguments substantially simpler than those previously employed.

We show that the Baire measurable chromatic number of every locally finite Borel graph on a non-empty Polish space is strictly less than twice its ordinary chromatic number, provided this ordinary chromatic number is finite. In the special case that the connectedness equivalence relation is hyperfinite, we obtain the analogous result for the μ-measurable chromatic number.

We give a classical proof of the generalization of the characterization of smoothness to quotients of Polish spaces by Borel equivalence relations. As an application, we describe the extent to which any given Borel equivalence relation on a Polish space is encoded by the corresponding σ-ideal generated by the family of Borel sets on which it is smooth.

We provide a new criterion for embedding 𝔼₀ and apply it to equivalence relations in model theory. This generalizes the results of the authors and Pierre Simon on the Borel cardinality of Lascar strong types equality, and Newelski’s results about pseudo F_σ groups.

We show that if the restriction of the Lascar equivalence relation to a KP-strong type is non-trivial, then it is non-smooth (when viewed as a Borel equivalence elation on an appropriate space of types).

We establish a dichotomy theorem characterizing the circumstances under which a treeable Borel equivalence relation E is essentially countable. Under additional topological assumptions on the treeing, we in fact show that E is essentially countable if and only if there is no continuous embedding of 𝔼₁ into E. Our techniques also yield the first classical proof of the analogous result for hypersmooth equivalence relations, and allow us to show that, up to continuous Kakutani embeddability, there is a minimum Borel function which is not essentially countable-to-one.

We answer in the negative a question posed by Kechris–Solecki–Todorcevic as to whether the shift graph on Baire space is minimal among graphs of indecomposably infinite Borel chromatic number. To do so, we use ergodic-theoretic techniques to construct a new graph amalgamating various properties of the shift actions of free groups. The resulting graph is incomparable with any graph induced by a function. We then generalize this construction and collect some of its useful properties.

We establish the generic inexistence of stationary Borel probability measures for aperiodic Borel actions of countable groups on Polish spaces. Using this, we show that every aperiodic continuous action of a countable group on a compact Polish space has an invariant Borel set on which it has no σ-compact realization.

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 sketch the ideas behind the use of chromatic numbers in establishing descriptive set-theoretic dichotomy theorems.

We characterize the class of definable families of countable sets for which there is a single countable definable set intersecting every element of the family.

We give classical proofs, strengthenings, and generalizations of Lecomte's characterizations of analytic ω-dimensional hypergraphs with countable Borel chromatic number.

We give a classical proof of the Kanovei–Zapletal canonization of Borel equivalence relations on Polish spaces.

We consider a descriptive set-theoretic analog of Kakutani equivalence for Borel automorphisms of Polish spaces. Answering a question of Nadkarni, we show that up to this notion, there are exactly two aperiodic Borel automorphisms of uncountable Polish spaces. Using this, we classify all Borel ℝ-flows up to C^∞-time-change isomorphism. We then extend the notion of descriptive Kakutani equivalence to all (not necessarily injective) Borel functions, and provide a variety of results leading towards a complete classification. The main technical tools are a series of Glimm–Effros and Dougherty–Jackson–Kechris-style embedding theorems.

Given a graphing G of a countable Borel equivalence relation on a Polish space, we show that if there is a Borel way of selecting a non-empty closed set of countably many ends from each G-component, then there is a Borel way of selecting an end or line from each G-component. Our method yields also Glimm–Effros style dichotomies which characterize the circumstances under which: (1) there is a Borel way of selecting a point or end from each G-component, and (2) there is a Borel way of selecting a point, end, or line from each G-component.

Given a countable Borel equivalence relation E on a Polish space, we show: (1) E admits an endless graphing if and only if E is smooth, (2) E admits a locally finite single-ended graphing if and only if E is aperiodic, (3) E admits a graphing for which there is a Borel way of selecting two ends from each component if and only if E is hyperfinite, and (4) E admits a graphing for which there is a Borel way of selecting a finite set of at least three ends from each component if and only if E is smooth.

We show that there is an antichain basis for neither (1) the class of non-potentially closed Borel subsets of the plane under Borel rectangular reducibility nor (2) the class of analytic graphs of uncountable Borel chromatic number under Borel reducibility.

We show that if add(null) = 𝔠, 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 [ℕ]^ℕ, although its Borel chromatic number is ℵ₀. We also show that if add(null) = 𝔠, 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 𝔾₀ with uncountable Borel (and Baire measurable) chromatic number. In contrast, we show that for all κ ∈ {2, 3, . . . , ℵ₀, 𝔠}, there is a treeing of 𝔼₀ 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 (ℝ^<ℕ, ⊇).

Given a Polish space X, a countable Borel equivalence relation E on X, and a Borel cocycle ρ : E → (0, ∞), we characterize the circumstances under which there is a probability measure μ on X such that ρ(φ^-1(x), x) = [d(φ∗μ)/dμ](x) μ-almost everywhere, for every Borel injection φ whose graph is contained in E.

Given a Polish space X, a countable Borel equivalence relation E on X, and a Borel cocycle ρ : E → (0, ∞), we characterize the circumstances under which there is a suitably non-trivial σ-finite measure μ on X such that ρ(φ^-1(x), x) = [d(φ∗μ)/dμ](x) μ-almost everywhere, for every Borel injection φ whose graph is contained in E.

Suppose that X is a Polish space and E is a countable Borel equivalence relation on X. We show that if there is a Borel assignment of means to the equivalence classes of E, then E is smooth. We also show that if there is a Baire measurable assignment of means to the equivalence classes of E, then E is generically smooth.

Answering a question of Kłopotowski–Nadkarni–Sarbadhikari–Srivastava, we characterize the Borel sets S ⊆ X × Y on which every Borel function f : S → ℂ is of the form uv|S, where u : X → ℂ and v : Y → ℂ are Borel.

Suppose that G and H are Polish groups which act in a Borel fashion on Polish spaces X and Y. Let E_G and E_H denote the corresponding orbit equivalence relations, and [G] and [H] the corresponding Borel full groups. Modulo the obvious counterexamples, we show that [G] ≅ [H] ⇔ E_G ≅_B E_H.

Given Polish spaces X and Y and a Borel set S ⊆ X × Y with countable sections, we describe the circumstances under which a Borel function f : S → ℝ is of the form f(x, y) = u(x) + v(y), where u : X → ℝ and v : Y → ℝ are Borel. This turns out to be a special case of the problem of determining whether a real-valued Borel cocycle on a countable Borel equivalence relation is a coboundary. We use several Glimm–Effros style dichotomies to give a solution to this problem in terms of certain σ-finite measures on the underlying space. The main new technical ingredient is a characterization of the existence of type III measures of a given cocycle.

In Chapter I, we study algebraic properties of full groups of automorphisms of σ-complete Boolean algebras. We consider problems of writing automorphisms as compositions of periodic automorphisms and commutators (generalizing work of Fathi and Ryzhikov), as well as problems concerning the connection between normal subgroups of a full group and ideals on the underlying algebra, in the process giving a new proof (joint with David Fremlin) of Shortt's characterization of the normal subgroups of the group of Borel automorphisms of an uncountable Polish space, as well as a characterization of the normal subgroups of full groups of countable Borel equivalence relations which are closed in the uniform topology of Bezuglyi–Dooley–Kwiatkowski. We also characterize the existence of an E-invariant Borel probability measure in terms of a purely algebraic property of [E]. The results of Chapter II include classifications of Borel automorphisms and Borel forests of lines up to the descriptive analog of Kakutani equivalence, along with applications to the study of Borel marriage problems, generalizing and strengthening results of Shelah–Weiss, Dougherty–Jackson–Kechris, and Kłopotowski–Nadkarni–Sarbadhikari–Srivastava. We also study the sorts of full groups on quotients of the form X/E for which the results of Chapter I do not apply. Actions of such groups satisfy a measureless ergodicity property which we exploit to obtain various classification and rigidity results. In particular, we obtain descriptive analogs of some results of Connes–Krieger and Feldman–Sutherland–Zimmer, answering a question of Bezuglyi. In Chapter III, we study some descriptive properties of quasi-invariant measures. We prove a general selection theorem, and use this to show a descriptive set-theoretic strengthening of an analog of the Hurewicz ergodic theorem which holds for all countable Borel equivalence relations. This then leads to new proofs of Ditzen’s quasi-invariant ergodic decomposition theorem and Nadkarni’s characterization of the existence of an E-invariant probability measure, and also gives rise to a quasi-invariant version of Nadkarni’s theorem, as well as a version for countable-to-one Borel functions. We close chapter III with results on graphings of countable Borel equivalence relations, strengthening theorems of Adams and Paulin.

This volume provides a self-contained introduction to some topics in orbit equivalence theory, a branch of ergodic theory. The first two chapters focus on hyperfiniteness and amenability. Included here are proofs of Dye's theorem that probability measure-preserving, ergodic actions of the integers are orbit equivalent and of the theorem of Connes–Feldman–Weiss identifying amenability and hyperfiniteness for non-singular equivalence relations. The presentation here is often influenced by descriptive set theory, and Borel and generic analogs of various results are discussed. The final chapter is a detailed account of Gaboriau's recent results on the theory of costs for equivalence relations and groups and its applications to proving rigidity theorems for actions of free groups.

We show that the existence of an invariant probability measure for a countable Borel equivalence relation with no singleton classes is equivalent to a first-order property of its full group.

We show that if a countable Borel equivalence relation is in the closure of the class of all smooth Borel equivalence relations under countable increasing union and countable intersection, then it is measure hyperfinite.

We give first-order properties of the full group of an aperiodic countable Borel equivalence relation that characterize the existence of an invariant probability measure.

We introduce essential values of Borel cocycles from analytic equivalence relations to countable discrete groups, establish a Glimm–Effros-style characterization of the circumstances under which such cocycles have a given non-trivial essential value, and obtain a Dougherty–Jackson–Kechris-style embedding theorem for such cocyles with hyperfinite domains. We then use these results to classify suitably Borel finite equivalence relations and free actions of finite groups on ℝ/ℚ. Assuming that (ℤ∗ℤ)-orderable Borel equivalence relations are hyperfinite, we also show that every suitably Borel automorphism of ℝ/ℚ is both a product of three involutions and a commutator, and that the group of all such automorphisms has exactly four proper normal subgroups and the 12-Bergman property.

We introduce a notion of separability that holds of all Borel automorphisms of standard Borel spaces and automorphisms of complete Boolean algebras. We then prove that separable automorphisms of σ-complete Boolean algebras are products of various types of periodic automorphisms in their full groups. As applications, we show that a wide variety of groups of automorphisms consist solely of commutators and satisfy the Bergman property, that natural strengthenings of the Bergman property characterize the inexistence of invariant Borel probability measures in standard Borel spaces and standard measure spaces, and that the length four normal closure of any Borel automorphism of ℝ with uncountable support is the group of all Borel automorphisms of ℝ.

We establish a dichotomy characterizing the class of (E × Δ(Y))-invariant Borel sets R ⊆ X × Y, whose vertical sections are countable, that admit (E × Δ(Y))-invariant Borel uniformizations, where X and Y are Polish spaces and E is a Borel equivalence relation on X. We achieve this by establishing a dichotomy characterizing the class of Borel equivalence relations F ⊆ E, where F has countable index below E and satisfies an additional technical definability condition, for which there is a Borel set intersecting each E-class in a non-empty finite union of F-classes.

The goal of these notes is to provide a succinct introduction to the primary structural dichotomy theorems of descriptive set theory. The only prerequisites are a rudimentary knowledge of point-set topology and set theory. Working in the base theory ZF + DC, we first discuss trees, the corresponding representations of closed, Borel, and Souslin sets, and Baire category. We then consider consequences of the open dihypergraph dichotomy and variants of the 𝔾₀ dichotomy. While primarily focused upon Borel structures, we also note that minimal modifications of our arguments can be combined with well-known structural consequences of determinacy (which we take as a black box) to yield generalizations into the projective hierarchy and beyond.

We establish the existence of treeable countable Borel equivalence relations with assorted counterintuitive properties.

We characterize the existence of invariant finite and σ-finite measures in the descriptive set-theoretic milieu.

Working essentially from scratch, we introduce the primary measure-theoretic notions relevant to the study of countable Borel equivalence relations.

We provide a succinct introduction to the structures underlying the main results of classical descriptive set theory. In the first half, we discuss trees, the corresponding representations of closed sets, Borel sets, analytic spaces, injectively analytic spaces, and Polish spaces, as well as Baire category. In the second half, we establish various relatives of the 𝔾₀ dichotomy, which we then use to establish many of the primary dichotomy theorems of descriptive set theory.

We use edge slidings and saturated disjoint Borel families to give a streamlined proof of Hjorth's theorem on cost attained: If a countable p.m.p. ergodic equivalence relation E is treeable and has cost n ∈ ℕ ⋃ {∞} then it is induced by an a.e. free p.m.p. action of the free group on n generators. More importantly, our techniques give a significant strengthening of this theorem: the action can be arranged so that each of the n generators alone acts ergodically. The existence of an ergodic action for the first generator immediately follows from a powerful theorem of Tucker–Drob, whose proof however uses a recent substantial result in probability theory as a black box. We give a constructive and purely descriptive set theoretic proof of a weaker version of Tucker–Drob's theorem, which is enough for many of its applications, including our strengthening of Hjorth's theorem. Our proof uses new tools, such as asymptotic means on graphs, packed disjoint Borel families, and a cost threshold for finitizing the connected components of nonhyperfinite graphs.

We investigate the existence of non-trivial bases for actions of locally-compact Polish groups satisfying a broad array of recurrence properties.

We give a streamlined version of Törnquist's proof of Mathias's theorem that there are no infinite maximal analytic families of pairwise almost disjoint subsets of ℕ.

Suppose that X is a Hausdorff space, ℐ is an ideal on X, and (A_i)_i∈ω is a sequence of analytic subsets of X. We investigate the circumstances under which there exists I ∈ [ω]^ω with ⋂_i∈I A_i ∉ ℐ. We focus on Laczkovich-style characterizations and ideals associated with descriptive set-theoretic dichotomies.

We discuss some of the motivation behind work described in lectures given at the Universities of Paris 6 and 7 in July 2009.

We give a classical proof of the Kechris–Solecki–Todorcevic dichotomy theorem characterizing analytic graphs of uncountable Borel chromatic number. Using this, we give a classical proof of a generalization of Silver's theorem characterizing characterizing co-analytic equivalence relations which admit perfect sets of inequivalent elements.

We give a classical proof of a generalization of the Kechris–Solecki–Todorcevic dichotomy theorem characterizing analytic graphs of uncountable Borel chromatic number. Using this, we give a classical proof of a generalization of Hjorths theorem characterizing smooth treeable equivalence relations.

We give a classical proof of a generalization of the Kechris–Solecki–Todorcevic dichotomy theorem characterizing analytic graphs of uncountable Borel chromatic number. Using this, we give a classical proof of the Harrington–Kechris–Louveau theorem characterizing non-smooth Borel equivalence relations.

We give a classical proof of a generalization of Kechris–Solecki–Todorcevic dichotomy theorem characterizing analytic graphs of uncountable Borel chromatic number. Using this, we give a classical proof of a result of Kanovei-Louveau which simultaneously generalizes results of Harrington–Kechris–Louveau and Harrington–Marker–Shelah.

We show that if ℬ is a basis for the class of analytic directed graphs on Polish spaces which are of Borel chromatic number at least three, then the partial order (ℝ^<ℕ, ⊇) embeds into (ℬ, ≤_B).

We study the Borel structure of quotient spaces of the form X/E, where X is a Polish space and E is a countable Borel equivalence relation on X. Our main result is the classification of finite Borel equivalence relations on the non-smooth hyperfinite quotient space 2^ℕ/𝔼₀. In particular, we see that for each natural number n ∈ ℕ, there are only finitely many Borel equivalence relations on 2^ℕ/𝔼₀ whose classes are all of cardinality n, up to Borel isomorphism. We achieve our main result by classifying Borel cocycles from hyperfinite equivalence relations into finite groups, up to Borel reducibility. This, in turn, depends on a parameterized family of embedding theorems in the style of Glimm–Effros and Dougherty–Jackson–Kechris.

We examine the circumstances under which certain analytic equivalence relations on Polish spaces have definable transversals.

We show that the axiom of dependent choice holds if and only if every Boolean algebra admits a complete embedding into the regular open algebra of a Baire space.

We consider the problem of characterizing the circumstances under which a Borel action of a countable semigroup on a Polish space admits an invariant probability measure, and we prove that aperiodic Borel actions of countable semigroups generically lack invariant probability measures.

We study the circumstances under which an aperiodic countable Borel equivalence relation is generated by a Borel action of a free product of countable groups which is faithful on every equivalence class.

At the request of Medynets, we give a measure-theoretic characterization of the circumstances under which Borel subsets A, B of a Polish space X can be mapped to one another via an element of the full group of a countable Borel equivalence relation on X.

At the request of Tsankov, we give a somewhat different proof of Medynets's result that topological full groups associated with countable groups of homeomorphisms of zero-dimensional Polish spaces are uniformly dense in their measure-theoretic counterparts.

At the request of Kechris, we prove a technical lemma involved with weak reducibility.

At the request of Adams (via Kechris), we prove a technical lemma involved with reducibility.

We prove a dichotomy theorem for oriented graphs induced by certain families of commuting partial injections.

We generalize the marker lemma from aperiodic countable Borel equivalence relations to transitive Borel binary relations with countably infinite vertical sections.

At the request of Andrés Caicedo, we describe how ideas from the study of Borel equivalence relations can be used to establish the consistency of the failure of the (weak) dual Schröder–Bernstein theorem from Con(ZF).