Click Here for the Fall 2009 Webpage

Metmathematics I

Math 502/Phil 596

Fall 2005

Course Meeting: 10:00 MWF 302 AH
Call Number: 22685/23110
Instructor: David Marker
Office: 411 SEO
Office Hours: M,W: 11-12, F:8:30-10: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.

Mathematical structures
Formal proofs
Godel's Completeness Theorem
The Compactness Theorem and elementary model theory
Model theory of algebraically closed fields
models of computation, Church's Thesis
Universal machines and undecidability
Recursively enumerable and arithmetic sets
Further topics in computability theory

Godel's Incompleteness Theorem will be discussed in Math 503 in Spring semester. The sequence Math 502-503 leads to the logic prelim.

Texts

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

For this course I will not be closely following any text.
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 closely follow Cutland.

The bookstore told me they were having trouble with Ebbinghaus-Flum-Thomas. I have asked them to order the replacement

J. Shoenfield, Mathematical Logic, A. K. Peters, 2001

Shoenfield is a classic text in the subject covering a great deal of interesting material with wonderful problems.
Unfortunately, in some aspects it is old-fashioned and the notation can be very cumbersome. My presentation of material will not closely follow Shoenfield.

I will circulate lecture notes.

Prerequisites

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

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, possibly oral, 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--8 Computability, recursive functions, recursively enumerable and arithmetic sets

Homework Assignments

Problem Set 1 Due Friday September 9
Problem Set 2 Due Wednesday September 28
Problem Set 3 Due Wednesday October 5
Problem Set 4 Due Friday October 21
Problem Set 5 Due Wednesday November 2
Problem Set 6 Due Wednesday Novermber 16
Problem Set 7 Due Wednesday December 7

Last updated 11/22/05