University of Notre Dame         Department of Mathematics

Decision Problems in Algebra

Course Information

Instructor
Joseph Flenner (jflenner@nd.edu)
Time & Place
MWF 11:45am-12:35pm, 229 Hayes-Healy Center
Registration
MATH 80520, Section 01
Useful
References

Notes

As the semester progresses (and beyond) I intend to post electronic versions of lecture notes here. These should be expected to lag behind the actual lectures as I transcribe handwritten notes. Since they may conceivably be reused at some point any alerts about typos or other suggestions for improvements will be immoderately appreciated.

The document.

Update history:

  1. 2/4: Chapter 1 (covering lectures through 1/21) posted.
  2. 2/17: New material covering lectures through 1/28.
  3. 3/4: New stuff covering lectures roughly through 2/9 but excluding the end of the proof of Robinson's theorem on defining Z in Q, which I am temporarily setting aside.
  4. 8/2: After a long hiatus, discussions of recursive functions and the Pell equation have been added to finish up Section 3.1.
  5. 9/1: Section 3.2 is now complete.

Course Description

Abstract:
In this course I aim to cover some of the main questions about decidability in algebra and number theory. The decision problem refers to the question of whether a certain algebraic structure or theory admits an algorithm determining truth or falsity of (first-order) statements about them.
Most (but not all) of the attention will go to negative results. One of the most famous examples is the undecidability of Hilbert's Tenth Problem. Hilbert had asked for a procedure to determine whether a polynomial equation with integer coefficients has an integer solution. We will show that there can be no such procedure. There are some rather surprising consequences to this, for example the existence of a polynomial whose image in N (as the variables range over N) is precisely the prime numbers. We will also consider Hilbert's Tenth Problem in several other rings. One of the main open questions in the field is Hilbert's Tenth Problem for the rationals.

A rough outline of the course:

  1. Undecidability of the rational numbers
  2. Hilbert's Tenth Problem for the integers
  3. Hilbert's Tenth Problem in other rings
  4. Decidable theories
  5. Other topics as time permits

Prerequisites:
I expect to be able to keep the prerequisites for this course very modest. In particular, while I will assume some knowledge of mathematical logic, nothing particularly difficult from logic will be needed, so that anyone lacking this background should be able to get up to speed easily. Number theoretic results will either be proved as needed, or clearly stated as a black box.

This feedback form is part of my general teaching webpage template, so feel free to torment me night and day with cryptic anonymous messages.