# Mathematics colloquium

### Thursday, October 27, 2005

### Baker Hall A53

### 4:30 - 5:30 with refreshments at 4

# 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?
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.

### 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 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.

### Contact

Ernest Schimmerling

Department of Mathematical Sciences

Carnegie Mellon University

E-mail: eschimme-at-andrew