Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 37 ยท Predicate Logic

Models, Interpretations and Truth in First-Order Logic

Understand structures, interpretations and satisfaction in first-order logic, write a finite model checker in Python, and see why validity cannot be checked by finite search.

In propositional logic, a formula gets a truth value from an assignment of true/false to variables. In first-order logic there is more to fix: what the objects are, what the predicate symbols mean, what the function symbols do. A bundle of all that information is called a structure or interpretation, and a structure in which a sentence is true is a model of it. This lesson makes "truth" in predicate logic precise and builds a model checker for finite structures.

Signature: the vocabulary

A signature lists the non-logical symbols we may use:

  • constants (0, alice),
  • function symbols with an arity (+ with 2 arguments, succ with 1),
  • predicate (relation) symbols with an arity (<, Parent).

Symbols have no meaning by themselves. R could be "less than" or "is a friend of".

Structures

A structure M for a signature supplies:

  1. a nonempty domain (universe) D,
  2. an element of D for each constant,
  3. a function Dโฟ โ†’ D for each n-ary function symbol,
  4. a relation (a subset of Dโฟ) for each n-ary predicate symbol.

Example: the signature has one binary predicate E. A graph is exactly a structure for it: the domain is the vertex set and E the edge relation. A sentence like โˆ€x โˆƒy E(x, y) then says "every vertex has an outgoing edge".

Satisfaction

Truth is defined by recursion on the formula, relative to a structure M and a variable assignment s (a map from variables to domain elements):

  • M, s โŠจ R(tโ‚,โ€ฆ,tโ‚™) iff the tuple of the terms' values is in R.
  • ยฌ, โˆง, โˆจ, โ†’: as in propositional logic.
  • M, s โŠจ โˆ€x ฯ† iff M, s[xโ†ฆd] โŠจ ฯ† for every d โˆˆ D.
  • M, s โŠจ โˆƒx ฯ† iff M, s[xโ†ฆd] โŠจ ฯ† for some d โˆˆ D.

A sentence (no free variables) does not depend on s, so we simply say it is true or false in M.

Python A finite model checker

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 same sentence is true in one structure and false in another. That is the heart of semantics: truth is relative to a model.

Validity, satisfiability, entailment

  • A sentence is satisfiable if it has at least one model.
  • It is valid if it is true in every structure (the analogue of a tautology). Example: โˆ€x P(x) โ†’ โˆƒx P(x), which is valid because domains are nonempty.
  • ฮ“ โŠจ ฯ† (entailment) means every model of all sentences in ฮ“ is a model of ฯ†.
  • Two sentences are logically equivalent if they have the same models.

Unlike propositional logic, validity here cannot be checked by enumeration: there are infinitely many structures, some with infinite domains. Church and Turing showed in 1936 that no algorithm decides validity of first-order sentences in general (the logic is undecidable, though semi-decidable: valid sentences can be proved by a complete proof system, see chapter 7).

Finite models find counterexamples

What we can do is search small structures. If a finite structure makes premises true and a conclusion false, we have a counterexample, proving the entailment invalid. The next program searches every relation on a small domain.

Python Counterexample search over all small structures

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 search finds a two-element structure {0, 1} with R = {(0, 1), (1, 0)}: everything relates to something, yet nothing is related to by everything. This confirms what we argued in the previous lesson, now by machine search.

Equality and arithmetic structures

Standard structures to know:

Structure Domain Symbols Typical sentence
(โ„•, 0, S, +, ร—, <) Natural numbers arithmetic โˆ€x โˆƒy (y > x)
(โ„ค, +, 0) Integers a group โˆ€x โˆƒy (x + y = 0)
(โ„š, <) Rationals dense order โˆ€x โˆ€y (x < y โ†’ โˆƒz (x < z โˆง z < y))
A graph (V, E) Vertices one relation โˆ€x ยฌE(x, x)

The sentence โˆ€x โˆ€y (x < y โ†’ โˆƒz (x < z โˆง z < y)) is true in (โ„š, <) but false in (โ„ค, <): between 1 and 2 there is no integer. Elementary equivalence, two structures satisfying the same sentences, is a central idea of model theory.

Python Density holds in โ„š-like samples but not in โ„ค

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.

(A finite sample of โ„š cannot witness density by itself; the midpoint argument works for every pair of rationals, which is exactly the universal proof that examples cannot give.)

Common mistakes

  • Treating a sentence as true or false without naming the structure.
  • Allowing an empty domain; standard first-order semantics requires nonempty domains.
  • Confusing a free variable's dependence on the assignment with a sentence's truth.
  • Believing a finite check proves validity; it only finds counterexamples.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A structure for a signature consists of...

    A structure interprets every non-logical symbol over a domain.
  2. 2. A first-order sentence is valid when...

    Validity means truth in all structures, the first-order analogue of a tautology.
  3. 3. What can a finite model search establish?

    A finite counterexample refutes an entailment, but a failed search proves nothing about infinite structures.
  4. 4. Is 'between any two elements there is a third' true in (โ„ค, <)?

    Density fails in the integers but holds in the rationals.

Summary

  • A structure gives a domain and meanings for all symbols; a model of a sentence makes it true.
  • Satisfaction is defined recursively; โˆ€ and โˆƒ range over the domain.
  • Valid means true in all structures; satisfiable means true in some.
  • First-order validity is undecidable, but finite models can refute entailments.
  • Truth is always relative to a structure.

Next: Translating English into Logic