Phil 641

Mathematical Logic

Time: Monday/Wednesday, 3:00-4:15 pm

YMCA 401

Instructor: Kenny Easwaran

YMCA 314

Office Hours:

There are three main skills that I want to develop through this class. The two most important ones are the skills of being able to write up a mathematical argument, and being able to present a mathematical argument verbally. To that end, students will be asked to write up one mathematical proof each week, and to present proofs in front of class. These will be low-pressure presentations, with audience members being encouraged to ask questions, and to help out, as students work through the material together. There will be no other graded assignments, though I will give a few quizzes to help figure out what material we should spend more time reviewing. Because of the importance of in-class presentations, students should let me know in advance if they expect to miss class, and should meet with me or another student to make sure they understand the work that happened in their absence.

The third main skill I want to develop in this class is an understanding of the core ideas of mathematical logic, and particularly the theorems of Cantor, Tarski, and Gödel. These results form the foundation of the theory of computation, and are important to much 20th century work in the philosophy of language, mind, and mathematics, among other areas. Importantly, these results help us to understand how abstract formal reasoning works at all when it does, and also help us understand what sorts of things that abstract formal reasoning cannot do. Most students won't be able to recall the details of the proofs of these results years from now, but having worked through the details at least once will give you a good basis for revisiting them (or other mathematical results) when they might become relevant in your future careers.

"An Aggie does not lie, cheat or steal, or tolerate those who do."

The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, in Cain Hall, Room B118, or call 845-1637. For additional information visit


This course will be taught from Boolos, Burgess, and Jeffrey, Computability and Logic

The readings and topics we will cover are (in order) the following:

Chapter 1 - enumerability

Chapter 2 - uncountability

Chapter 9 - syntax of first-order logic

Chapter 10 - semantics of first-order logic

Handout on deduction

Chapter 6 - primitive recursive functions

Chapter 7 - recursive functions and relations

Chapter 15 - computability and logic

Chapter 16 - representation of recursive functions in logic

Chapter 17 - the first incompleteness theorem

If you want a second source on any of this material, ask me for other notes.


The class meets on Monday/Wednesday, from 3:00-4:15 pm, in YMCA 401.

I will be out of town the weeks of March 20-23 and April 3-7 - we might re-schedule the two missed days each week, or arrange for an alternate instructor, or take the time for a review of previously covered material.

Spring break is the week of March 13-17.

There will be no final exam.


due 1/30, Exercise 1.2

due 2/6, Exercise 1.1