Math 225B - Metamathematics (Part II)

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

Introduction

First order arithmetic

Language and theory of first order arithmetic

The standard model

Non-standard models

Is Th(N) hard ?

Formalizations

The question of axiomatizability

The systems PA^- and PA

Completeness and computability

II.

Computability Theory

Primitive recursive functions

Definition, examples

mu-operator

Partial and general recursive functions

Turing machines

Definition, examples

The Church-Turing Thesis

Equivalence of notions of computability

Aspects of the Church-Turing Thesis

Basic results on computable functions

Goedel numbers

Padding Lemma

Kleene Normal Form

Enumeration and S-m-n-Theorem

Computably enumerable sets and unsolvable problems

Halting problem and its variants

Many-one reducibility

Index sets and Rice's Theorem

Applications: new uncomputable sets

* Computable isomorphisms

1-1 reducibility

Myhill Isomorphism Theorem

Completeness

* Creative and productive sets

* Myhill's Theorem on creative sets.

The Recursion Theorem

10.

Relative computability and Turing reducibility

Oracle Turing machines

Turing degrees and the jump operator

11.

The Limit and Modulus Lemma

12.

Representation of arithmetical sets

C.e. sets and Sigma_1 definable sets

* Diophantine sets

13.

The arithmetical hierarchy

Post's Theorem

Complete sets

14.

* High and low sets

Domination properties of functions

III.

Metamathematics of Arithmetic

Theories and Decidability

Undecidability of arithmetic

Representability in theories

Arithmetization of syntax and PA^-

Goedel's First Incompleteness Theorem

Theorems of Tarski and Church

Self-Reference and the Second Incompleteness Theorem

Models of PA

Complete Extensions of PA

Recursive inseperability

* Effectively closed sets and the low basis theorem

The Parris-Harrington Theorem

Ramsey properties

Indiscernibles

Interpretability

Transfer of undecidability results

10.

Examples of undecidable theories

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

Exams

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