Relations and Logic: interpretations

Needing Interpretations to Evaluate Formulas 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 fine-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 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 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 or .)

Using Truth Tables to Summarize Interpretations (Optional) Consider the formula ϕ R x y Sx y T x y . As yet, we haven't said anything about the interpretations of these three relations. But, we do know that each of Rx y, Sx y, and Tx y can either be true or false. Thus, treating each of those as a proposition, we can describe the formula's truth under different interpretations. R x y S x y R x y ϕ

Using Formulas to Classify Interpretations (Optional) In the previous section, having a formula was rather useless until we had a particular interpretation 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 elementi elementj . But if we now broaden our mind about what relations/functions the symbols element, <, and ≤ represent and then wonder about the set of all structures/interpretations which 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 applies to more structures than we first suspected. 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, and algebras.

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 9 81 9 17 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, R x y R x z yz This is a common trick, for to describe uniqueness: if y and z each have some property, then they must be equal. (We have not yet specified that for every element of the domain, there is at least one element associated with it; we'll get to that later.) We just used a binary relation to model a unary function. Carry on this idea, by using a ternary relation to start to model a binary function. In particular, write a formula stating that for every pair of elements w, x in the domain, the relation S associates at most one value with that pair. For all w, x, y, and z of the domain, S w x y S w x z y z