3.2 Interpretations

Needing interpretations to evaluate formulas

You might have noticed something funny: we said $\mathrm{safe}(a)$ depended on the board, but that $\mathrm{prime}(18)$ was false. Why are some some relations different than others?To add to the puzzling, there was a caveat in some fine-print from the previous section:

$\mathrm{prime}(18)$ is false under the standard interpretation of prime

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 specific 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.

Interpretation

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

Programs are to data, as formulas are to interpretations

Using truth tables to summarize interpretations (optional)

Consider the formula $\varphi =R(x, y)\implies (S(x, y)\land \neg T(x, y))$ . As yet, we haven't said anything about the interpretations of thesethree relations. But, we do know that each of $R(x, y)$ , $S(x, y)$ , and $T(x, y)$ can either be true or false. Thus, treating each of those as a proposition, we can describe the formula'struth under different interpretations.

Using formulas to classify interpretations (optional)

In the previous section , having a formula was rather useless until we had a particularinterpretation for it. But we can view that same idea backwards:Given a formula, what are all the interpretations for which the formula is true?

For instance, consider a formula expressing that an array is sorted ascendingly:For all numbers $i$ , $j$ , $(i< j)\implies (\mathrm{element}(i)\le \mathrm{element}(j))$ .But if we now broaden our mind about what relations/functionsthe symbols $\mathrm{element}$ , , and $\le$ represent and then wonder about the set of all structures/interpretationswhich make this formula true, we might find that our notion of sorting is broader than we first thought.Or equivalently, we might decide that the notion

ascending

Similarly, mathematicians create some formulas about functions being associative, having an identity element, and such,and then look at all structures which have those properties; this is how they define notions such as groups, rings, fields, andalgebras.

Encoding functions as relations

What about adding functions, to our language, in addition to relations? Well, functions are just a way of relating input(s) to an output.For example, 3 and 9 are related by the square function, as are 9 and 81, and 0,0.Is any binary relation a function? No, for instance $\{\left(9,81\right), \left(9,17\right)\}$ is not a function, because there is no unique output related to the input 9.

How can we enforce uniqueness? The following sentence asserts that for each element $x$ of the domain, $R$ associates at most one value with $x$ : For all $x$ , $y$ and $z$ of the domain,