Skip to content Skip to navigation

Connexions

You are here: Home » Content » Relations and Logic: interpretations

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

      What are tags? tag icon

      Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

    • External bookmarks
  • E-mail the authors
  • Rate this module (How does the rating system work?)

    Rating system

    Ratings

    Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

    How to rate a module

    Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

    		(0 ratings)

Recently Viewed

This feature requires Javascript to be enabled.

Relations and Logic: interpretations

Module by: Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, Matthias Felleisen

Summary: Interpretations map relation-symbols to an actual relation.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Needing Interpretations to Evaluate Formulas

You might have noticed something funny: we said safea safe a depended on the board, but that prime18 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: “ prime18 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 ExxE x x true for all xx in a domain? Well, it depends not only on the domain, but also on the specific binary relation EE actually stands for:

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

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

Definition 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.)

Using Truth Tables to Summarize Interpretations (Optional)

Consider the formula ϕ=Rxy⇒Sxy∧¬Txy ϕ 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 RxyRx y, SxySx y, and TxyTx 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.

Table 1
Rxy R x y Sxy S x y Rxy R x y ϕ
false false false true
false false true true
false true false true
false true true true
true false false false
true false true false
true true false true
true true true false

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 ii,jj, i<j⇒elementi≤elementj i j elementi elementj . But if we now broaden our mind about what relations/functions the symbols elementelement, <<, 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 819 17 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 xx of the domain, RR associates at most one value with xx: For all xx, yy and zz of the domain,

Rxy∧Rxz⇒y=z R x y R x z yz (1)
This is a common trick, for to describe uniqueness: if yy and zz 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.)

Exercise 1

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 ww, xx in the domain, the relation SS associates at most one value with that pair.

Solution

For all ww, xx, yy, and zz of the domain,

Swxy∧Swxz⇒y=z S w x y S w x z y z (2)

Comments, questions, feedback, criticisms?

Send feedback