Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » Relations and Logic: properties of relations

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 module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collection: "Intro to Logic"

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

Recently Viewed

This feature requires Javascript to be enabled.
 

Relations and Logic: properties of relations

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

Summary: Relations are subsets. Binary relations might be reflexive, symmetric, antisymmetric, or transitive.

When using relations in logic formulas, there are two things going on:

  • relations themselves, as mathematical entities, and
  • formulas involving symbols, which must be interpreted as specific relations.
First things first: we'll just discuss relations for now, and later tackle using relations in logic formulas.

We'll start with a couple of equivalent ways of defining relations, and then discuss a common subclass of relations: binary relations.

Relations as subsets

Consider the set of WaterWorld locations Loc=ABZ Loc A B Z . For this domain (also known as a universe), we'll say a binary relation is a set of (ordered) pairs of the domain.

Example 1

For instance, the nhbrnhbr relation of the previous section is the set A BA GB AB CY XY ZZ Y A B A G B A B C Y X Y Z Z Y .

That is, xx is related to yy if x yx y is in the set nhbrnhbr.

Example 2

For the domain D=ObjectStringMutableString D Object String MutableString , the relation subclass-ofsubclass-of might be String Object MutableString Object MutableString String String Object MutableString Object MutableString String .

In general, a binary relation over the domain DD is a subset of D×D D D . Note that these are ordered pairs; just because xx is related to yy doesn't mean yy has the same relation to xx. For example, while MutableString Object MutableString Object is in the relation subclass-ofsubclass-of, the pair Object MutableString Object MutableString most certainly is not.

Example 3

You can consider the relation hasStarredWithhasStarredWith, over the domain of Hollywood actors. We won't list all the elements of the relation, but some related pairs are:

  • hasStarredWithEwan McGregorCameron Diaz hasStarredWith Ewan McGregor Cameron Diaz , as witnessed by the movie A Life Less Ordinary, 1997.
  • hasStarredWithCameron DiazJohn CusackhasStarredWith Cameron Diaz John Cusack , as witnessed by the movie Being John Malkovich, 1999.

If binary relations are subsets of pairs of the domain, what might a unary relation be? Simply, subsets of the domain.

Example 4

For the domain of vegetables, Ian defines the relation yummy?yummy? as tomatoesokracucumberscarrotspotatoes tomatoes okra cucumbers carrots potatoes and nothing else.

Example 5

In one particular game of WaterWorld, the relation hasPiratehasPirate turned out to be KTRUE K T R U E .

If unary and binary relations make sense, what about ternary, etc., relations? Sure! In general, a kk-ary relation (or, “relation of arity kk) over the domain DD is a subset of Dk D k . However, any given relation has a fixed arity. That is, a relation may be binary or ternary, but not both.

As with propositions, rather than writing RxyRx y is true ”, we'll simply write RxyRx y. In fact, notice that once you choose some particular pair of xx and yy, then RxyRx y can be treated as a single true/false proposition. (We'll soon extend the idea of propositions to include such relation symbols, and then allow formulas to include these terms.)

Example 6

prime18prime18 is a proposition that's false, assuming the standard interpretation of primeprime.

Example 7

safeAsafe A is a proposition that is true on some boards and not others.

Relations as functions

The relation nhbrnhbr, which we're defining as a set (of pairs), could also be thought of being a function. We say that the indicator function of a set is a Boolean function indicating whether its input is in the set or not. So instead of being given the set nhbrnhbr, you would have been equally happy with its indicator function fnhbrfnhbr, where (for example) fnhbrBC=true fnhbr B C and fnhbrBQ=false fnhbr B Q . Similarly, if you know that fhasPirateK=true fhasPirate K and that fhasPirateL=false fhasPirate L , then this is enough information to conclude that KhasPirate K hasPirate and LhasPirate L hasPirate . The set and the function are equivalent ways of modeling the same underlying relation.

The next two exercises aren't meant to be difficult, but rather to illustrate that, while we've sketched these two approaches and suggested they are equivalent, we still need an exact definition.

Exercise 1

