## 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

Jay Williams

POSTDOCTORAL SCHOLAR IN MATHEMATICS

256 Sloan

626-395-4338

jaywill@caltech.edu

## POLICIES

There will be a weekly homework assignment due on Tuesday at 1pm. The lowest homework score will be dropped. There will be no exams for the class. On each homework there will be one starred problem on which no collaboration is allowed. For the other problems, collaboration is allowed but you should write up your own solutions. You cannot look up solutions to the problems from any source. No late submissions are allowed except for medical problems (note needed from the health center) or serious personal difficulties (note needed from the Dean's Office).

## LECTURE NOTES

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

T 3-31 | Propositional logic definitions |

Th 4-2 | Truth tables and induction on formulas |

T 4-7 | Graphs, trees, Konig's lemma, and Compactness (updated since original posting) |

Th 4-9 | Combinatorial applications of Konig's lemma |

T 4-14 | Beginnings of a formal proof system |

Th 4-16 | Proofs by resolution and a Hilbert-style proof system |

T 4-21 | Soundness and completeness of our Hilbert-style proof system |

Th 4-23 | First-order logic |

T 4-28 | Definability and isomorphisms |

Th 4-30 | Prenex normal form and games |

T 5-5 | First-order theories |

Th 5-7 | A proof system for first-order logic |

T 5-12 | The Completeness Theorem for first-order logic |

Th 5-14 | The Compactness Theorem for first-order logic |

T 5-19 | The Tarski-Seidenberg Theorem |

Th 5-21 | Finishing Tarski-Seidenberg, decision problems |

T 5-26 and Th 5-28 | Computability, Turing machines, complexity and the class P (these notes are from a different version of the course, so they look somewhat different) |

## HOMEWORK

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

Tuesday, April 7 | Homework 1 | |

Tuesday, April 14 | Homework 2 | |

Tuesday, April 21 | Homework 3 | |

Tuesday, April 28 | Homework 4 | |

Tuesday, May 5 | Homework 5 | |

Tuesday, May 12 | Homework 6 | |

Tuesday, May 19 | Homework 7 | |

Tuesday, May 26 | Homework 8 | |

Tuesday, June 2 | Homework 9 |