Time: Tuesday/Thursday, 11:10-12:25
Instructor: Kenny Easwaran
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.
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 http://disability.tamu.edu.
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 Tuesday/Thursday from 11:10 to 12:25, in YMCA 401.
I will be out of town the week of February 16-20 - we might re-schedule the two missed days, or arrange for an alternate instructor, or take the time for a review of previously covered material.
Spring break is the week of March 16-20.
Tuesday, April 21 is Muster - I don't know if this is expected to affect class schedule.
Tuesday, May 5 is re-defined as a Friday for the academic calendar - we may use this day as a make-up time, or have it off.
There will be no final exam.
1/27 - Exercise 1.1
2/3 - Exercise 1.3
2/10 - Exercise 2.8
2/24 - Exercise 2.7
3/10 - Exercise 9.2
3/24 - Exercise 9.5