completeness of first-order logic
Summary
Godel's Completeness Theorem shows that there is a complete (and sound) deductive calculus for first-order logic. In other words, if some set of sentences is consistent (one cannot derive a contradiction from them), then there is some model in which all the sentences are satisfied. This result is significant in that it unifies the syntax and semantics of first-order logic.
Context
This concept has the prerequisites:
- first-order logic
- semantics of first-order logic (Defining completeness requires defining the semantics.)
- proofs in first-order logic (One must show a particular predicate calculus to be complete.)
- countable sets (The proof of the Completeness Theorem involves countable sets.)
Goals
- Know what it means for a first-order deductive calculus to be complete
- Know the statement of Godel's Completeness Theorem
- Prove Godel's Completeness Theorem (Henkin's proof in particular)
- Using the Completeness Theorem, prove the Compactness Theorem for first-order logic.
Core resources (read/watch one of the following)
-Free-
→ Notes on Logic (2013)
Lecture notes for a course on first order logic.
-Paid-
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
- Section 2.2, "Truth and models," subsection "Homomorphisms," pages 94-99
- Section 2.5, "Soundness and completeness theorems," pages 131-145
Other notes:
- Refer to Section 2.4 for the specific deductive calculus.
→ A Course in Mathematical Logic
A graduate textbook in mathematical logic.
- Section 2.7, "Hintikka sets," pages 83-88
- Section 3.3, "Completeness of the first-order predicate calculus," pages 117-122
- Section 3.5, "What have we achieved?", pages 122-124
See also
-No Additional Notes-