Ma 6c:  Introduction to Discrete Mathematics (Spring 2014-15)

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

## PREREQUISITES

The only prerequisites are Ma 6ab.

## SCHEDULE

TR 13:00 - 14:25, 153 Sloan

## INSTRUCTORS

Jay Williams
POSTDOCTORAL SCHOLAR IN MATHEMATICS
256 Sloan
626-395-4338
jaywill@caltech.edu

## TA's

• William Chan
Sloan 160
wcchan@caltech.edu
• Jim Tao
Sloan 155
jtao@caltech.edu

## OFFICE HOURS

• Jay Williams: F 10:30-11:30 AM
• William Chan: Sun 6-7 PM
• Jim Tao: M 7-8 PM

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

## TEXTBOOKS

There will be no textbook. The course will be self-contained.

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