## ANNOUNCEMENTS

- Beginning of Instruction for the Spring term is Monday, March 28, 2016.
- This page was last updated: .

## COURSE DESCRIPTION

The material covered in this term will include an introduction to mathematical logic, including propositional and predicate (or first-order) calculus, computability theory, and computational complexity. We will discuss the syntax and semantics of formal languages, formal proofs, the Gödel Completeness and Incompleteness Theorems, undecidability and intractability, and the P=NP problem.

## INSTRUCTORS

Martino Lupini

HARRY BATEMAN INSTRUCTOR IN MATHEMATICS

260 Sloan

626-395-4340

lupini@caltech.edu

## OFFICE HOURS

Martino Lupini: Thursdays at 5pm (260 Sloan) or any other time by appointment (just send me an email to lupini@caltech.edu)

Jim Tao: Mondays at 10pm (307 Kellogg)

## TEXTBOOKS

There will be no official textbook. The lectures will follow notes that will be posted on this website.

Interested students can consult the following books:

Enderton, A mathematical introduction to logic. Second Edition (2001)

Shoenfield, Mathematical logic. Second Edition (2001)

Manin, A course in mathematical logic for mathematicians. Second Edition (2010)

The following is a book containing a wealth of examples of proofs by induction taken from a variety of mathematical subjects, and aimed at undergraduate students:

David Gunderson, Handbook of Mathematical Induction, CRC Press, 2011

## LECTURE NOTES

Date | Description |
---|---|

Tuesday, March 29 | Lecture 1 |

Thursday, March 31 | Lecture 2 |

Tuesday, April 5 | Lecture 3 |

Thursday, April 7 | Lecture 4 |

Tuesday, April 12 | Lecture 5 (source) |

Thursday, April 14 | Lecture 6 (source) |

Tuesday, April 19 | Lecture 7 (source) |

Thursday, April 21 | Lecture 8 (source) |

Tuesday, April 26 | Lecture 9 (source) |

Thursday, April 28 | Lecture 10 (source) |

Tuesday, May 3 | Lecture 11 |

Thursday, May 5 | Lecture 12 (source) |

Tuesday, May 10 | Lecture 13 (source) |

Thursday May 12 | Lecture 14 (source) |

Tuesday, May 17 Thursday, May 19 |
Lecture 15 and 16 |

Tuesday, May 24 Thursday, May 26 |
Lecture 17 and 18 |

## PRACTICE PROBLEMS

Lecture number | Description |
---|---|

Lecture 7 and 8 | Practice set 1 |

Lecture 8 | Practice set 2 |

Lecture 9 | Practice set 3 |

Lecture 10 | Practice set 4 |

Lecture 12 | Practice set 5 |

Lecture 13 and 14 | Practice set 6 |

Lecture 15 and 16 | Practice set 7 |

Lecture 17 and 18 | Practice set 8 |

## HOMEWORK

Due Date | Homework | Solutions |
---|---|---|

Tuesday, April 12 | Homework 1 | |

Tuesday, April 19 | Homework 2 | |

Tuesday, April 26 | Homework 3 | |

Tuesday, May 10 | Homework 4 | |

Tuesday, May 24 | Homework 5 | |

Tuesday, May 31 | Homework 6 |

## EXAMS

There will be no final exams. The grade will be based on 6 written assignments.