Mathematics 5165 -5166

Mathematics 5165-5166: Mathematical Logic

Fall 2009- Spring 2010

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. 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
Wayne Richter, Mathematical Logic: An Introduction to Algorithms and Computability (hereafter referred to as A&C )

A&C is available at Alpha Print in Dinkytown, and Enderton is available 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, up to and including (perhaps) 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. A student who takes Math 5165 but not Math 5166 will miss material on algorithms, effective computability, recursive functions, and the Goedel Incompleteness Theorems.
Fall Semester will cover Parts I and II and part of 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

Grading (approximate) for Fall Semester:

Homework 40%
Two Hour Exams 30%
Final Exam 30%

Final Exam: Wednesday, December 23, 1:30-3: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

Solutions to some homework problems

Some old exams and related files.
Old Second Midterm Exam

Department of Mathematics .
Updated September 5, 2009