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? The tools and methods of computability theory allow us to discuss and answer such a question in a meaningful mathematical way. For instance, we may ask whether every infinite computable finitely-branching tree has an infinite computable branch. If not, we may seek to classify just how noncomputable we must look before we can see an infinite branch. 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). This study unearths some interesting connections between various theorems of mathematics and provides some insight into what techniques must be used in their proofs.
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 Mathemtics from Urbana-Champaign 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, he is an L.E. Dickson Instructor of Mathematics at the University of Chicago.
Department of Mathematical Sciences
Carnegie Mellon University