Math 225B - Metamathematics (Part II)

Spring 2009

Overview

Lectures: TuTh 2-330pm, Room 81 Evans
Instructor: Jan Reimann
Office: 705 Evans Hall
Office hours: Tu 4-5, We 10-12 and by appointment
Email:
Personal Website: http://math.berkeley.edu/~reimann/

Course webpage: This site is mainly for documetary purposes. The course material (homework, sample exams, etc.) will be posted on bSpace. The course site also has a chat room. I encourage you to make use of it. (I will check in regularly myself.) Go to http://bspace.berkeley.edu and log on with your Calnet ID. Then select the tab "MATH 225B Sp09".

Course Outline


I. Introduction
1. First order arithmetic
a. Language and theory of first order arithmetic
b. The standard model
c. Non-standard models
d. Is Th(N) hard ?
2. Formalizations
a. The question of axiomatizability
b. The systems PA^- and PA
c. Completeness and computability
II. Computability Theory
1. Primitive recursive functions
a. Definition, examples
b. mu-operator
c. Partial and general recursive functions
2. Turing machines
a. Definition, examples
3. The Church-Turing Thesis
a. Equivalence of notions of computability
b. Aspects of the Church-Turing Thesis
4. Basic results on computable functions
a. Goedel numbers
b. Padding Lemma
c. Kleene Normal Form
d. Enumeration and S-m-n-Theorem
5. Computably enumerable sets and unsolvable problems
a. Halting problem and its variants
6. Many-one reducibility
a. Index sets and Rice's Theorem
b. Applications: new uncomputable sets
7. * Computable isomorphisms
a. 1-1 reducibility
b. Myhill Isomorphism Theorem
8. Completeness
a. * Creative and productive sets
b. * Myhill's Theorem on creative sets.
9. The Recursion Theorem
10. Relative computability and Turing reducibility
a. Oracle Turing machines
b. Turing degrees and the jump operator
11. The Limit and Modulus Lemma
12. Representation of arithmetical sets
a. C.e. sets and Sigma_1 definable sets
b. * Diophantine sets
13. The arithmetical hierarchy
a. Post's Theorem
b. Complete sets
14. * High and low sets
a. Domination properties of functions
III. Metamathematics of Arithmetic
1. Theories and Decidability
a. Undecidability of arithmetic
2. Representability in theories
a. Arithmetization of syntax and PA^-
3. Goedel's First Incompleteness Theorem
4. Theorems of Tarski and Church
5. Self-Reference and the Second Incompleteness Theorem
6. Models of PA
7. Complete Extensions of PA
a. Recursive inseperability
b. * Effectively closed sets and the low basis theorem
8. The Parris-Harrington Theorem
a. Ramsey properties
b. Indiscernibles
9. Interpretability
a. Transfer of undecidability results
10. Examples of undecidable theories
a. * The word problem for groups

Text

We will not use a textbook, but instead produce our own notes. One of the requirements for completing the course is that you produce detailed notes of at least two class sessions. These notes should be in LaTeX (or something that can be converted to it), and are due the week after the corresponding lecture.

For each lecture, I will point to several resources which you can use in producing your notes. You can also use these references to read ahead if you want. I created a Google calendar for the course where I will announce the material covered in the upcoming lectures.

Most of the material can be found in the following texts:

These texts have been placed on one-day reserve at the math library.

Exams

There will be a take home final in the last week of classes.

Homework

Homework will be assigned on Thursday and will be due on the following Thursday in class. Homework will be graded and the two lowest scores will be dropped. Late homework will not be accepted. There will be no exception to this rule. Of course it may happen that you cannot turn in homework because you were ill or for some other valid reason. This is why the two lowest scores will be dropped.

A note on academic honesty: Collaboration among students to solve homework assignments is welcome. This is a good way to learn mathematics. So is the consultation of other sources such as other textbooks. However, every student has to hand in an own set of solutions, and if you use other people's work or ideas you should indicate the source in your solutions.
(In any case, complete and correct homework receives full credit.)

Course Grade

The course grade will be based on the homework grades (60%), the take-home final (20%) and the quality of the lecture notes produced (20%).