Mathematical Logic

This introduction to mathematical logic will focus on three interacting topics. First, computability. The main question here is which mathematical tasks can be accomplished by a "mechanical procedure", of the kind that could be implemented on a computer. Given a certain precise definition of 'mechanical procedure', one can prove that some important tasks cannot be solved by mechanical procedures thus defined.

The second topic is metatheory for first-order logic. In introductory logic one learns to use systems of propositional and predicate logic, such as truth tables and derivation systems. In mathematical logic, rather than doing proofs in the various systems of logic, we prove things about those systems of logic. One can prove, for example, that for any argument of propositional logic that is valid according to truth tables, there exists a derivation of that argument's conclusion from its premises.

The final topic is the metatheory of arithmetic, specifically, Gödel’s incompleteness theorems. This concerns the limitations of the axiomatic method as applied to arithmetic. The axiomatic method works as follows: a few arithmetic claims that seem certainly true are taken as axioms, and some patterns of inference that seem undeniably correct are taken as rules. We then derive theorems from the rules and axioms: a theorem is any claim that can be derived by a finite sequence of applications of rules to axioms and previously proved theorems. Gödel proved the startling result that truth in arithmetic cannot be completely captured by the axiomatic method: for any consistent (and “recursive”) set of axioms we choose, there will be true statements of arithmetic that are not theorems, and are thus beyond the reach of our chosen axioms.

This course is reasonably difficult. It isn't hard computationally (you won’t have to use a calculator), but you must master difficult, abstract proofs, and produce some of your own.

Text

Required: George Boolos and Richard Jeffrey, Computability and Logic, 3rd ed. (Cambridge: 1989). We will doing chapters 1-15, in order, skipping chapters 4, 8, 13, and parts of 14. If we have time we'll do parts of some later chapters. Recommended: Gödel's Proof, by Ernest Nagel and James R. Newman.

Requirements/Grading

75% exams, 25% homework. There will be two or three in-class exams; dates and times TBA; there will be between 5 and 10 homework assignments. Graduate students may be asked to answer different questions on exams than undergraduates. I will put answers to homework problems on reserve after the assignments have been handed in. The homework assignments will sometimes require significant effort and ingenuity. I don't expect you always to be able to get all of the homework problems correct, so don't fret if you get stuck: just do the best you can.