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:


  • 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.
Author: Henry Cohn
Other notes:
  • See Section 10 for the statement and proof of the Compactness Theorem


See also

-No Additional Notes-