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 341, 375, 421 or 521 or graduate or professional standing or member of the Pre-Masters Mathematics (Visiting International) Program