Math 558: Foundations of Mathematics

Fall 2009, Tue-Thu 9:45–11:00 AM, 315 McAllister

Stephen G. Simpson, 305 McAllister, 863-0775, simpson@math.psu.edu

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

       http://www.math.psu.edu/simpson/courses/math558/.

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

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ödel numbers, undefinability of arithmetical truth.

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.