Completeness, compactness and consequences

Learning objective. Global first-order facts often follow from finite consistency arguments, but these theorems have precise hypotheses. Running application. An increasingly demanding scheduling specification is feasible at each finite stage, suggesting a first-order compactness argument.

The fifth unit uses theories with indefinitely many distinguishable constants. The key move is to examine an arbitrary finite part: only finitely many inequalities appear, so a sufficiently large finite domain realizes that part. Compactness then produces a model of all inequalities. That model is necessarily infinite, which demonstrates why 'each finite request works' does not imply a finite global solution.

Here the object of study is a metatheorem whose conclusion quantifies over theories or structures, rather than an ordinary sentence evaluated in a domain. Always cite the correct conditional: the premise may require first-order syntax, consistency, satisfiability, finite satisfiability or the presence of an infinite model. Small illustrative structures can motivate the statement but cannot prove it. Give the construction on an arbitrary finite subset or invoke a justified completeness result at the proper stage. This avoids drawing infinite conclusions from a fixed computational bound.

A disciplined learning sequence begins with definitions, continues with a reproducible worked interpretation and ends with a search for a legitimate counterexample. You should be able to write a compact formal claim, list its hypotheses and decide whether it asserts satisfaction in one model, entailment by a theory, or a theorem about models. That choice determines the form of appropriate evidence. Keep one running example throughout the unit and modify its domain, relations, parameters or background theory only when you explicitly say so. Comparing these controlled interventions is more instructive than memorizing isolated definitions.

The five lessons proceed from a manageable definition to a mathematically consequential comparison. The first exercise of each lesson reconstructs its example; the second challenges an unjustified strengthening; the third transfers the idea to an applied specification. Each solution hint is guidance, not a substitute for checking the semantics line by line. Write formal answers with explicit witnesses or countermodels wherever possible.

The statement and its scope

Core principle. Gödel first-order completeness gives T⊨φ iff T⊢φ for an appropriate sound and complete proof calculus.

A worked semantic construction

To show T∪{¬φ} unsatisfiable is to show that φ follows semantically from T; completeness then guarantees a finite formal derivation of φ from T. Analyze this example systematically. Record the language first, then the nonempty domain, the interpretations of constant, function and relation symbols actually in use, and finally the formula under investigation. If no concrete relation is present, interpret the example as an argument about all structures meeting the stated hypotheses and write that change of level explicitly. Each step should say why the mathematical object exists, not merely report the eventual result.

Counterexample discipline and boundary conditions

Frequent mistake. Do not confuse this theorem with computational decidability: validity in full first-order logic is recursively enumerable but not decidable. A meaningful counterexample preserves the hypotheses of the claim being tested while breaking only the proposed conclusion. If a supposed counterexample changes the language, silently changes its constants, or violates one of the axioms, it does not disprove the original claim. Conversely, when the claim is a universal assertion about all models, just one legal countermodel is decisive. Keep these two directions separate: finding a witness is enough for an existential conclusion in a fixed structure; proving universal entailment demands attention to every legal structure.

Proof laboratory: what must be shown

Separate existence of a proof from the runtime needed to discover it. One rigorous route is to write the target as a precise mathematical judgment and split the argument into sound subgoals. A constructive case should produce the structure, map, formula, or witness promised by the judgment. A negative case should produce a legal countermodel or identify an explicit theorem barring the proposed definition. If an implication is being established, prove the forward direction under named assumptions; for an equivalence, prove both directions independently. Do not let a numerical screen result replace a structural proof when the statement ranges over unbounded domains.

Transfer to applied reasoning

Verification pipelines can check certificates without claiming that search will always terminate on invalid inputs. The translation must include the mathematical object corresponding to a real-world identifier, the status of absent or unknown information, and a statement of what the formal model leaves unspecified. A theorem guarantees something given these premises. It cannot establish that the premises faithfully describe a laboratory, database or institutional policy without external evidence. Keep a record of unverifiable assumptions, because a formal derivation may be completely valid even when its data pipeline is flawed.

Three exercises and instructor guidance

Exercise 5.1a — Reconstruct. Rebuild the worked example in the smallest signature needed. State the domain, all nonlogical interpretations and the central truth or preservation claim. Is the conclusion about a single structure or an entire class? Guidance: Begin from: To show T∪{¬φ} unsatisfiable is to show that φ follows semantically from T; completeness then guarantees a finite formal derivation of φ from T. Write a sentence or a formula-with-assignment, and justify the conclusion from the relevant recursive semantic clause or theorem. Name every free variable and every parameter.

