Skip to main content
2 of 2
Fix grammar as requested by Peter Mortensen
Siddharth Bhat
  • 1.2k
  • 3
  • 11
  • 23

Descriptive set theory for computer scientists?

It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the Polynomial hierarchy for one, and the relationship between topology and computability.

I would like to understand things such as:

It would be fantastic if these could be answered from the perspective of computability. For example, I know that the Cantor set has good computability properties, and I (possibly very incorrect) believe that this is related to descriptive set theory.

I'd greatly appreciate references to lecture notes, talks, video lectures, textbooks. Pretty much anything where I can study descriptive set theory with a computational bent would be great.

Siddharth Bhat
  • 1.2k
  • 3
  • 11
  • 23