Mathematics 5165-5166: Mathematical Logic
Fall 2007- Spring 2008
- 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: Monday and Wednesday 1:30-2:15,
and by appointment. I am also usually available after class for a few minuttes. 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.
Prerequisites: One of the following:
Math 3283W, or
Math 2283, or the Honors Math calculus sequence, or a 5xxx level
Philosophy course in Logic, or a theoretical computer science course
dealing with finite automata, Turing Machines, etc., or my
permission.
Experience has shown that students without the prerequisites have a tough time.
This is not a course in logical reasoning.
It is a rather theoretical mathematics course with lots of proofs, that uses mathematics to investigate the structure of various mathematical systems. In particular, it is concerned in part with understanding the strength and limitations of mathematical systems, and the nature of computability.
Required Texts
- Enderton,
A Mathematical Introduction to Logic
- Wayne Richter, Mathematical Logic: An Introduction to
Algorithms and Computability (hereafter referred to as
A&C )
A&C will soon be available, and Enderton is available, both at the University Bookstore.
Math 5165 is the first semester of a year course, Math 5165-5166, in
Mathematical Logic.
Math 5165 is devoted to sentential logic, and first-order logic
leading up to but not including the Goedel Completeness Theorem. Since Math 5166 is a
direct continuation of Math 5165,
it is not recommended
that one
take Math 5166 without first taking Math 5165.
The material covered in Fall Semester provides the groundwork for most
of the exciting results, which occur in Spring Semester. A student who takes
Math 5165 but not Math 5166 will miss material on the Goedel
Completeness Theorem and applications, algorithms, effective
computability, recursive functions, and the
Goedel Incompleteness Theorems.
Fall Semester will cover approximately Parts I-II and the first half
of Part III below.
Brief course description for Math 5165-5166:
Part I: Introduction to Set Theory
- finite and infinite sets
- enumerable, countable, and uncountable sets
- Cantor's Theorem on the size of sets
Part II: Sentential Logic
Part III: First-order Logic
- First-order languages
- Truth and Models
- Goedel Completeness Theorem
- consequences of the Goedel Completeness Theorem
Part IV : Algorithms and Computability
- 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 V: Goedel Incompleteness Theorems
Part VI: Second-Order Logic and Game Theory (as time permits)
Grading (approximate):
- Homework 40%
- Two Hour Exams 30%
- Final Exam 30%
Final Exam: Monday, December 17, 10:30-12:30.
-
Approximate class schedule, homework list, and exciting,
late breaking news.
-
Finite and Infinite Sets
-
Notes on Sentential Logic
-
Notes on First Order Logic
-
Notes on the Completeness Theorem
-
Old First Midterm Exam.
Old Second Midterm Exam
Final Exam 2005
Some Homework Problem Solutions
Test I
Test II
Department of Mathematics .
Updated September 19, 2007