
Math 503: Metamathematics II

General Information

Time and Place: MWF 2-2:50pm, 312 Lincoln Hall
Control Number: 22977

Instructor: Matthias Aschenbrenner

E-mail address: maschenb

math.uic.edu
Homepage: http://www.math.uic.edu/~maschenb

Office: 417 SEO
Office Phone: (312) 413-3150
Office Hours: MWF 1-2pm, or by appointment.

Prerequisites: Math 502 (Metamathematics I); some elementary number theory.

Achtung! Downloading files from this website requires software to display PDF files, such as Acrobat Reader or Ghostview.

Click here to download the class information handout.

Description

The focus of this course will be incompleteness and undecidability in mathematics. In particular, it will provide an introduction to two landmarks of 20th-century mathematical logic: Gödel's Incompleteness Theorems, and the undecidability of Hilbert's Tenth Problem. (Hilbert had asked for an algorithm to decide whether a given polynomial equation with integer coefficients has a solution in the integers. Matiyasevich, based on work of Putnam, Davis, and Robinson, proved that no such algorithm exists.) Time permitting, we will contrast this with positive results such as the decidability of Presburger arithmetic.

Course Text

For Hilbert's 10th Problem: Hilbert's 10th Problem by Yuri Matiyasevich, MIT Press, 1993.

Other texts that you might want to consult:

Mathematical Developments Arising from Hilbert Problems edited by Felix Browder, AMS, 1976.
Hilbert's Tenth Problem: Relations with Arithmetic and Algebraic Geometry edited by Jan Denef et al., AMS, 2000.
The Collected Works of Julia Robinson edited by Solomon Feferman, AMS, 1996.

A good general reference for mathematical logic is Mathematical Logic by Joseph R. Shoenfield, A K Peters, Ltd., 2000.

To get an idea about ongoing research on extensions of Hilbert's 10th Problem see Alexandra Shlapentokh's book manuscript Hilbert’s Tenth Problem: Diophantine Classes and Other Extensions to Global Fields, Cambridge University Press, to appear.

See also the Hilbert's 10th Problem web page.

Homeworks

There will be a problem set due every two weeks or so, to be handed in at the beginning of class. No late homework will be accepted.

Homework 1 (due February 13)
Homework 2 (due March 10)
Homework 3 (due April 28)

Historical Information

Click below for biographical information about some of the main actors involved the solution of Hilbert's 10th Problem:

Martin Davis
Kurt Gödel
David Hilbert
Yuri Matiyasevich
Hilary Putnam
Julia Robinson

Back to my home page. Bauarbeiten

Last modified April 19, 2006.