Exercise 5.1b — Find a boundary. Test the tempting stronger claim that the principle automatically survives an arbitrary change of vocabulary, domain or interpretation. Give a specific change that would invalidate the inference or explain which hypotheses prevent such a change. Guidance: The primary hazard is: Do not confuse this theorem with computational decidability: validity in full first-order logic is recursively enumerable but not decidable. Construct a countermodel if a universal claim is false; if the claim is valid, identify the preserving map or model-theoretic theorem. A failure to find a counterexample by enumeration does not resolve an unbounded question.

Exercise 5.1c — Apply and audit. Design an audit record for the application scenario below. Include the signature, an intended model, a checkable formula, and one risk of interpreting the result as an external fact. Scenario: Verification pipelines can check certificates without claiming that search will always terminate on invalid inputs. Guidance: State the proof obligation as: Separate existence of a proof from the runtime needed to discover it. Then list the semantic evidence that a verifier can inspect and the external factual assumption that needs separate validation.

The statement and its scope

Core principle. A set of first-order sentences is unsatisfiable exactly when some finite subset is unsatisfiable, by compactness.

A worked semantic construction

If T contains P(c), ∀x(P(x)→Q(x)), and ¬Q(c), those three sentences already form a finite inconsistent core. Analyze this example systematically. Record the language first, then the nonempty domain, the interpretations of constant, function and relation symbols actually in use, and finally the formula under investigation. If no concrete relation is present, interpret the example as an argument about all structures meeting the stated hypotheses and write that change of level explicitly. Each step should say why the mathematical object exists, not merely report the eventual result.

Counterexample discipline and boundary conditions

Frequent mistake. A bounded solver returning unknown is neither a proof of consistency nor a proof of inconsistency. A meaningful counterexample preserves the hypotheses of the claim being tested while breaking only the proposed conclusion. If a supposed counterexample changes the language, silently changes its constants, or violates one of the axioms, it does not disprove the original claim. Conversely, when the claim is a universal assertion about all models, just one legal countermodel is decisive. Keep these two directions separate: finding a witness is enough for an existential conclusion in a fixed structure; proving universal entailment demands attention to every legal structure.

Proof laboratory: what must be shown

Identify the exact finite premises used rather than citing an enormous database. One rigorous route is to write the target as a precise mathematical judgment and split the argument into sound subgoals. A constructive case should produce the structure, map, formula, or witness promised by the judgment. A negative case should produce a legal countermodel or identify an explicit theorem barring the proposed definition. If an implication is being established, prove the forward direction under named assumptions; for an equivalence, prove both directions independently. Do not let a numerical screen result replace a structural proof when the statement ranges over unbounded domains.

Transfer to applied reasoning

Constraint solvers should return an explanatory unsatisfiable subset when one is available. The translation must include the mathematical object corresponding to a real-world identifier, the status of absent or unknown information, and a statement of what the formal model leaves unspecified. A theorem guarantees something given these premises. It cannot establish that the premises faithfully describe a laboratory, database or institutional policy without external evidence. Keep a record of unverifiable assumptions, because a formal derivation may be completely valid even when its data pipeline is flawed.

Three exercises and instructor guidance

Exercise 5.2a — Reconstruct. Rebuild the worked example in the smallest signature needed. State the domain, all nonlogical interpretations and the central truth or preservation claim. Is the conclusion about a single structure or an entire class? Guidance: Begin from: If T contains P(c), ∀x(P(x)→Q(x)), and ¬Q(c), those three sentences already form a finite inconsistent core. Write a sentence or a formula-with-assignment, and justify the conclusion from the relevant recursive semantic clause or theorem. Name every free variable and every parameter.

Exercise 5.2b — Find a boundary. Test the tempting stronger claim that the principle automatically survives an arbitrary change of vocabulary, domain or interpretation. Give a specific change that would invalidate the inference or explain which hypotheses prevent such a change. Guidance: The primary hazard is: A bounded solver returning unknown is neither a proof of consistency nor a proof of inconsistency. Construct a countermodel if a universal claim is false; if the claim is valid, identify the preserving map or model-theoretic theorem. A failure to find a counterexample by enumeration does not resolve an unbounded question.

