Definability and expressive limits

Learning objective. A formula singles out a relation inside a structure, but different structures and signatures support different definable sets. Running application. A graph analytics team wants to express reachability without accidentally importing an algorithm as a new predicate.

The third unit studies descriptions relative to the pure order (Q,<) and several tiny graphs. Rational points do not become individually definable merely because mathematicians can name one by writing a numeral in English. By contrast, in a language expanded with a constant naming a point, formulas may isolate that point and define intervals around it.

Definability asks what the language is capable of distinguishing internally. An externally describable set may fail to be defined by any formula in a chosen signature. Adding named parameters or predicates may change the answer dramatically. Good semantic analysis therefore records the vocabulary and the permitted parameters before proposing a formula. For counterexamples, look for a symmetry preserving every named relation but moving a supposedly unique object. An automorphism cannot break the truth of a parameter-free formula, so such a symmetry can refute an ambitious definability claim.

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. A set X⊆Dⁿ is definable if some formula φ(x₁,…,xₙ) picks out exactly its tuples in the structure.

A worked semantic construction

In (Z,<), the relation x≤y is definable as x

Counterexample discipline and boundary conditions

Frequent mistake. Definability always depends on a background structure; a relation being computable does not prove that it is first-order definable. 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

Supply the formula and prove both inclusion directions for its intended relation. 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 schemas can implement views corresponding to particular formulas. 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 3.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: In (Z,<), the relation x≤y is definable as x

Exercise 3.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: Definability always depends on a background structure; a relation being computable does not prove that it is first-order definable. 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 3.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: Formal schemas can implement views corresponding to particular formulas. Guidance: State the proof obligation as: Supply the formula and prove both inclusion directions for its intended relation. 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. Allowing domain elements as parameters enlarges what can be defined; parameter-free definability is more restrictive.

A worked semantic construction

In (Q,<), the interval (a,b) is definable by a

Counterexample discipline and boundary conditions

Frequent mistake. Naming a value as a parameter is not the same as proving it can be identified from structure alone. 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

List all parameters explicitly, especially in automorphism arguments. 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

Search filters with supplied endpoints should not be mistaken for intrinsic data classifications. 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 3.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: In (Q,<), the interval (a,b) is definable by a

Exercise 3.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: Naming a value as a parameter is not the same as proving it can be identified from structure alone. 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 3.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: Search filters with supplied endpoints should not be mistaken for intrinsic data classifications. Guidance: State the proof obligation as: List all parameters explicitly, especially in automorphism arguments. 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. Quantifier rank measures maximum nesting depth of quantifiers, and bounded rank provides a resource-sensitive comparison of structures.

A worked semantic construction

For φ=∀x(P(x)→∃y E(x,y)), the quantifier rank is 2; a flat conjunction of two rank-1 formulas still has rank 1. 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. Formula length and quantifier rank are different measures, and bounded-rank tests do not settle elementary equivalence for all formulas. 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

Compute rank recursively: atoms 0, connectives max, quantifiers 1 plus the inner rank. 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

Query optimizer design can use bounded fragments while labeling their completeness limits. 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 3.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: For φ=∀x(P(x)→∃y E(x,y)), the quantifier rank is 2; a flat conjunction of two rank-1 formulas still has rank 1. 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 3.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: Formula length and quantifier rank are different measures, and bounded-rank tests do not settle elementary equivalence for all formulas. 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 3.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: Query optimizer design can use bounded fragments while labeling their completeness limits. Guidance: State the proof obligation as: Compute rank recursively: atoms 0, connectives max, quantifiers 1 plus the inner rank. 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. Every parameter-free definable set is invariant under all automorphisms of the structure.

A worked semantic construction

In (Q,<), order automorphisms can move any chosen rational to any other. Therefore a formula without parameters cannot define the singleton {0} in this structure. 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. Automorphism invariance is a necessary condition; in arbitrary structures it is not a sufficient test of first-order definability. 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

Find one automorphism moving a proposed definable set to refute parameter-free definability. 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

Identity-agnostic graph features should remain invariant under node renaming. 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 3.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: In (Q,<), order automorphisms can move any chosen rational to any other. Therefore a formula without parameters cannot define the singleton {0} in this structure. 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 3.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: Automorphism invariance is a necessary condition; in arbitrary structures it is not a sufficient test of first-order definability. 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 3.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: Identity-agnostic graph features should remain invariant under node renaming. Guidance: State the proof obligation as: Find one automorphism moving a proposed definable set to refute parameter-free definability. 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 interpretation can represent one structure inside another via definable domains, relations, and sometimes a definable equivalence relation for quotienting.

A worked semantic construction

A structure with a definable equivalence relation E may code quotient objects as E-classes; translating a target equality requires E rather than raw element identity. 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 mere arbitrary coding is not automatically a first-order interpretation; the decoding relations must be definable. 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

Check that each target symbol has a defining formula and that the quotient operations are well-defined. 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

Knowledge representation languages sometimes compress many logical objects into one universe with tags. 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 3.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: A structure with a definable equivalence relation E may code quotient objects as E-classes; translating a target equality requires E rather than raw element identity. 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 3.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: A mere arbitrary coding is not automatically a first-order interpretation; the decoding relations must be definable. 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 3.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: Knowledge representation languages sometimes compress many logical objects into one universe with tags. Guidance: State the proof obligation as: Check that each target symbol has a defining formula and that the quotient operations are well-defined. 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: A formula singles out a relation inside a structure, but different structures and signatures support different definable sets. 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.