BRICS · Contents · Programme · References

A Taster of Descriptive Set Theory

A BRICS Mini-Course
September 9, 14 and 16, 1999

Lectures by
Julian Bradfield, jcb@daimi.au.dk
BRICS and LFCS, Edinburgh


Course Contents

Descriptive set theory came into being around the turn of the (last!) century, as a means of analysing the ``difficulty'' of sets of real numbers, of the kind encountered in analysis. It is so called because it uses the logical description of a set as a measure of complexity.

A few decades later, when recursion theory had been invented, similar ideas were used to describe sets of integers: the stuff of computation. It turned out that this ``effective'' descriptive theory and the older classical descriptive set theory are best seen as one subject; the combination brought great advances in both.

The basic terminology of effective descriptive set theory pops up quite often in theoretical computer science: Pi11-complete, for example. The classical notions are also seen, particularly when talking about timed systems and other things involving the reals. It is therefore often useful to have a nodding acquaintance with the terms and concepts of descriptive set theory. Furthermore, there are occasions when results of descriptive set theory have been used to surprising effect in TCS problems.

However, it is also the case that descriptive set theory is a fascinating and beautiful subject, with surprising links to deep foundational issues in mathematics.

The aim of this mini-course, therefore, is three-fold: to give, at a high level and without much formal detail, an introduction to the main concepts of (mainly effective) descriptive set theory; to show some of the curious foundational links; and, if time permits, to sketch an application in computer science.

A knowledge of undergraduate recursion theory (i.e. the meaning of ``recursive function'', the relationship between Turing machines and recursive functions, etc) will be assumed, but little more. In some places it will be necessary to assume a little knowledge of ordinal and cardinal numbers. The ``crash course'' (yes, it's just one Web page) http://www.earlham.edu/ peters/writing/infapp.htm is enough for the cardinals.

Programme

Thursday September 9, 1999, 15:15-17:00 in Auditorium D4

(Liable to change according to timing, audience interaction, etc.)

What is (effective) descriptive set theory? Complexity of sets of integers: the arithmetical hierarchy. Allowing second order quantification: `effective' computation on reals/irrational, and the analytical hierarchy.

Tuesday September 14, 1999, 15:15-17:00 in Auditorium D4

In between: the hyperarithmetic hierarchy. A little about classical descriptive set theory.

Thursday September 16, 1999, 15:15-17:00 in Auditorium D4

Foundations: how set theory affects descriptive set theory. Inductive definitions and fixpoints.

References

Y. N. Moschovakis, Descriptive Set Theory, Amsterdam: North-Holland (1980).

Printed notes will be issued during the course.