You are here

Needing Interpretations to Evaluate Formulas

16 June, 2015 - 14:38
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

You might have noticed something funny: we said safe (a) depended on the board, but that prime (18) was false. Why are some some relations different than others? To add to the puzzling, there was a caveat in some fne-print from the previous section: " prime (18) is false under the standard interpretation of prime ". Why these weasel-words? Everybody knows what prime is, don't they? Well, if our domain is matrices of integers (instead of just integers), we might suddenly want a different idea "prime".

Consider the formula E (x, x) true for all x in a domain? Well, it depends not only on the domain, but also on the specifc binary relation E actually stands for:

  • for the domain of integers where E is interpreted as "both are even numbers", E (x, x) is false for some x.
  • for the domain {2, 4, 6, 8} where E is interpreted as "sum to an even number", E (x, x) is true for every x.
  • for the domain of integers where E is interpreted as "greater than", E(x, x) is false for some x (indeed, it's false for every x).
  • for the domain of people where E is interpreted as "is at least as tall as", E (x, x) is true for every x.

Thus a formula's truth depends on the interpretation of the (syntactic, meaning-free) relation symbols in the formula.

Definition 3.1: Interpretation

The interpretation of a formula is a domain, together with a mapping from the formula's relation symbols to specific relations on the domain.

One analogy is “Programs are to data, as formulas are to interpretations ". (In particular, the formula is a like a boolean function: it takes its input (interpretation), and returns true or false.)