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

#### Speaker:

Wesley Calvert
#### Title:

Hard
#### Abstract:

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