Mathematics 5165: Mathematical Logic
Fall 2003
- Lecturer :
Wayne Richter
- Office :
235 Vincent Hall
- Phone : 625-1858
- E-mail : richter@math.umn.edu
- Web Page: http://www.math.umn.edu/~richter
- Office hours: 1:30-2:15 on Monday and Wednesday
If you want to make an appointment
for some other time, see me in class
or leave me a phone message (or send e-mail the day before).
You may also ask questions by
\
e-mail at any time.
Required Texts
- Enderton,
A Mathematical Introduction to Logic, 2nd Edition
Later in the semester we will use
- Course notes by Wayne Richter. These are available at
the University bookstore in Coffman.
If you have a Macintosh computer or easy access to one, an
excellent inroduction with software to Part II (see below) is:
- Turing's World 3.0. An introduction to
Computability Theory, by Jon Barwise & John Etchemendy
The Enderton book is available in the University bookstore.
.
Math 5165 and Math 5166 (taught in Spring 2004) constitute a year
course in mathematical logic. In Fall Semester we develop
first-order logic
through the Goedel
Completeness Theorem. This is followed by a study of computability
theory, which is important in understanding questions of incompleteness
and undecidability. The study of computability theory will spill over
into Math 5166. The remainder of Spring Semester will develop
results of Goedel and Church on incompleteness and
undecidability. Since Math 5166 is a
direct continuation of Math 5165,
it is not recommended
that one
take Math 5166 without first taking Math 5165.
Brief course description for Math 5165 and Math 5166:
Part I: Sentential Logic and First-Order Logic
- Sentential Logic
- First-order languages
- Truth and Models
- Completeness of first-order logic
Part II: Algorithms and Computability (continued in Math
5166)
- informal notion of algorithm and computability
- Turing machines
- Church's Thesis
- primitive recursive functions
- partial recursive functions
- recursive sets
- recursively enumerable sets
- Kleene Normal Form
Part III (Math 5166):
- Incompleteness and Undecidability
Grading for Fall Quarter (approximate):
- Homework 30%
- Three Hour Exams 15% each
- Final Exam 25%
Department of Mathematics .
-
Approximate class schedule, homework list, and exciting,
late breaking news
- Logic Notes
- For information about the P versus NP problem (and a possible million
dollar reward!) go to
Millenium Prize
Problems and then click on "P versus NP".
-
Some old exams and related files.