MAGIC110: Complexity of Classification Problems

Course details

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

No bibliography has been specified for this course.

Assessment

Attention needed

Assessment information will be available nearer the time.

Files

Only consortium members have access to these files.

Please log in to view course materials.

Lectures

Please log in to view lecture recordings.