This course is meant to be a second course in symbolic logic, intended to provide a foundation for understanding current research in philosophical logic and related areas of cognitive science. I will devote some time to review of basic techniques of formalization, in propositional logic and first-order predicate logic, but it will be assumed that students are familiar with this from an introductory course. The course will concentrate on the theory of logic and computation, and will cover the following topics:
- The nature of algorithms; some models of computation; basic limitative results
- Proof techniques and proof theory
- Models and validity
- Semantic completeness of propositional and quantificational logic; Löwenheim-Skolem theorem
- Incompleteness of formal arithmetic and undecidability of first-order logic; Gödel's second theorem on the unprovability of consistency.
Written work will consist of problem sets every two weeks, plus and midterm and final exams.
This is a fast-moving course that assumes some previous familiarity with logic and the ability to understand and construct mathematical proofs. Students who are uncertain about their mathematical background may wish to consult with the instructor before taking this course.
Two lectures of 1.5 hours each