# 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-