Predicate Logic · step 5 of 13

Validity & counter-models

A formula of predicate logic is valid if it is true in every structure — every choice of domain and interpretation of the predicates. Refuting validity is concrete work: you supply one structure where it fails. Almost every refutable exam formula fails in a domain of one or two elements, so a counter-model is usually a two-line table, not an essay.

Practise validity & counter-models free → All Predicate Logic subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Choose a tiny domainStart with D = {1} and then D = {1, 2}. Most invalid formulas break at size 2, and small models are easy to check exhaustively.
Interpret each predicate as a setSay exactly which elements satisfy P, and which pairs satisfy R. A table of the relation is the clearest presentation.
Evaluate the formula in your structureWork outward, checking each quantifier against every element of the domain. Show this evaluation — it carries the marks.
If no counter-model exists, argue generallyTake an arbitrary structure, assume the premises hold, and derive the conclusion using the meaning of the quantifiers.

Worked example

Is ∃x P(x) ∧ ∃x Q(x) → ∃x (P(x) ∧ Q(x)) valid?

Take D = {1, 2}.
Interpret P as {1} and Q as {2}.
Then ∃x P(x) is true (witness 1) and ∃x Q(x) is true (witness 2), so the antecedent holds.
No element is in both P and Q, so ∃x (P(x) ∧ Q(x)) is false and the implication is false.

Answer. Invalid. Counter-model: D = {1, 2}, P = {1}, Q = {2}. The two existentials may be witnessed by different elements.

Where marks get dropped

These are the specific errors that cost credit on validity & counter-models questions — QED's rubric penalises each of them separately.

Giving a counter-model without specifying the domain. The interpretation is meaningless without it.
Trying only one-element domains. Formulas about relations and quantifier order typically need two elements to fail.
Confusing "false in some structure" with "false" — a formula can be satisfiable and invalid at the same time, and the question asks which.

Practise this until it is automatic

Unlimited fresh questions

QED generates new validity & counter-models problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Predicate Logic mastery is tracked so you know when this is exam-ready.

Validity & counter-models — frequently asked questions

How small can a counter-model be?

Often one or two elements. If a first-order formula has any model it has a countable one (Löwenheim–Skolem), and for exam formulas the finite witnesses are tiny.

Is validity decidable in predicate logic?

No. First-order validity is only semi-decidable — you can enumerate proofs of the valid formulas, but there is no algorithm that always halts on the invalid ones (Church–Turing).

Do I need to check every predicate interpretation?

Only for a proof of validity, where you argue about an arbitrary structure. To refute, one specific interpretation is enough.

The rest of Predicate Logic

Quantifiers, predicates, binding, and validity. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make validity & counter-models exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →