Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: A Finite Model Checker

Write a first-order logic evaluator for finite structures, count models of relation axioms, find countermodels to invalid claims and see why some theories have only infinite models.

Propositional logic has valuations; first-order logic has structures. A structure M = (D, Rโ‚, Rโ‚‚, โ€ฆ) consists of a nonempty domain D and an interpretation for each relation symbol. A sentence is true or false in M. When D is finite, you can evaluate any first-order sentence by brute force: โˆ€x ฯ† becomes "ฯ† holds for every element of D" and โˆƒx ฯ† becomes "for some element". In this project you build such a model checker, then use it as a laboratory: count the models of familiar axioms, hunt for countermodels and meet a theory with no finite model at all.

You will rely on the relation vocabulary from relations and their properties and the equivalence and order axioms from equivalence relations and partial orders.

Step 1: formulas and an evaluator

Represent formulas as tuples: ("R", "x", "y") is an atom, ("eq", "x", "y") is equality, then not, and, or, imp, forall and exists (the latter two carry a variable name). An assignment maps variable names to domain elements. The evaluator is the formal Tarski truth definition, nearly line by line.

Python The evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 2: counting models

How many binary relations on a 3-element set are equivalence relations? On an n-element set you can enumerate all 2^(nยฒ) relations, build the structure and keep those where the axioms hold. You should recover the Bell numbers from the partition lesson: 1, 2, 5 for n = 1, 2, 3. For partial orders the labeled counts are 1, 3, 19.

Python Enumerating structures and counting models

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 3: validity, countermodels and the limits of brute force

A first-order sentence is valid if it is true in every structure, of every size. A finite model checker cannot prove validity, but it can refute a claim by finding a small countermodel. Consider the tempting claim: "every symmetric and transitive relation is reflexive". The "proof" goes: from R(x,y) get R(y,x), then R(x,x) by transitivity. It fails for an element related to nothing. A search finds the smallest counterexample: the empty relation on one element.

Python Searching for countermodels

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second claim, with seriality added (โˆ€x โˆƒy R(x,y)), has no countermodel of any size: it is actually valid. The brute-force search only covers sizes up to 3, so it cannot prove this. A real proof uses the argument from the first paragraph: seriality supplies a y with R(x,y), then symmetry and transitivity give R(x,x).

Step 4: a theory with no finite models

Some theories are satisfiable, but only by infinite structures. Take the axioms: R is irreflexive, transitive and serial (every element has an R-successor). In a finite domain, start anywhere and follow successors: by the pigeonhole principle you eventually revisit an element, and transitivity then gives R(a, a), contradicting irreflexivity. Yet (โ„•, <) satisfies all three. This is a first-order flavor of the infinite-versus-finite contrast from cardinality.

Python No finite model, but an infinite one

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The compactness theorem (see soundness and completeness) also holds for first-order logic. It implies, for example, that no first-order sentence can say "the domain is finite", and that nonstandard models of arithmetic exist.

Extensions

  1. Add function symbols and constants (for example group axioms with * and e), and count groups of order 1 to 4 (1, 1, 1, 2 up to isomorphism).
  2. Remove isomorphic duplicates by canonical relabeling, so that you count unlabeled models.
  3. Parse formulas from text such as forall x. exists y. R(x,y).
  4. Use the SAT solver from the DPLL lesson by encoding "R(i,j)" as variables: this is how Alloy and Mace4 find finite models quickly.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a first-order structure consist of?

    A structure supplies the domain of quantification and the meaning of each relation and function symbol.
  2. 2. How does a finite model checker evaluate โˆ€x ฯ†(x)?

    Over a finite domain, โˆ€ is a big conjunction over all elements and โˆƒ a big disjunction.
  3. 3. What can a countermodel search prove?

    A countermodel refutes validity; failing to find one in small sizes proves nothing.
  4. 4. Which theory has only infinite models?

    In a finite domain, following successors must revisit an element and transitivity then forces R(a, a), contradicting irreflexivity.

Summary

  • A first-order structure is a domain plus interpretations; over a finite domain truth is computed by Tarski's definition with loops for quantifiers.
  • Counting models recovers Bell numbers for equivalence relations and 1, 3, 19 for partial orders.
  • Finite search finds countermodels to invalid claims but cannot prove validity for all sizes.
  • Some theories, such as irreflexive serial transitive relations, have only infinite models.

Next: Practice: Sets, Relations and Logic Problems