Frequency:
Fall
Student Body:
majors in mathematics, computer science and philosophy. Graduate students in related areas
Background and Goals:
This course provides an introduction into mathematical logic, including the syntax and semantics of first-order languages, a formal calculus for proofs, Gödel's Completeness Theorem and the compactness theorem, nonstandard models of arithmetic, decidability and undecidability, and Gödel's Completeness Theorem. It is particularly suitable for majors in mathematics, computer science and philosophy.
Alternatives:
None.
Subsequent Courses:
Math 770.
Course Content:
- Propositional logic: Connectives and proposition symbols. Formation rules. Parsing sequences for wffs and induction on wffs. Formal tableau proofs. Models and truth values. Soundness and completeness theorems.
- Predicate logic: Logic with quantifiers, variables, and predicate symbols. Formation rules. Models, valuation of variables, and truth values. Tableau proofs. Soundness and completeness theorems. Direct proofs and informal proofs in the usual mathematical style.
- Full predicate logic: Predicate logic with equality and function symbols. Formation rules and models. Tableau proofs with equality substitutions. Examples from calculus, set theory, and group theory. Peano arithmetic and formal induction. Soundness and completeness.
- Undecidability: Machine computability. Gödel numbers and universal machines. Church's Thesis. Examples of undecidable problems including the halting problem. Undecidability of predicate logic and the Gödel incompleteness theorem.
credits:
3 (X-A)
semester:
Fall
prereqs:
Math 340 or 341 or 375. Previous serious exposure to understanding and writing proofs is required in Math 571. Math 521 or Math 541 are encouraged, but any of the courses Math 341, Math 375-76, Math 421, Math 441 or Math 461 could suffice. Admission to Math 571 is also possible with the consent of the instructor.