Exercise 5.2c — Apply and audit. Design an audit record for the application scenario below. Include the signature, an intended model, a checkable formula, and one risk of interpreting the result as an external fact. Scenario: Constraint solvers should return an explanatory unsatisfiable subset when one is available. Guidance: State the proof obligation as: Identify the exact finite premises used rather than citing an enormous database. Then list the semantic evidence that a verifier can inspect and the external factual assumption that needs separate validation.

The statement and its scope

Core principle. If every finite subset of a first-order theory has a model, compactness yields a model of the full theory.

A worked semantic construction

Introduce constants c₀,c₁,… and inequalities cᵢ≠cⱼ for every i≠j. Every finite part has a finite model, so the whole theory has an infinite model. Analyze this example systematically. Record the language first, then the nonempty domain, the interpretations of constant, function and relation symbols actually in use, and finally the formula under investigation. If no concrete relation is present, interpret the example as an argument about all structures meeting the stated hypotheses and write that change of level explicitly. Each step should say why the mathematical object exists, not merely report the eventual result.

Counterexample discipline and boundary conditions

Frequent mistake. Compactness does not assert that there is a finite model of the whole theory; the conclusion is a model of unspecified size. A meaningful counterexample preserves the hypotheses of the claim being tested while breaking only the proposed conclusion. If a supposed counterexample changes the language, silently changes its constants, or violates one of the axioms, it does not disprove the original claim. Conversely, when the claim is a universal assertion about all models, just one legal countermodel is decisive. Keep these two directions separate: finding a witness is enough for an existential conclusion in a fixed structure; proving universal entailment demands attention to every legal structure.

Proof laboratory: what must be shown

Demonstrate finite satisfiability then explicitly invoke compactness. One rigorous route is to write the target as a precise mathematical judgment and split the argument into sound subgoals. A constructive case should produce the structure, map, formula, or witness promised by the judgment. A negative case should produce a legal countermodel or identify an explicit theorem barring the proposed definition. If an implication is being established, prove the forward direction under named assumptions; for an equivalence, prove both directions independently. Do not let a numerical screen result replace a structural proof when the statement ranges over unbounded domains.

Transfer to applied reasoning

Incremental requirement systems need to distinguish local feasibility from a finite global deployment. The translation must include the mathematical object corresponding to a real-world identifier, the status of absent or unknown information, and a statement of what the formal model leaves unspecified. A theorem guarantees something given these premises. It cannot establish that the premises faithfully describe a laboratory, database or institutional policy without external evidence. Keep a record of unverifiable assumptions, because a formal derivation may be completely valid even when its data pipeline is flawed.

Three exercises and instructor guidance

Exercise 5.3a — Reconstruct. Rebuild the worked example in the smallest signature needed. State the domain, all nonlogical interpretations and the central truth or preservation claim. Is the conclusion about a single structure or an entire class? Guidance: Begin from: Introduce constants c₀,c₁,… and inequalities cᵢ≠cⱼ for every i≠j. Every finite part has a finite model, so the whole theory has an infinite model. Write a sentence or a formula-with-assignment, and justify the conclusion from the relevant recursive semantic clause or theorem. Name every free variable and every parameter.

Exercise 5.3b — Find a boundary. Test the tempting stronger claim that the principle automatically survives an arbitrary change of vocabulary, domain or interpretation. Give a specific change that would invalidate the inference or explain which hypotheses prevent such a change. Guidance: The primary hazard is: Compactness does not assert that there is a finite model of the whole theory; the conclusion is a model of unspecified size. Construct a countermodel if a universal claim is false; if the claim is valid, identify the preserving map or model-theoretic theorem. A failure to find a counterexample by enumeration does not resolve an unbounded question.

Exercise 5.3c — Apply and audit. Design an audit record for the application scenario below. Include the signature, an intended model, a checkable formula, and one risk of interpreting the result as an external fact. Scenario: Incremental requirement systems need to distinguish local feasibility from a finite global deployment. Guidance: State the proof obligation as: Demonstrate finite satisfiability then explicitly invoke compactness. Then list the semantic evidence that a verifier can inspect and the external factual assumption that needs separate validation.

The statement and its scope

Core principle. Compactness can construct models of first-order arithmetic containing an element larger than each standard numeral.

A worked semantic construction

