A basic result in combinatorics, known as König's Lemma, says that every infinite finitely-branching tree has an infinite branch. How complicated are these branches relative to the complexity of the tree? Computability theory has tools for making such questions precise, and methods relevant to the answers. In particular, it provides various hierarchies by which we can measure the complexity of trees, branches, and other objects, and techniques for carrying out such measurements. After introducing the relevant background from computability theory, we will discuss the above problem and others arising from combinatorics (in Ramsey theory) and algebra (in ideal theory). A successful analysis of a mathematical theorem using these techniques gives information about how complicated the sets involved in any proof must be. Furthermore, this study unearths some interesting connections between various theorems across different areas of mathematics.
Joseph Mileti was a double major in Mathematical Sciences and Computer Science at CMU, where he finished his undergraduate work with honors in 1999. He received the Ph.D. in Mathematics from Urbana in 2004 and shared the Sacks Prize with Nathan Segerlind (another CMU alumnus) for the two best doctoral dissertations in mathematical logic that year. Currently, Mileti is an L.E. Dickson Instructor of Mathematics at Chicago.
Ernest Schimmerling
Department of Mathematical Sciences
Carnegie Mellon University
E-mail: eschimme-at-andrew