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.

Location: Section 11, "Consequences of compactness," pages 25-28

[external website]

Author: Henry Cohn

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