Applications, verification and semantic boundaries

Learning objective. The model-theoretic viewpoint supplies precise guarantees and counterexamples while exposing the limits of finite experimentation. Running application. A research team must publish the structures, signatures and assumptions behind every formal claim.

The final unit treats a database or graph as a particular mathematical interpretation. If one node has no outgoing neighbor, the sentence ∀x∃y E(x,y) fails in that graph, even if the dataset was intended to represent a complete network. The correct response is to show the node and missing relation, then separately ask whether the data accurately reflect the intended real-world process.

Applied semantics requires an explicit mapping from real records to a logical structure. A computationally cheap answer may be correct for the modeled data and still fail to answer a business or scientific question if the data omit important cases. Classical first-order semantics uses two truth values, nonempty domains and well-defined interpretations. A platform using unknown values, incomplete facts, permissions or time-indexed data needs those deviations modeled, not hand-waved. In research reports, describe the representational contract and distinguish a checked counterexample from absence of evidence.

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. Model checking a fixed first-order sentence on a given finite structure can enumerate assignments, but cost depends on both structure size and formula.

A worked semantic construction

For a graph on n vertices, ∀x∃y E(x,y) is evaluated by inspecting up to n² ordered pairs; any vertex with no outgoing neighbor refutes it. 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 finite-model check certifies only the supplied structure; it does not prove the sentence follows from a theory in all models. 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

Provide asymptotic bounds as upper estimates under a stated evaluation algorithm. 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

Safety-critical property checks need stored models and counterexample traces. 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 8.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: For a graph on n vertices, ∀x∃y E(x,y) is evaluated by inspecting up to n² ordered pairs; any vertex with no outgoing neighbor refutes it. 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 8.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: A finite-model check certifies only the supplied structure; it does not prove the sentence follows from a theory in all models. 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 8.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: Safety-critical property checks need stored models and counterexample traces. Guidance: State the proof obligation as: Provide asymptotic bounds as upper estimates under a stated evaluation algorithm. 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. Select-project-join patterns with Boolean combinations and quantification correspond closely to first-order querying; recursive reachability goes beyond plain first-order logic on arbitrary finite graphs.

A worked semantic construction

The SQL-like condition every employee has a supervisor can be modeled by ∀x(Employee(x)→∃y Supervises(y,x)). Negation needs care with closed-world versus open-world assumptions. 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. SQL NULL and three-valued behavior are not the same as classical two-valued first-order semantics unless explicitly modeled. 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

Translate a query and test it on a tiny structure with both positive and negative cases. 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 integrity auditing benefits from explicit structure semantics and missing-value assumptions. 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 8.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: The SQL-like condition every employee has a supervisor can be modeled by ∀x(Employee(x)→∃y Supervises(y,x)). Negation needs care with closed-world versus open-world assumptions. 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 8.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: SQL NULL and three-valued behavior are not the same as classical two-valued first-order semantics unless explicitly modeled. 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 8.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: Database integrity auditing benefits from explicit structure semantics and missing-value assumptions. Guidance: State the proof obligation as: Translate a query and test it on a tiny structure with both positive and negative cases. 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. An ontology is a formal vocabulary plus axioms; asserted triples alone do not automatically supply unique names, a closed world, or completeness.

A worked semantic construction

From Parent(a,b) and ∀xy(Parent(x,y)→Related(x,y)), Related(a,b) follows. Absence of Parent(b,a) does not entail its negation under open-world semantics. 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. Description logics restrict the language in ways chosen for decidability or scalability; do not treat all ontology languages as unrestricted first-order logic. 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

Publish the entailment regime and the assumptions about identity and incompleteness. 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

Research matching graphs should distinguish unknown evidence from verified negative findings. 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 8.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: From Parent(a,b) and ∀xy(Parent(x,y)→Related(x,y)), Related(a,b) follows. Absence of Parent(b,a) does not entail its negation under open-world semantics. 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 8.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: Description logics restrict the language in ways chosen for decidability or scalability; do not treat all ontology languages as unrestricted first-order logic. 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 8.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: Research matching graphs should distinguish unknown evidence from verified negative findings. Guidance: State the proof obligation as: Publish the entailment regime and the assumptions about identity and incompleteness. 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 bounded model finder enumerates structures up to a specified size and checks a finite collection of formulas, making counterexamples concrete.

A worked semantic construction

Search all directed graphs of size at most 3 for a countermodel to ∀xy(E(x,y)→E(y,x)); a two-node graph with just E(0,1) refutes it. 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. No countermodel within a size bound is not proof that a first-order sentence is valid across all finite and infinite 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

Always report the domain-size bound, vocabulary and solver status. 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

Specification debugging can expose omitted symmetry or transitivity requirements early. 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 8.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: Search all directed graphs of size at most 3 for a countermodel to ∀xy(E(x,y)→E(y,x)); a two-node graph with just E(0,1) refutes it. 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 8.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: No countermodel within a size bound is not proof that a first-order sentence is valid across all finite and infinite 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 8.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: Specification debugging can expose omitted symmetry or transitivity requirements early. Guidance: State the proof obligation as: Always report the domain-size bound, vocabulary and solver status. 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. Classical first-order semantics does not settle every notion of computation or mathematical truth; stronger logics trade expressive power and metatheory.

A worked semantic construction

Full second-order semantics can characterize standard natural-number structures categorically with suitable axioms, while ordinary first-order Peano arithmetic has nonstandard models. 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 comparison depends on full versus Henkin semantics and must not be condensed into the claim that second-order logic is universally superior. 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

End each model-based report by identifying what was proved, what was computed and what remains an assumption. 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

Choose a modeling logic by its semantics, decidability, tooling and evidential needs. 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 8.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: Full second-order semantics can characterize standard natural-number structures categorically with suitable axioms, while ordinary first-order Peano arithmetic has nonstandard models. 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 8.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: This comparison depends on full versus Henkin semantics and must not be condensed into the claim that second-order logic is universally superior. 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 8.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: Choose a modeling logic by its semantics, decidability, tooling and evidential needs. Guidance: State the proof obligation as: End each model-based report by identifying what was proved, what was computed and what remains an assumption. 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: The model-theoretic viewpoint supplies precise guarantees and counterexamples while exposing the limits of finite experimentation. 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.