MAGIC110: Complexity of Classification Problems

Course details

A specialist MAGIC course


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 if 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


Follow the link for a book to take you to the relevant Google Book Search page

You may be able to preview the book there and see links to places where you can buy the book. There is also link marked 'Find this book in a library' - this sometimes works well, but not always - you will need to enter your location, but it will be saved after you do that for the first time.


The assessment for this course will be released on Monday 10th January 2022 and is due in by Sunday 23rd January 2022 at 23:59.

Assessment for all MAGIC courses is via take-home exam which will be made available at the release date (the start of the exam period).

You will need to upload a PDF file with your own attempted solutions by the due date (the end of the exam period).

If you have kept up-to-date with the course, the expectation is it should take at most 3 hours’ work to attain the pass mark, which is 50%.

Please note that you are not registered for assessment on this course.


Only consortium members have access to these files.

Please log in to view course materials.


Please log in to view lecture recordings.