3.1 Properties of relations  (Page 2/2)

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

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 itemin exactly one tuple. For example, $\mathrm{isPlanet}=\{\left(\mathrm{Earth},\mbox{true}\right), \left(\mathrm{Venus},\mbox{true}\right), \left(\mathrm{Sol},\mbox{false}\right), \left(\mathrm{Ceres},\mbox{false}\right), \left(\mathrm{Mars},\mbox{true}\right)\}$ is actually a (unary) function. On the other hand, $\mathrm{isTheSquareOf}=\{\left(0,0\right), \left(1,1\right), \left(1,-1\right), \left(4,2\right), \left(4,-2\right), \left(9,3\right), \left(9,-3\right), \text{…}\}$ is not a function, for two reasons. First, some numbers occur as the first element of multiple pairs. Second, some numbers, like $3$ , 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 $\mathrm{nhbr}$ .

Binary relation notation

Although we introduced relations with prefix notation, e.g., , we'll use the more common infix notation, $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

• $\mathrm{hasStarredWith}(\mathrm{Ewan\; McGregor}, \mathrm{Cameron\; Diaz})$ , as witnessed by the movie A Life Less Ordinary , 1997.
• $\mathrm{hasStarredWith}(\mathrm{Cameron\; Diaz}, \mathrm{John\; Cusack})$ , as witnessed by the movie Being John Malkovich , 1999.

location

adjacent

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 beexecuted 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?