Many Faces of Transfinite Hierarchies

Strictly speaking, an algorithm is a procedure which can be carried out on a computer, but computability theory also includes more expansive notions of algorithm. A generalized algorithm runs for transfinitely many steps, and even a single step is too hard for an ordinary computer, but this kind of algorithmic thinking gives a useful perspective on mathematics. This project will use the algorithmic perspective of computability theory to analyze various hierarchies from classical analysis, topological dynamics, and descriptive set theory. Sometimes a hierarchy-derived tool, such as the measurability of a Borel set, is less powerful than a full hierarchy analysis, but still strong enough for many purposes. The research will explore this distinction, among other questions. The project will also support the training of graduate students.

Theorems about Borel sets are sometimes proved by recursing along the structure of the Borel sets, but more often they are proved via measure or category. When the usual measure and category approaches do not pan out, reverse mathematics provides one framework for formalizing the question of whether any measure or category approach could succeed. This framework will be applied to analyze various theorems about Borel sets, in particular theorems from descriptive combinatorics. Second, the PI will address a number of questions about computability-theoretic properties of hierarchies in classical analysis, such as the Bourgain rank or the hierarchy of Denjoy integrable functions. Finally, shifts of finite type (SFTs) are certain topological dynamical systems which are simply described but exhibit complex behavior, because their dynamics can simulate Turing computations. It is not well understood which properties of the resulting dynamical system can be controlled by these computations. The project aims to develop usable meta-theorems describing classes of algorithms that can be implemented in SFTs.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.