compactness of first-order logic
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.
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.)
- 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)
→ Notes on Logic (2013)
Lecture notes for a course on first order logic.
- See Section 10 for the statement and proof of the Compactness Theorem
→ 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
-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