Courses:

Logic II >> Content Detail



Syllabus



Syllabus

A list of topics by lecture is available in the calendar listed below.



Description


We'll begin with an introduction to the theory of computability, then proceed to a detailed study of its most illustrious result: Kurt Gödel's theorem that, for any system of true arithmetical statements we might propose as an axiomatic basis for proving truths of arithmetic, there will be some arithmetical statements that we can recognize as true even though they don't follow from the system of axioms. In my opinion, which is widely shared, this is the most important single result in the entire history of logic, important not only on its own right but for the many applications of the technique by which it's proved. We'll discuss some of these applications, among them: Church's theorem that there is no algorithm for deciding when a formula is valid in the predicate calculus; Tarski's theorem that the set of true sentence of a language isn't definable within that language; and Gödel's second incompleteness theorem, which says that no consistent system of axioms can prove its own consistency.

The text for the course will be lecture notes.



Grading


There will be homework assignments every week or two, and they will be the basis for your grade in the course. I would encourage you to work together on the homework, but when you finally sit down to write up your answers, you should work by yourself without looking at anyone else's efforts.



Calendar



LEC #TOPICSKEY DATES
1Why Study Computability?
2-3Key Computability Concepts
4The Language of Arithmetic
5Church-Turing Thesis
6Nonstandard Models of Arithmetic
7Gödel NumberingHomework 1 due
8Robinson's ArithmeticHomework 2 due
9-10Coding Proofs
11-12Peano ArithmeticHomework 3 due in Lec #12
13-14Self-Reference Lemma
15-16First Incompleteness TheoremHomework 4 due in Lec #16
17Interpretations
18Tarski's Theory of TruthHomework 5 due
19

Gödel, Mechanism, and Mind

Articles by Lucas and Benacerraf

20-21Second Incompleteness TheoremHomework 6 due in Lec #21
22Introduction to Modal Logic
23-24Provability LogicHomework 7 due in Lec #23
25Defining ExponentiationHomework 8 due

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.