eduKateSG · Mathematical Logic · Worked learning guide
Find the reasoning step you need
Build one complete interpretation that breaks an inference, then learn why searching small models without finding a failure does not prove unrestricted validity.
1. State precisely what a countermodel must do
3. Work a two-object relation countermodel
5. Use a truth table where the language permits it
7. See an inference that fails only in an infinite model
9. Practise by verifying every part of a model
Full chapter index · Practice and checking · Mathematical Logic subject guide
One correct countermodel can defeat a proposed deductive inference. Many successful examples cannot automatically establish it. The difference is about what the claim requires: validity concerns every permitted interpretation.
This guide explains countermodel construction through original relation tables, named-object examples and a function on the natural numbers. It also shows a particularly useful limit: an inference can hold in every finite interpretation of the relevant kind and still fail in an infinite one.
The setting is classical first-order logic with identity and nonempty domains. Use Mathematical Logic for the wider distinction between truth, consequence and proof. Here the focus is a practical method for finding and checking failures.
Chapter index
Chapters 1–4
Chapters 5–8
Chapters 9–10
An argument is logically valid when every permitted interpretation that makes all its premises true also makes its conclusion true. A countermodel is one permitted interpretation where all premises are true and the conclusion is false.
Those requirements are conjunctive. A model where the conclusion is false but a premise is also false does not refute the argument. The argument only promises to preserve truth when its premises hold.
Likewise, a model where every sentence is true is a successful example, but it does not show the absence of a different failing interpretation.
Begin with an original argument
Premise 1: every blue token is round. Premise 2: token a is round. Conclusion: token a is blue.
Let B mean blue and R mean round. The formulas are ∀x(B(x) → R(x)), R(a), and therefore B(a). A countermodel needs a round nonblue object named a while keeping every blue object round.
A one-object domain can do this. Let D = {u}, assign a to u, let R = {u}, and let B = ∅. The universal premise is true, the roundness premise is true and the conclusion is false.
That complete interpretation is enough to establish invalidity. It need not describe an actual token collection. Logical validity is a claim across the allowed interpretations, so a possible interpretation satisfying the stated language and conditions can refute it.
The constructive habit is to write the required truth pattern first: all premises true, conclusion false. This gives the model-building task a target and prevents random example generation.
A first-order interpretation needs a domain and meanings for its nonlogical vocabulary. Unary predicates become subsets of the domain. Binary predicates become sets of ordered pairs. Constant symbols receive domain objects. Function symbols receive appropriate total functions in the standard semantics used here.
For a finite countermodel, list every object and give complete predicate extensions. If R is binary on {u,v}, there are four possible ordered pairs: (u,u), (u,v), (v,u), and (v,v). State which are true; the others are false.
A diagram can help, but it should not leave the self-pairs ambiguous. An arrow from u to v does not tell a reader whether u relates to itself unless the diagram’s convention is explicit.
Names need assignments
If the language contains a and b, say what each denotes. Different names need not denote different objects. A model may assign both names to u.
If a premise says a ≠ b, then a one-object domain cannot satisfy that premise. The domain must provide at least two distinct objects and assign the names accordingly.
Identity is interpreted as genuine identity of objects. It is not another arbitrary binary relation that can be chosen independently. A model in which u = v is true for two distinct domain objects violates the standard identity semantics.
The point of completeness is reproducibility. Another reader should be able to evaluate every premise and the conclusion without guessing missing entries or relying on the story’s tone.
A countermodel is a small mathematical object. Its explanatory story helps the reader remember it, while its domain and interpretation provide the actual verification.
Consider the proposed inference from ∀x∃y R(x,y) to ∃y∀x R(x,y). The premise says every row of the relation has a true entry. The conclusion says one column has true entries throughout.
Let D = {u,v}, with R = {(u,u),(v,v)}. All other pairs are false.
| R(x,y) | y = u | y = v |
|---|---|---|
| x = u | True | False |
| x = v | False | True |
For x = u, choose y = u. For x = v, choose y = v. Thus the premise is true.
For the conclusion, try y = u: row v makes R(v,u) false. Try y = v: row u makes R(u,v) false. Neither candidate works for every x, so the conclusion is false.
Check the smallest domain
Could a one-object model refute this inference? If D = {u} and the premise is true, R(u,u) must be true. Then the same u supplies a column that works for every object. The conclusion is true.
Therefore this inference has no one-object countermodel but does have a two-object countermodel. Failing to find a countermodel at size one would have been insufficient.
This is a useful demonstration of bounded search. A search limited to one object can be complete for that bound and still miss an invalid inference. The search report must state the bound.
The table also explains the invalidity in ordinary language: separate witnesses need not combine into a shared witness. The model does not merely return a verdict; it identifies which additional uniformity the conclusion demands.
A proposed countermodel may look promising until one premise excludes it. Suppose an inference includes ∀x(A(x) → B(x)) and ∃x A(x), with conclusion ∃x B(x).
An empty A-category cannot refute it because the existence premise would be false. A valid countermodel would need an A-object, make every A-object a B-object, and yet have no B-object. Those requirements cannot all be met.
An informal proof explains why: take a witness to A from the second premise. The universal first premise makes that witness B, so the conclusion follows.
Extra structural assumptions matter
If a binary relation is declared symmetric, each true pair (u,v) must be accompanied by (v,u). If it is transitive, any true R(u,v) and R(v,w) require R(u,w). A relation table that breaks these premises is not a permitted countermodel.
Do not assume symmetry or transitivity merely because a relation has a familiar-sounding name. They must follow from the stipulated meaning or be included among the premises defining the class of interpretations.
Likewise, arithmetic examples may be intended over the standard integers, while unrestricted logical validity allows many interpretations of nonlogical symbols. Decide whether the task is consequence from explicit arithmetic assumptions, truth in a fixed structure, or validity across arbitrary structures.
The repair is to make a premise checklist. For each candidate interpretation, evaluate every premise before celebrating a false conclusion. A single failed premise disqualifies the candidate, even if the story feels like a convincing objection.
This is a respectful way to assess disagreement too: identify whether an objection rejects a premise or exposes an invalid inference. Both can matter, but they are different criticisms.
For a propositional argument, a truth table can exhaust all valuations of its finitely many sentence letters. With n letters, there are 2ⁿ valuations. A row with all premises true and conclusion false is a countervaluation.
For example, p → q and q do not entail p. The valuation p = false and q = true makes both premises true and the conclusion false.
Checking every valuation can establish propositional validity because the finite table exhausts that language’s relevant valuations. That is different from testing a few selected first-order domains.
Why the distinction matters
A quantified formula can express relationships among arbitrarily many objects. A single propositional letter standing for that whole sentence hides its internal structure. Propositional abstraction may lose the relationships needed for a first-order inference.
For instance, “Every A is B” and “some A exists” together imply “some B exists.” Treating those three sentences as unrelated propositional letters would not capture their shared predicates and quantifier structure.
A truth table remains useful for the truth-functional skeleton of a formula, but it does not automatically evaluate quantifiers over a domain. A first-order interpretation supplies that additional structure.
The right method depends on the formal language. State whether the search enumerates propositional valuations, all relations on a fixed finite domain, or selected models from a larger class.
A complete search in one setting is valuable evidence within that setting. It becomes misleading only when its scope is silently enlarged. Precise labels let the reader understand both the strength of the result and the remaining question.
For a fixed labelled domain of n objects and one binary predicate R, there are n² ordered pairs. Each pair can be true or false independently when no structural premises restrict it. Thus there are 2^(n²) possible interpretations of R on that domain.
At n = 2, there are 16 relation tables. At n = 3, there are 512. At n = 4, there are 65,536. Adding predicates, constants and functions changes the search space.
A program can enumerate these finite possibilities and evaluate a formula in each. If a countermodel is found, inspect the returned domain, extensions and assignments. If none is found, the result establishes only the absence of a countermodel within the completed search space.
A search result needs a completion claim
“No countermodel found” can mean an exhaustive search finished without one, or that a search stopped after a timeout, or that a heuristic inspected only some candidates. These outcomes are different.
A reproducible report states the maximum domain size, vocabulary, restrictions, whether all relevant interpretations were examined, and whether the search terminated normally.
Even exhaustive searches at many finite sizes do not automatically establish validity over all domains. Some failures require larger finite models; others require infinite models.
For the original two-object diagonal relation, a complete one-object search misses the failure while a two-object search finds it. The next chapter develops a stronger example: no finite countermodel exists at any size, but an infinite countermodel does.
This is a reason to combine model search with proof and theory, rather than treating search failure as a universal certificate. The method is useful precisely when its output is interpreted within its actual guarantee.
Let f be a total function from the domain to itself. Consider this premise: f is injective, meaning ∀x∀y(f(x) = f(y) → x = y). Proposed conclusion: f is surjective, meaning ∀y∃x(f(x) = y).
On a finite domain, every injective self-map is surjective. If the domain has n objects, injectivity gives n distinct outputs, and there are only n domain objects available as outputs. Every object must appear.
Thus no finite interpretation of a total self-function can make the premise true and the conclusion false. Exhaustive finite searches, however large, will find no countermodel to this argument.
Now choose domain ℕ = {0,1,2,…} and interpret f(n) = n + 1. This is a total function from ℕ to ℕ. It is injective: if x + 1 = y + 1, then x = y.
It is not surjective, because 0 has no preimage in ℕ. For every natural x, x + 1 is at least 1, so f(x) ≠ 0. The premise is true and the conclusion false. This is an infinite countermodel.
What the example establishes
The unrestricted first-order inference is invalid. The inference restricted to finite domains is valid. These statements do not conflict because they quantify over different classes of interpretations.
The function’s totality matters. Standard first-order function symbols already denote total functions. If a software table represents a partial function, it is a different object and needs different conditions.
The natural numbers’ starting point also matters. On the integers, n ↦ n + 1 is surjective because y has preimage y − 1. Changing the domain changes the model.
The complete countermodel therefore includes the domain and function rule, followed by separate checks of injectivity and the missing output. The familiar formula n + 1 alone is insufficient.
When a small-model search finds nothing, inspect the formula’s demands before increasing the bound. Does a premise require distinct objects, a chain, an injective function or a relation with a particular structure? Such conditions can suggest why small models fail.
Then decide whether to seek a proof, a larger model or an infinite construction. A proof must establish the claim for the full intended class, while a countermodel needs only one permitted failure.
For the injective-function example, the finite counting argument explains why more finite search cannot help. The natural-number construction supplies the appropriate next direction.
Keep the verdict proportional to the work
A useful report might say: “No countermodel exists on domains of sizes one through four under the completed enumeration. Unrestricted validity has not been established.” That is a positive, precise result.
If a proof is available, state the assumptions under which it works. A finite-domain proof should not be presented as a proof over arbitrary domains. If a model is found, verify it independently against each premise rather than relying only on a tool’s label.
A classroom correction can preserve the student’s successful examples. Explain that they show the claim works in those cases, then ask what the universal conclusion still requires. The examples were useful exploration; the overreach happened in the final inference.
The learning aim is judgment about evidence. A learner should know when one example is decisive, when exhaustive finite checking is decisive, and when a broader proof or construction is needed.
Exercise 1: a converse mistake
Premises: ∀x(P(x) → Q(x)) and Q(a). Conclusion: P(a). Construct a one-object countermodel.
Let D = {u}, a denote u, P = ∅ and Q = {u}. The universal and Q(a) are true; P(a) is false.
Exercise 2: distinct names
Premises: P(a) and P(b). Conclusion: at least two distinct objects have P. Construct a countermodel.
Use D = {u}, assign both a and b to u, and let P = {u}. The premises hold, but there is only one qualifying object. Adding a ≠ b would exclude this model.
Exercise 3: a quantifier shift
Use D = {u,v} and R = {(u,u),(v,v)}. Verify ∀x∃y R(x,y) and refute ∃y∀x R(x,y). State a witness for each row and a failing row for each column.
Exercise 4: finite versus infinite functions
Explain why f(n) = n + 1 on ℕ refutes “injective implies surjective,” while the same rule on the integers does not. On ℕ, 0 has no preimage. On the integers, y − 1 is a preimage for every y.
Transfer check
For any proposed argument, list its vocabulary, domain restrictions and required truth pattern. Build a candidate interpretation, evaluate every premise, then evaluate the conclusion. Finally state whether the result concerns one model, a bounded search, all finite models or every permitted model.
A complete answer is a verified interpretation and a correctly scoped verdict. A diagram, a tool output or a persuasive story becomes decisive only after those conditions are checked.
Frequently asked questions
Does a false conclusion refute an argument? Only if every premise is true in the same permitted interpretation.
Can one countermodel prove invalidity? Yes. Validity allows no true-premise, false-conclusion case.
Does checking all small models prove validity? It proves the bounded claim actually checked. Unrestricted first-order validity needs a broader justification.
Can an argument hold in every finite model but fail in an infinite one? Yes. An injective total self-map must be surjective on finite domains, while successor on ℕ supplies an infinite failure.
Connected reading
Use Mathematical Logic for proof, semantics and limits. Logic develops argument assessment, while Discrete Mathematics develops finite relations and counting.
Sources and scope
Interpretation-based argument testing was checked against forall x: Calgary, Reasoning about Interpretations. Domain, identity and total-function conventions follow the Open Logic Project syntax and semantics reference. Accessed 22 October 2026. The countermodels, search-space counts and finite-versus-infinite function argument are explicitly developed here as original teaching examples. No particular theorem prover or model-search implementation is certified by this guide.
Contents · Previous chapter · Continue to Mathematical Logic
Connected Mathematical Logic guides
Quantifier order and dependent choices