MAGIC110: Complexity of Classification Problems

Course details


Autumn 2021
Monday, October 4th to Friday, December 10th


Live lecture hours
Recorded lecture hours
Total advised study hours


13:05 - 13:55

Course forum

Visit the MAGIC110 forum


In broad brushstrokes, we can generally describe classification programmes in mathematics as follows.  You have some mathematical objects that you want to classify, up to isomorphism or some other such equivalence relation.  You also have some mathematical objects that you want to use as invariants, again possibly up to some equivalence relation.  And you want a reasonably definable map from the objects to be classified to the invariants, in such a way that the objects to be classified are equivalent if and only their images are equivalent.

It is often the case that the mathematical objects we are interested in, both those to be classified and the intended invariants, can be encoded by real numbers.  In this case the question of classifiability boils down to the existence of a "reasonably definable" map from R to R respecting the equivalence relations.  Taking "Borel" as a suitably liberal interpretation of "reasonably definable", we can sometimes prove that no such map exist, ruling out the classification.  This has been successfully used to prove that some old classification programmes, in areas such as C*-algebras and ergodic theory, were impossible tasks.

This course will introduce students to this area, developing the theory from theground up, culminating in Hjorth's notion of turbulence, which is the central tool for proving unclassifiability results.


Basic topology (open and closed sets).


Motivation: examples.  Polish spaces, Borel functions and Borel reductions.  The logic action and orbit equivalence relations.  Standard Borel spaces, Polish groups and Borel groups.  Smooth relations, E0, and the Effros Borel space.  Baire category machinery, building to proof that the Effros Borel space is a universal Borel G-space.  Borel completeness.  Generic ergodicity.  Isomorphism of rank-1 torsion free abelian groups is not smooth.  Turbulence. Examples of turbulence and unclassifiability.


  • Dr Andrew Brooke-Taylor

    Dr Andrew Brooke-Taylor

    University of Leeds


No bibliography has been specified for this course.


Attention needed

Assessment information will be available nearer the time.


Only consortium members have access to these files.

Please log in to view course materials.


Please log in to view lecture recordings.