Expand a suitable first-order theory true in N with a constant c and sentences c>0, c>1, c>2,… . Every finite subset is satisfiable in N; a model of all sentences makes c nonstandard. Analyze this example systematically. Record the language first, then the nonempty domain, the interpretations of constant, function and relation symbols actually in use, and finally the formula under investigation. If no concrete relation is present, interpret the example as an argument about all structures meeting the stated hypotheses and write that change of level explicitly. Each step should say why the mathematical object exists, not merely report the eventual result.

Counterexample discipline and boundary conditions

Frequent mistake. This argument does not make an actual ordinary natural number larger than all naturals; the new model is not the standard N. A meaningful counterexample preserves the hypotheses of the claim being tested while breaking only the proposed conclusion. If a supposed counterexample changes the language, silently changes its constants, or violates one of the axioms, it does not disprove the original claim. Conversely, when the claim is a universal assertion about all models, just one legal countermodel is decisive. Keep these two directions separate: finding a witness is enough for an existential conclusion in a fixed structure; proving universal entailment demands attention to every legal structure.

Proof laboratory: what must be shown

Explain precisely where compactness creates a nonstandard structure. One rigorous route is to write the target as a precise mathematical judgment and split the argument into sound subgoals. A constructive case should produce the structure, map, formula, or witness promised by the judgment. A negative case should produce a legal countermodel or identify an explicit theorem barring the proposed definition. If an implication is being established, prove the forward direction under named assumptions; for an equivalence, prove both directions independently. Do not let a numerical screen result replace a structural proof when the statement ranges over unbounded domains.

Transfer to applied reasoning

Formal program verification must declare whether it assumes standard arithmetic or arbitrary first-order models. The translation must include the mathematical object corresponding to a real-world identifier, the status of absent or unknown information, and a statement of what the formal model leaves unspecified. A theorem guarantees something given these premises. It cannot establish that the premises faithfully describe a laboratory, database or institutional policy without external evidence. Keep a record of unverifiable assumptions, because a formal derivation may be completely valid even when its data pipeline is flawed.

Three exercises and instructor guidance

Exercise 5.4a — Reconstruct. Rebuild the worked example in the smallest signature needed. State the domain, all nonlogical interpretations and the central truth or preservation claim. Is the conclusion about a single structure or an entire class? Guidance: Begin from: Expand a suitable first-order theory true in N with a constant c and sentences c>0, c>1, c>2,… . Every finite subset is satisfiable in N; a model of all sentences makes c nonstandard. Write a sentence or a formula-with-assignment, and justify the conclusion from the relevant recursive semantic clause or theorem. Name every free variable and every parameter.

Exercise 5.4b — Find a boundary. Test the tempting stronger claim that the principle automatically survives an arbitrary change of vocabulary, domain or interpretation. Give a specific change that would invalidate the inference or explain which hypotheses prevent such a change. Guidance: The primary hazard is: This argument does not make an actual ordinary natural number larger than all naturals; the new model is not the standard N. Construct a countermodel if a universal claim is false; if the claim is valid, identify the preserving map or model-theoretic theorem. A failure to find a counterexample by enumeration does not resolve an unbounded question.

Exercise 5.4c — Apply and audit. Design an audit record for the application scenario below. Include the signature, an intended model, a checkable formula, and one risk of interpreting the result as an external fact. Scenario: Formal program verification must declare whether it assumes standard arithmetic or arbitrary first-order models. Guidance: State the proof obligation as: Explain precisely where compactness creates a nonstandard structure. Then list the semantic evidence that a verifier can inspect and the external factual assumption that needs separate validation.

The statement and its scope

Core principle. The class of all finite structures is not first-order axiomatizable over an unrestricted nonempty domain by a single first-order sentence or theory that has exactly all finite structures.

A worked semantic construction

If T has arbitrarily large finite models, add inequalities among infinitely many distinct constants; by compactness T has an infinite model. Thus no first-order theory characterizes finiteness over all structures. Analyze this example systematically. Record the language first, then the nonempty domain, the interpretations of constant, function and relation symbols actually in use, and finally the formula under investigation. If no concrete relation is present, interpret the example as an argument about all structures meeting the stated hypotheses and write that change of level explicitly. Each step should say why the mathematical object exists, not merely report the eventual result.

Counterexample discipline and boundary conditions

Frequent mistake. Finiteness of a fixed bounded domain can be expressed; the impossibility concerns uniform first-order descriptions over unbounded structures. A meaningful counterexample preserves the hypotheses of the claim being tested while breaking only the proposed conclusion. If a supposed counterexample changes the language, silently changes its constants, or violates one of the axioms, it does not disprove the original claim. Conversely, when the claim is a universal assertion about all models, just one legal countermodel is decisive. Keep these two directions separate: finding a witness is enough for an existential conclusion in a fixed structure; proving universal entailment demands attention to every legal structure.

