# Mathematics colloquium and PAL colloquium

### Thursday, October 27, 2005

### Baker Hall A53

### 4:30 - 5:30 with refreshments at 4 in the lobby

# Joseph Mileti, Department of Mathematics, University of Chicago

# "Using computability theory to calibrate mathematical complexity"

### Abstract

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.

### Biography

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.

### Contact

Ernest Schimmerling

Department of Mathematical Sciences

Carnegie Mellon University

E-mail: eschimme-at-andrew