completeness of first-order logic
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.
This concept has the prerequisites:
- 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)
→ Notes on Logic (2013)
Lecture notes for a course on first order logic.
→ 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
- 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
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation