MATH 409 - Introduction to Mathematical Logic (3)

Propositional and first-order logic are developed. The basic framework of formal languages, logical structures and their models is given. Formal deductive systems for logical proofs are set in an algorithmic framework. The completeness and compactness theorems for consistent axiom systems are proven, including the Lowenheim-Skolem theorems. The last half of the course focuses on the work of Goedel. Using Goedel’s numbering of number theoretic formulae and proofs, his theorem asserting the incompleteness (inability to prove all true statements) of any consistent axiomatization of the natural numbers that is recursively given are proven. Related results of Tarski and Rosser, his second incompleteness theorem; the impossibility of Peano arithmetic, if consistent, to prove its own consistency are also proven. Time permitting, the course will introduce Goedel’s proof of the consistency of Cantor’s continuum hypothesis and axiom of choice with the usual axioms of set theory.

Grading: Graded/Satisfactory Unsatisfactory/Audit
Course ID: 55243
Consent: No Special Consent Required
Components: Lecture
Prerequisite: CMSC 441, MATH 301, or PHIL 346 with a grade of ‘C’ or better.