For the indicator function fxy={true  if  y=x2false  otherwise   f x y y x 2 on the domain of (pairs of) natural numbers, write down the set-of-pairs representation for the corresponding binary relation. It's insightful to give the answer both by listing the elements, possibly with ellipses, and also by using set-builder notation.

In general, for a binary indicator function ff, what, exactly, is the corresponding set?

Solution

00112439i i2 00 11 24 39 i i2 In set-builder notation, this is xy y=x2 xy y x2

In general, for an indicator function ff, the corresponding set would be xy fxy xy f xy (Note that we don't need to write “ … fxy=true f xy ; as computer scientists comfortable with Booleans as values, we see this is redundant.)

Exercise 2

For the relation hasPirate=KTRUE hasPirate K T R U E on the set of (individual) WaterWorld locations, write down the indicator-function representation for the corresponding unary relation. In general, how would you write down this translation?

Solution

fhasPiratex={true  if  x=Ktrue  if  x=Ttrue  if  x=Rtrue  if  x=Utrue  if  x=Efalse  otherwise   f hasPirate x x K x T x R x U x E .

In general, for a (unary) relation RR, fRx={true  if  xRfalse  if  xR f R x x R x R .

Since these two formulations of a relation, sets and indicator functions, are so close, we'll often switch between them (a very slight abuse of terminology).

Think about when you write a program that uses the abstract data type Set. Its main operation is elementOf. When might you use an explicit enumeration to encode a set, and when an indicator function? Which would you use for the set of WaterWorld locations? Which for the set of prime numbers?

Functions as Relations

Some binary relations have a special property: each element of the domain occurs as the first item in exactly one tuple. For example, isPlanet=Earth trueVenus trueSol falseCeres falseMars true isPlanet Earth Venus Sol Ceres Mars is actually a (unary) function. On the other hand, isTheSquareOf=0 01 11 -14 24 -29 39 -3 isTheSquareOf 0 0 1 1 1 -1 4 2 4 -2 9 3 9 -3 is not a function, for two reasons. First, some numbers occur as the first element of multiple pairs. Second, some numbers, like 33, occurs as the first element of no pairs.

We can generalize this to relations of higher arity, also. This is explored in this exercise and this one.

Binary Relations

One subclass of relations are common enough to merit some special discussion: binary relations. These are relations on pairs, like nhbrnhbr.

Binary Relation Notation

Although we introduced relations with prefix notation, e.g., <ij< i j, we'll use the more common infix notation, i<j i j, for well-known arithmetic binary relations.

Binary Relations as Graphs

In fact, binary relations are common enough that sometimes people use some entirely new vocabulary: A domain with a binary relation can be called vertices with edges between them. Together this is known as a graph. We won't stress these terms right now, as we're not studying graph theory.

Binary relations (graphs) can be depicted visually, by drawing the domain elements (vertices) as dots, and drawing arrows (edges) between related elements.

A binary relation with a whole website devoted to it is “has starred in a movie with”. We'll call this relation hasStarredWithhasStarredWith over the domain of actors. Some sample points in this relation:

  • hasStarredWithEwan McGregorCameron Diaz hasStarredWith Ewan McGregor Cameron Diaz , as witnessed by the movie A Life Less Ordinary, 1997.
  • hasStarredWithCameron DiazJohn Cusack hasStarredWith Cameron Diaz John Cusack , as witnessed by the movie Being John Malkovich, 1999.
You can think of each actor being a “location”, and two actors being “adjacent” to each other if they have ever starred in a movie together; two of these locations, even if not adjacent might have a multi-step path between them. (There is also a shorter path; can you think of it? The (in)famous Kevin Bacon game asks to find a shortest path from one location to the location Kevin Bacon. Make a guess, as to the longest shortest path leading from (some obscure) location to Kevin Bacon.)

Some other graphs:

  • Vertices can be tasks, with edges meaning dependencies of what must be done first.
  • In parallel processing, Vertices can be lines of code; there is an edge between two lines if they involve common variables. Finding subsets of vertices with no lines between them represent sets of instructions that can be executed in parallel (and thus assigned to different processors.)
  • “Word ladders” seek to transform one word to another by changing one letter at a time, while always remaining a word. For example, a ladder leading from WHITE to SPINE in three steps is:
    • WHITE
    • WHINE
    • SHINE
    • SPINE
    If a solution to such a puzzle corresponds to a path, what do vertices represent? What are edges? Do you think there is a path from any 5-letter word to another?

Content actions

Download module as:

Add 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