Proof laboratory: what must be shown

State the intended class of domains before invoking nondefinability. One rigorous route is to write the target as a precise mathematical judgment and split the argument into sound subgoals. A constructive case should produce the structure, map, formula, or witness promised by the judgment. A negative case should produce a legal countermodel or identify an explicit theorem barring the proposed definition. If an implication is being established, prove the forward direction under named assumptions; for an equivalence, prove both directions independently. Do not let a numerical screen result replace a structural proof when the statement ranges over unbounded domains.

Transfer to applied reasoning

Database systems operating only on finite structures can have capabilities not expressible by one uniform first-order sentence. The translation must include the mathematical object corresponding to a real-world identifier, the status of absent or unknown information, and a statement of what the formal model leaves unspecified. A theorem guarantees something given these premises. It cannot establish that the premises faithfully describe a laboratory, database or institutional policy without external evidence. Keep a record of unverifiable assumptions, because a formal derivation may be completely valid even when its data pipeline is flawed.

Three exercises and instructor guidance

Exercise 5.5a — Reconstruct. Rebuild the worked example in the smallest signature needed. State the domain, all nonlogical interpretations and the central truth or preservation claim. Is the conclusion about a single structure or an entire class? Guidance: Begin from: If T has arbitrarily large finite models, add inequalities among infinitely many distinct constants; by compactness T has an infinite model. Thus no first-order theory characterizes finiteness over all structures. Write a sentence or a formula-with-assignment, and justify the conclusion from the relevant recursive semantic clause or theorem. Name every free variable and every parameter.

Exercise 5.5b — Find a boundary. Test the tempting stronger claim that the principle automatically survives an arbitrary change of vocabulary, domain or interpretation. Give a specific change that would invalidate the inference or explain which hypotheses prevent such a change. Guidance: The primary hazard is: Finiteness of a fixed bounded domain can be expressed; the impossibility concerns uniform first-order descriptions over unbounded structures. Construct a countermodel if a universal claim is false; if the claim is valid, identify the preserving map or model-theoretic theorem. A failure to find a counterexample by enumeration does not resolve an unbounded question.

Exercise 5.5c — Apply and audit. Design an audit record for the application scenario below. Include the signature, an intended model, a checkable formula, and one risk of interpreting the result as an external fact. Scenario: Database systems operating only on finite structures can have capabilities not expressible by one uniform first-order sentence. Guidance: State the proof obligation as: State the intended class of domains before invoking nondefinability. Then list the semantic evidence that a verifier can inspect and the external factual assumption that needs separate validation.

Part A: specify the vocabulary. From this unit's running application, choose one nonempty domain and a minimal signature. Interpret each constant, function and relation explicitly. Write at least two sentences: one intended to hold and one intended to fail. If the unit focuses on a metatheorem rather than one finite example, explain why the running finite structure is illustrative rather than the theorem's proof.

Part B: produce a controlled comparison. Construct a second structure, a second theory or a modified formula connected with one of this unit's five lessons. Change exactly one semantically significant feature and compute what happened to the truth conditions. If the proposed preservation theorem is invalid, supply a legal counterexample. If it is valid, outline the inductive or theorem-based reason that every relevant formula is preserved.

Part C: critique the claim. A hypothetical reviewer states that the exercise establishes the result 'for all structures of any size'. Explain whether that is justified, using this unit's central distinction: Global first-order facts often follow from finite consistency arguments, but these theorems have precise hypotheses. State the strongest conclusion that the evidence supports. Identify one mathematical assumption and one practical assumption that would need separate checking before applying the result to the real-world scenario.

Suggested response framework. Include the written signature; a complete interpretation table; formulas with all quantifiers and parentheses; one explicit witness or countermodel; a short derivation of the outcome; and a paragraph describing the limitations. Students working collaboratively should swap their artifacts and test whether another reader can reproduce the same evaluation without informal clarification.

• I can restate the five definitions of this unit accurately, with all needed hypotheses.
• I can build a legitimate small example and evaluate its key formulas.
• I can name at least one tempting invalid strengthening and diagnose it.
• I can distinguish first-order truth from real-world empirical truth.
• I can identify which claims require proof beyond a finite simulation.