Metmathematics I

Math 502/Phil 596

Fall 2003

Call Number: 67590/84970 MWF 11-12 302AH
Instructor: David Marker
Office: 411 SEO
Office Hours: M 1:30-3:00, W 9:00-11:00, Th 10:30-12:00
phone: (312) 996-3069
e-mail: marker@math.uic.edu
course webpage: http://www.math.uic.edu/~marker/math502

Description

A first graduate course in mathematical logic. We will introduce the fundamental themes of mathematical logic (truth, provability, and computability), discuss their interconnections and examine the power and limits of formal methods. The main results will be Godel's Completeness and Incompleteness Theorems and Tarski's decidability results for the real and complex fields. Specific topics covered will include.

Mathematical structures
Formal proofs
The Completeness Theorem
The Compactness Theorem and elementary model theory
Introduction to computability theory
The Incompleteness Theorem
Decidability results for real closed fields and algebraically closed fields

Texts

H.-D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic Second Edition, Springer-Verlag, 1994.
N. Cutland, Computability: An introduction to recursive function theory, Cambridge University Press, 1986.
J. Shoenfield, Mathematical Logic, A.K. Peters, 2001

I will not be following any of these texts completely. The treatment of material at the begining of the course on structures, truth and formal proofs will be similar to the treatment in Ebbinghaus-Flum-Thomas. The treatment of computability will follow Cutland. Shoenfield's Mathematical Logic is the classic text in the subject. It is an excellent reference for some of the more advanced subjects we will cover and contains a wealth of interesting material.

Prerequisites

Graduate standing. No previous background in logic is assumed. As many examples will come from Algebra, Math 516 is a useful.

Grading

I will give out about 8 problem sets. You may work together on homework problems (and I encourage you to do so), but when you turn in the problem you should acknowledge that you have worked together. There will probably be a one hour final exam testing basic concepts, definitions, and statements of theorems.

Lecture Notes

Survey of Basic Set Theory
Sections 1--5: Languages and Structures, Theories, Formal Proofs, Goedel's Completeness Theorem, Basic Model Theory
Sections 6--9: Models of Computation, Universal Machines and Undecidability, Recursively Enumerable and Arithmetic Sets, Further Topics in Computability Theory
VERY PRELIMINARY VERSION Section 10 Godel's Incompleteness Theorem

Homework Assignments

Problem Set 1 Due Friday 9/12
- Solutions
Problem Set 2 Due Friday 9/26
- Solutions
Problem Set 3 Due Wednesday 10/8
- Solutions
Problem Set 4 Due Wednesday 10/22
- Solutions
Problem Set 5 Due Friday 11/7
- Selected Solutions
Problem Set 6 Due Wednesday 12/10
- Selected Solutions

Dave Marker's Home Page

Last updated 11/21/03