Graduate Student Seminar, 4:30 pm October 11, 2004; HH127


Wesley Calvert




It is an observation common to anyone who has done a bit of mathematics that some things are harder than others. There are several ways in which we can turn this statement into a provable mathematical fact, and several ways in which we can classify things according to how hard they are. These classifications range from the simplest problems of finite combinatorics (and some problems of finite combinatorics are not simple at all) to the most abstract points of analysis and set theory. Most of us are interested in things in a very comfortable middle range.

This talk will begin with the simplest set of all, the empty set. We will continue through polynomial-time and NP problems, and the halting set, and continue straight into the Borel hierarchy and beyond. Near the end, we will get to sets so complicated that the axiom of choice is necessary to prove their existence (like a non-measurable set), and to some where even that is not enough.

Concrete examples from algebra, analysis, and combinatorics will be given along the way.

To volunteer to give a talk, or for any other questions regarding this schedule, contact Sara Miller