PL-UY 3004 Metalogic

4 Credits

What is the relation between truth and proof? Are there true statements about natural numbers that cannot, in principle, be proven? Can an algorithm be written to decide which statements about numbers are provable and which are not? What is the mathematical basis of the concept of a mechanically implementable algorithm (i.e., a computer program)? What does all of this have to do with logic? This course addresses these and other questions by investigating the properties of propositional and 1st-order logic. Topics include the soundness and completeness of formal systems of propositional and 1st-order logic, the Löwenheim-Skolem and Compactness theorems for 1st-order logic, Gödel’s incompleteness theorems for formal arithmetic, and Turing machines and the notions of computability and undecidability.

Prerequisite(s): PL-UY 2004 or permission of the instructor.
Note: Satisfies a humanities and social sciences elective.