MAGIC110: Complexity of Classification Problems

Course details

A specialist MAGIC course

Semester

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

Hours

Live lecture hours
10
Recorded lecture hours
0
Total advised study hours
40

Timetable

Fridays
13:05 - 13:55

Course forum

Visit the MAGIC110 forum

Description

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.

Prerequisites

Basic topology (open and closed sets).

Syllabus

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.

Lecturer

  • Dr Andrew Brooke-Taylor

    Dr Andrew Brooke-Taylor

    University
    University of Leeds

Bibliography

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.

Assessment

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.

Files

Only consortium members have access to these files.

Please log in to view course materials.

Lectures

Please log in to view lecture recordings.