eduKateSG · Mathematical Logic · Worked learning guide
Find the reasoning step you need
Distinguish a finite set of sentences from a finite model, then use compactness to understand infinite requirements and the limits of first-order descriptions.
1. State the theorem with its quantifiers intact
3. Build a theory that requires arbitrarily many objects
5. Explain why first-order sentences cannot characterise finiteness
7. Separate all models from a fixed intended structure
9. Practise the hypothesis and conclusion separately
Full chapter index · Practice and checking · Mathematical Logic subject guide
A collection of infinitely many requirements can be jointly satisfiable even when no single finite structure meets all of them. The compactness theorem explains an important connection between finite pieces of a first-order theory and the theory as a whole.
The gold standard is to keep two meanings of finite separate: finitely many sentences and finitely many domain objects. Confusing them changes the theorem.
This guide uses classical first-order logic with identity and standard nonempty domains. It develops original model constructions and explains the scope of the theorem; it does not present compactness as a practical algorithm for checking an arbitrary infinite list. Start with Mathematical Logic for the subject map.
Chapter index
Chapters 1–4
Chapters 5–8
Chapters 9–10
The compactness theorem says that a set Γ of first-order sentences is satisfiable if and only if every finite subset of Γ is satisfiable.
The forward direction is immediate. A model of all of Γ satisfies any subset of Γ. The reverse direction is the substantial result: models for all finite pieces guarantee a model for the entire set.
The finite pieces need not share the same model. A model satisfying the first selected piece may fail requirements appearing in another piece. Compactness guarantees that some model satisfies everything, rather than saying that any one previously chosen model will do.
Every finite subset means every one
Checking a few initial segments is insufficient unless there is a general argument covering every finite subset. For an indexed list of sentences, one can sometimes prove that each finite subset is contained in a satisfiable initial segment. That supplies the needed argument.
A numerical experiment over the first hundred sentences does not, by itself, establish finite satisfiability of an infinite theory. The theorem’s hypothesis is universal over finite subsets.
The theorem concerns first-order sentences under the stated semantics. It should not be transferred automatically to full second-order logic, arbitrary extensions of the language, or a class of interpretations restricted only to finite structures.
The reader should be able to repeat the theorem without replacing “finite subset” with “finite model.” That small wording check prevents the most common misunderstanding before any advanced application begins.
A finite theory can require an infinite domain. Let the language contain a unary function f. State that f is injective and that some object is not an output of f.
The injectivity sentence is ∀x∀y(f(x) = f(y) → x = y). The missing-output sentence is ∃z∀x f(x) ≠ z. Together these two sentences have an infinite model on ℕ with f(n) = n + 1.
They have no finite model. An injective total self-map on a finite set is surjective, contradicting the missing-output requirement.
The size of the sentence set is not the size of the model
There are only two sentences in this example. Their satisfiability does not imply a model with two objects, or any finite number of objects.
Conversely, an infinite set of sentences can be satisfied by a small finite model if its requirements permit one. Repeating compatible conditions in many forms does not necessarily demand more domain objects.
This distinction connects directly with finite countermodels and their limits. A finite search may miss a model because the required structure is infinite, rather than because too few formulas were checked.
A compactness argument must identify what is finite at each step. Write “finite subset of sentences” and “finite domain” in full until the roles are clear.
The theorem’s conclusion promises a model. It does not promise that the model is finite, small, familiar, unique or the intended real-world interpretation.
For each positive integer n, let σ_n say that at least n distinct objects exist. For example, σ_2 is ∃x∃y(x ≠ y). The sentence σ_3 uses three witnesses and requires each pair to be distinct.
Let Γ = {σ_1, σ_2, σ_3, …}. Any finite subset mentions only finitely many lower bounds. Let N be the largest index appearing in that subset. A domain with N objects satisfies every selected sentence.
Thus every finite subset is satisfiable. Compactness yields a model of all of Γ. Such a model must be infinite because it has at least n objects for every positive integer n.
The models can grow with the finite piece
A two-object domain satisfies σ_1 and σ_2 but not σ_3. A ten-object domain satisfies the first ten bounds but fails σ_11. No fixed finite domain satisfies the entire theory.
This is consistent with compactness. Its premise never required one fixed finite model for every piece. It allowed a suitable model to be chosen separately for each finite subset.
The example also supplies a direct infinite model: any infinite domain satisfies all the distinctness requirements. Compactness is not needed to guess that particular model. The construction is useful because it makes the theorem’s quantifier pattern visible.
Compare “for each finite subset there is a model” with “there is one model for every sentence.” Compactness bridges these statements for first-order theories. The bridge is a theorem, not a generally valid swap of ∀ and ∃ in arbitrary situations.
Suppose a first-order theory T has finite models of arbitrarily large size. Add the size requirements σ_n from the preceding chapter, and consider T ∪ {σ_n: n ≥ 1}.
Take any finite subset Δ of this enlarged theory. It contains only finitely many size requirements, so there is a largest relevant lower bound N. Choose a finite model of the whole T with at least N objects.
That model satisfies every sentence from T appearing in Δ and every size requirement in Δ. Hence every finite subset of the enlarged theory is satisfiable. Compactness gives a model satisfying T and all size requirements, which must be infinite.
What the hypothesis really says
Arbitrarily large finite models means there is no finite upper bound on the available model sizes. It does not require a model at every exact positive size.
A theory with models only at certain unbounded finite sizes still meets the hypothesis. For a finite subset needing at least N objects, any sufficiently large available size works.
The conclusion does not say every theory with a finite model also has an infinite one. A theory asserting exactly three objects has a finite model but no arbitrarily large finite models.
The proof is a reusable template: add sentences requiring a desired collection of finite approximations, show each finite selection can be satisfied, and apply compactness. Every application still needs its own hypothesis check.
A clear solution identifies which original model supplies the finite subset and why it also meets the extra size bound. Without that step, “by compactness” can hide the main reasoning rather than complete it.
CHAPTER 5 OF 10
5. Explain why first-order sentences cannot characterise finiteness
Suppose one first-order sentence F were true exactly in all finite nonempty structures of a fixed vocabulary and false in all infinite structures.
Then {F} would have finite models of arbitrarily large size: every finite nonempty structure of that vocabulary would satisfy F. The preceding compactness argument would produce an infinite model of F.
That contradicts the proposed characterisation. Therefore no such first-order sentence exists under ordinary semantics.
The argument extends to a first-order theory whose models were claimed to be exactly all finite structures: arbitrarily large finite models would again force an infinite one.
Do not weaken the conclusion into a different claim
First-order logic can express “exactly three objects exist.” It can express “at most ten objects exist.” It can also express infinitude by an infinite collection of lower-bound sentences such as Γ, with identity.
The limitation concerns characterising the whole class of finite structures by a first-order theory. It does not mean first-order logic cannot count any finite number or distinguish any finite model sizes.
Nor does it mean the everyday word finite is meaningless. It is a statement about the expressive resources of a particular formal language and semantics.
This is a useful lesson in mathematical communication. A limit theorem should be repeated at the same strength and scope at which it was proved. Turning it into “logic cannot describe size” would discard the carefully stated distinctions that make the result interesting.
A consequence of compactness is that if a first-order theory Γ is unsatisfiable, some finite subset is already unsatisfiable. A conflict cannot require every sentence of an infinite set while all finite pieces remain satisfiable.
This does not give a computable bound on how many sentences must be examined in every case. It also does not provide a general terminating procedure for deciding whether a given first-order set is satisfiable.
For a simple indexed example, imagine Γ contains many harmless sentences followed by p and ¬p. The finite conflict is just those two sentences, wherever they occur. Examining only an early prefix may miss both.
Entailment uses finitely many premises
If Γ entails C in first-order logic, then some finite Γ₀ ⊆ Γ already entails C. To see this, Γ ∪ {¬C} is unsatisfiable. Compactness supplies a finite unsatisfiable subset.
If that subset includes ¬C, the remaining finite premises entail C. If it does not, the selected finite premises are already unsatisfiable and classically entail C as well.
The result aligns with finite proofs: a particular formal derivation uses only finitely many premises. It does not say that one finite subset suffices for every possible conclusion of an infinite theory.
Different conclusions may require different finite subsets. A theory can still have infinitely many independent requirements.
A practical report should therefore distinguish an existence guarantee from a search guarantee. Compactness says a finite conflict or finite premise support exists in the stated situations. Finding it, bounding it and choosing a repair are further tasks.
Compactness concerns whether some first-order structure satisfies a theory. It does not guarantee a solution within one preselected structure.
Over the standard natural numbers, consider a new constant c together with the requirements c > 0, c > 1, c > 2, and so on, interpreting each numeral and the order in their usual way. Any finite collection can be met by choosing c larger than its greatest bound.
No standard natural number satisfies all those requirements. This does not refute compactness, because the overall problem has been restricted to one fixed intended arithmetic structure.
If one includes the full first-order theory true in the standard natural numbers and adds the c-bounds, compactness supplies another model of that theory with an element above every standard numeral. The new model is not the standard natural-number structure.
Keep the conclusion appropriately labelled
The existence of such a model does not produce a previously overlooked ordinary natural number. It shows that first-order sentences true in the intended structure can also hold in a different structure with additional behaviour.
This is an advanced application, so its role here is limited: it makes the interpretation class explicit. If a practical task asks for a value within a fixed finite roster or the standard integers, a model somewhere in the full first-order class may not answer that task.
A valid theorem can be applied to the wrong class of models. State whether the target is any interpretation, a finite interpretation or one specified structure before invoking compactness.
Compactness says that any particular consequence of a first-order theory uses only finitely many premises semantically. It does not say the entire theory can be replaced by one finite subset.
For an original example, use infinitely many unary predicates P₁, P₂, P₃, … and theory T = {∀x P_n(x): n ≥ 1}. Any finite subset mentions only finitely many predicate symbols.
Choose an index k not mentioned there. On a one-object domain, make every mentioned predicate true and P_k false. This model satisfies the selected finite subset but fails ∀x P_k(x), which is part of T.
Therefore no finite subset of T has exactly all T’s consequences. Each individual premise of T has finite support—namely itself—while the whole infinite collection cannot be discarded in favour of one finite selection.
This example concerns replacement by a finite subset of the displayed theory. Claims about some different finite axiomatisation require their own language and expressibility argument.
The distinction is useful when reading a proof that cites only a few assumptions from a large background theory. That proof has finite support; it does not establish that the entire background theory is redundant beyond those assumptions.
Exercise 1: finite pieces with growing models
For Γ = {σ_n: n ≥ 1}, show that {σ_2, σ_5, σ_8} is satisfiable. Any eight-object domain works. Explain why no finite domain satisfies all of Γ.
Exercise 2: exactly three
Let T assert exactly three domain objects. Does T have arbitrarily large finite models? No. The infinite-model consequence does not apply.
Exercise 3: a finite theory with only infinite models
Use the injective nonsurjective self-function theory. Verify its model on ℕ with successor, and explain why finite total self-maps cannot satisfy both premises.
Exercise 4: the wrong inference
A learner checks the first fifty sentences of an infinite list and finds a model. Has finite satisfiability been established? No. The hypothesis requires every finite subset, supported by a general argument or equivalent justification.
Transfer check
Write a compactness argument in four parts: the original theory, the added sentences, a model for an arbitrary finite subset, and the property forced in the final model.
Mark each occurrence of finite as referring to sentences or objects. Then state one thing the theorem does not promise, such as a finite model or a terminating search. This final scope check keeps the theorem’s power and limitations together.
Frequently asked questions
Does finite satisfiability mean a finite model exists? No. It means every finite subset of sentences has some model.
Must all finite subsets use the same model? No. Their models can differ.
Does compactness decide satisfiability automatically? No. Its model-existence guarantee is not a general decision procedure.
Can first-order logic express exactly n objects? Yes, for each specified finite n, using identity and suitable quantifiers.
Connected reading
Return to Mathematical Logic. Use finite countermodels for the difference between finite and unrestricted interpretation classes, and existence and identity for distinct-object formulas.
Sources and scope
The compactness theorem and its standard model-existence applications were checked against the Open Logic Project text, first-order completeness and compactness sections, accessed 22 October 2026. The lower-bound theory and proof explanations are developed explicitly here. The stated setting is ordinary classical first-order logic; no extension to finite-only semantics or stronger languages is assumed.
Contents · Previous chapter · Continue to Mathematical Logic
Explore models, proofs and their limits
Consistency and conflicting premises