PHIL 642: Mathematical Logic II

This course is a continuation of the study of the metatheory of first-order predicate logic begun in PHIL 641, Mathematical Logic I. It will cover the theory of first-order languages and arithmetic through Gödel's First Incompleteness Theorem.

After a brief review of the basic completeness and soundness results concerning first-order logic, the course will present the elements of set theory and transfinite arithmetic, including Cantor's diagonal argument and Cantor's theorem, Zermelo-Fraenkel set theory, the Axiom of Choice and Zorn's Lemma. We will then consider the extension of completeness results to non-denumerably infinite languages.

We will next consider the question of expressive completeness for languages of arbitrary cardinality, concerning which the most important results are the (upwards and downwards) Löwenheim-Skolem theorems. This will lead to consideration of "Skolem's Paradox" and non-standard models for arithmetic.

Next, the course will cover fundamental results in decision theory and computability. After defining the basic notions of 'decision procedure' and 'decidable set', we will consider first the relatively simple application to propositional logic, where theoremhood is decidable. We will then explore the decision problem for logical consequence in first-order languages and its (negative) solution in Church's Theorem (the proof of which will only be sketched).

Finally, we will develop the materials necessary for a proof of Gödel's First Incompleteness Theorem, beginning with a formal theory of arithmetic. We will then develop a basic theory of recursive functions and show how such functions may be represented in our formal arithmetic. Then, using Gödel's device of representing the formulas and proofs of our formal arithmetic with numbers, we will show how statements about the syntax of formulas and proofs in the language can in effect be converted into statements of arithmetic and thus represented in the formal language itself. Using this device and an argument broadly similar to Cantor's diagonal argument, we then show how to derive a formula that is formally undecidable in the language.

Texts

The text for this class is: This course presupposes a general familiarity with the material in the first five Chapters of Zalabardo and, after a brief initial review, will begin with Chapter 6. In addition to this text, supplementary notes will be distributed on Church's Theorem, Recursive Functions and Computability, and Gödel's First Incompleteness Theorem.

Formal Work

  1. Homework asssignments (8): 20%
  2. Mid-term exam (take-home): 40%
  3. Final exam (take-home): 40%

In addition, we will work through a number of proofs in class. Understanding the nature of proofs in logical theory is a fundamental aspect of this course, and students will occasionally be asked to make presentations of proofs of theorems in class (with advance warning).

Schedule


Policies on Academic Dishonesty

Please see the Texas A&M University Student Rules

Americans with Disabilities Act

The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accomodation of their disabilities. If you believe you have a disability requiring an accomodation, please contact the Department of Student Life, Services for Students with Disabilities in Room 126 of the Koldus Building, or call 845-1637.