Compactness Theorem (Sentential)

Satisfiable if and only if every finite subset is.

The idea

Theorem (Compactness Theorem).

A set $\Sigma$ of sentences of sentential logic is satisfiable if and only if every finite subset of $\Sigma$ is satisfiable.

Here $\Sigma$ is satisfiable when a single truth assignment makes every member of $\Sigma$ true at once. For a finite $\Sigma$ this is a finite check. For an infinite $\Sigma$ it demands an assignment defined on infinitely many sentence symbols and meeting infinitely many conditions, and no procedure can inspect them all.

One direction is immediate: an assignment satisfying all of $\Sigma$ satisfies each finite subset. The content is the converse, which says that unsatisfiability is never a purely global property: if $\Sigma$ cannot be satisfied, then some finite subset of $\Sigma$ is already unsatisfiable. Every failure has a finite witness.

This is how compactness is applied. To show that an infinite object with a given property exists, encode the property as a set of sentences arranged so that each finite subset speaks only about a finite piece of the object. Checking the finite pieces is ordinary finite mathematics, and the theorem then delivers an assignment satisfying the whole set — the infinite object itself.

Ways to work on it

• Walkthrough. The biconditional, finite satisfiability, and the finite-consequence corollary.
• Practice. Decide whether a described infinite set is finitely satisfiable.
• Hardest. Apply compactness to lift finite 3-colorability to an infinite graph.

Not sure where to start? Take the ten-question placement test.