- Place and Time:
- Instructor: Robin Smith (rasmith@tamu.edu)
- Office: Bolton 314
- Telephone: 845-5696

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.

- José L. Zalabardo,
*Introduction to the Theory of Logic*. Westview Press, 1999. ISBN 0-8133-6602-X

- Homework asssignments (8): 20%
- Mid-term exam (take-home): 40%
- 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).

- Week 1
- Review of first-order theory: syntax, semantics of FOL
- Review of first-order theory: completeness, soundness of FOL

- Week 2
- Defining cardinal numbers
- Cardinalities of sets

- Week 3
- Cantor's diagonal argument; uncountable sets
- Russell's Paradox and ZF

- Week 4
- The Continuum Hypothesis
- The Axiom of Choice and Zorn's Lemma

- Week 5
- Completeness for uncountable languages
- Isomorphic structures

MID-TERM EXAM DISTRIBUTED

- Week 6
- The Downwards Löwenheim-Skolem Theorem

MID-TERM EXAM DUE - The Upwards Löwenheim-Skolem Theorem

- The Downwards Löwenheim-Skolem Theorem
- Week 7
- Categoricity; Morely's Categoricity Theorem
- Non-Standard Models for Arithmetic

- Week 8
- Non-Standard Models for Arithmetic, again
- Decision procedures and Decidability

- Mar. 10, 12: Spring Break
- Week 9
- The Decision Problem for First-Order Logic
- Church's Theorem

- Week 10
- Church's Theorem
- Formal Arithmetic

- Week 11
- Recursive Functions
- Primitive Recursive Functions and Computability; Church's Thesis

- Week 12
- Computable Numbers
- Gödel's First Incompleteness Theorem: Arithmetizing Syntax

- Week 13
- Gödel's First Incompleteness Theorem: Representability
- Gödel's First Incompleteness Theorem: Representability, again

- Week 14
- Gödel's First Incompleteness Theorem: The "Diagonal" Argument
- Gödel's "Diagonal" Argument, again

FINAL EXAM DISTRIBUTED

- Week 15
- Extensions of Gödel's Theorem
- FINAL EXAM DUE

Please see the Texas A&M University Student Rules

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.