You are here

Invariant Descriptive Set Theory

Su Gao
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
Pure and Applied Mathematics 293
[Reviewed by
Leon Harkleroad
, on

Blend together some real analysis and point-set topology. Add a handful of group theory. Mix well with model theory and computability theory from mathematical logic. Spice with a dash of graph theory and other flavors. The field known as invariant descriptive set theory contains many more ingredients — both in its tools and in its objects of study — than its name suggests, and Gao’s book provides a generous helping.

This area focuses on equivalence relations that arise in a variety of mathematical contexts. Typical examples include:

  • for real numbers x ≈ y iff x – y is rational;
  • for subsets of the free group on two generators, A≈ B iff for some g, A = gB;
  • for countable locally finite trees, T1≈ T2 iff they are graph isomorphic.

Given two equivalence relations ≈ and ≈' that occur naturally in disparate mathematical contexts, often one can “nicely” (i.e., uniformly, via a Borel function) convert questions about ≈ into questions that ≈' can answer. Invariant descriptive set theory examines and compares equivalence relations from this viewpoint, thereby in Gao’s words, “making new connections between mathematical fields.”

This book, which grew out of lecture notes from a short course that the author gave as a visitor at the University of Notre Dame in 2005, was written to serve as a graduate text. Accordingly, Gao supplies necessary background material, detailed proofs, and plenty of exercises. In 2000, Greg Hjorth had also taught a short course in this area while a visitor at Notre Dame. Hjorth’s lecture notes evolved into a 43-page tutorial “Countable Models and the Theory of Borel Equivalence Relations,” one quarter of the compilation The Notre Dame Lectures [1].

Working on a larger canvas, Gao gets to develop the subject in more breadth and depth, as well as in a more leisurely fashion. On the other hand, Hjorth’s relative compactness sometimes helps make the forest more easily visible for the trees. Together, the two presentations make nice companion pieces, each in its own way providing a helpful and readable introduction to a young and developing area of research.


[1] The Notre Dame Lectures, ed. Peter Cholak. Lecture Notes in Logic 18, Association for Symbolic Logic/A K Peters, 2005.

Leon Harkleroad did his graduate work in computability theory at Notre Dame. He is glad that mathematical logic is flourishing there even more energetically than during his student days, which is more than can be said for football.


Polish Group Actions

Polish spaces
The universal Urysohn space
Borel sets and Borel functions
Standard Borel spaces
The effective hierarchy
Analytic sets and Σ 1/1 sets
Coanalytic sets and Π 1/1 sets
The Gandy–Harrington topology
Polish Groups 
Metrics on topological groups
Polish groups
Continuity of homomorphisms
The permutation group S 
Universal Polish groups
The Graev metric groups
Polish Group Actions
Polish G-spaces
The Vaught transforms
Borel G-spaces
Orbit equivalence relations
Extensions of Polish group actions
The logic actions
Finer Polish Topologies
Strong Choquet spaces
Change of topology
Finer topologies on Polish G-spaces
Topological realization of Borel G-spaces
Theory of Equivalence Relations 
Borel Reducibility 
Borel reductions
Faithful Borel reductions
Perfect set theorems for equivalence relations
Smooth equivalence relations
The Glimm–Effros Dichotomy
The equivalence relation E0 
Orbit equivalence relations embedding E0 
The Harrington–Kechris–Louveau theorem
Consequences of the Glimm–Effros dichotomy
Actions of cli Polish groups
Countable Borel Equivalence Relations
Generalities of countable Borel equivalence relations
Hyperfinite equivalence relations
Universal countable Borel equivalence relations
Amenable groups and amenable equivalence relations
Actions of locally compact Polish groups
Borel Equivalence Relations 
Hypersmooth equivalence relations
Borel orbit equivalence relations
A jump operator for Borel equivalence relations
Examples of Fσ equivalence relations
Examples of Π 0/3 equivalence relations
Analytic Equivalence Relations
The Burgess trichotomy theorem
Definable reductions among analytic equivalence relations
Actions of standard Borel groups
Wild Polish groups
The topological Vaught conjecture
Turbulent Actions of Polish Groups 
Homomorphisms and generic ergodicity
Local orbits of Polish group actions
Turbulent and generically turbulent actions
The Hjorth turbulence theorem
Examples of turbulence
Orbit equivalence relations and E1 
Countable Model Theory 
Polish Topologies of Infinitary Logic
A review of first-order logic
Model theory of infinitary logic
Invariant Borel classes of countable models
Polish topologies generated by countable fragments
Atomic models and Gδ-orbits
The Scott Analysis
Elements of the Scott analysis
Borel approximations of isomorphism relations
The Scott rank and computable ordinals
A topological variation of the Scott analysis
Sharp analysis of S-orbits
Natural Classes of Countable Models
Countable graphs
Countable trees
Countable linear orderings
Countable groups
Applications to Classification Problems
Classification by Example: Polish Metric Spaces 
Standard Borel structures on hyperspaces
Classification versus nonclassification
Measurement of complexity
Classification notions
Summary of Benchmark Equivalence Relations
Classification problems up to essential countability
A roadmap of Borel equivalence relations
Orbit equivalence relations
General Σ 1/1 equivalence relations
Beyond analyticity
Appendix: Proofs about the Gandy–Harrington Topology
The Gandy basis theorem
The Gandy–Harrington topology on Xlow