Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Intro to Logic » interpretations

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Recently Viewed

This feature requires Javascript to be enabled.
 

interpretations

Module by: Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, Matthias Felleisen. E-mail the authors

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

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 ϕ=RxySxy¬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)(elementielementj) 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,

RxyRxz(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,

SwxySwxz(y=z) S w x y S w x z y z
(2)

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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