2018-2020 Undergraduate and Graduate Bulletin (with addenda) 
    
    May 27, 2020  
2018-2020 Undergraduate and Graduate Bulletin (with addenda)
Add to Portfolio

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.



Add to Portfolio