Math 558: Foundations of Mathematics

Spring 2004, MWF 10:10-11:00 AM, 107 Sackett, Schedule 271918

Stephen G. Simpson, 333 McAllister, 863-0775,

This course is suitable for all mathematics graduate students.  The
textbook will consist of notes provided by the instructor, also
on-line at

1. Computability

Primitive recursive functions, the Ackermann function, computable
functions, partial recursive functions, the enumeration theorem, the
Halting Problem, examples of functions and sets which are not

2. Undecidability of the Natural Number System

Terms, formulas, sentences, arithmetical definability, Chinese
Remainder Theorem, definability of computable functions, definability
of the Halting Problem, G"odel numbers, undefinability of arithmetical

3. Decidability of the Real Number System

Effective functions, quantifier elimination (P. J. Cohen's method),
definability over the real number system, decidability of the real
number system, decidability of Euclidean geometry.

4. Introduction to Set Theory

Russell paradox, operations on sets, cardinal numbers, ordinal
numbers, transfinite recursion, the Axiom of Choice, the Well Ordering
Theorem, the Continuum Hypothesis, inaccessible cardinals.

5. Independence of the Continuum Hypothesis

The Zermelo-Fraenkel axioms, set-theoretic foundations of mathematics,
models of set theory, inner models, constructible sets, the inner
model L, the Generalized Continuum Hypothesis in L, models constructed
by forcing, a model where the Continuum Hypothesis fails.