Math 558: Foundations of Mathematics Spring 2004, MWF 10:10-11:00 AM, 107 Sackett, Schedule 271918 Stephen G. Simpson, 333 McAllister, 863-0775, t20@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.personal.psu.edu/t20/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"odel 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.