compactness of first-order logic
Summary
The Compactness Theorem for first-order logic states that for any set of sentences S, if every finite subset of S has a model, then S has a model. This theorem can be used to show that certain sets of structures are not definable in first-order logic; examples include connected graphs and finite sets of unbounded size. It also enables the nonstandard analysis, where the real number line is extended to include infinitesimals.
Context
This concept has the prerequisites:
- semantics of first-order logic (Compactness is a property of the semantics of first-order logic.)
- completeness of first-order logic (The Compactness Theorem follows from the Completeness Theorem.)
Goals
- Prove the Compactness Theorem of first-order logic, assuming the Completeness Theorem
- Using the Compactness Theorem, show that any first-order theory with an arbitrarily large finite model has an infinite model as well
Core resources (read/watch one of the following)
-Free-
→ Notes on Logic (2013)
Lecture notes for a course on first order logic.
Other notes:
- See Section 10 for the statement and proof of the Compactness Theorem
-Paid-
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
- Section 2.5, "Soundness and completeness theorems," statement and proof of Compactness Theorem on page 142
- Section 2.6, "Models of theories," subsection "Finite models," pages 147-151
See also
-No Additional Notes-