<< Chapter < Page
  Intro to logic   Page 1 / 1
Chapter >> Page >
Interpretations map relation-symbols to an actual relation.

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 relationson 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 S x y 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.

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 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 element i element j .But if we now broaden our mind about what relations/functionsthe symbols element , < , and 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
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, 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 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 y z
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 tostart to model a binary function. In particular, write a formula stating thatfor 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

Got questions? Get instant answers now!

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Intro to logic. OpenStax CNX. Jan 29, 2008 Download for free at http://cnx.org/content/col10154/1.20
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Intro to logic' conversation and receive update notifications?

Ask