Relations and Logic: properties of relations

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 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. For instance, the nhbr relation of the previous section is the set A B A G B A B C … Y X Y Z Z Y . That is, x is related to y if x y is in the set nhbr. For the domain D Object String MutableString , the relation subclass-of might be String Object MutableString Object MutableString String . In general, a binary relation over the domain D is a subset of D D . Note that these are ordered pairs; just because x is related to y doesn't mean y has the same relation to x. For example, while MutableString Object is in the relation subclass-of, the pair Object MutableString most certainly is not. You can consider the relation hasStarredWith, over the domain of Hollywood actors. We won't list all the elements of the relation, but some related pairs are: hasStarredWith Ewan McGregor Cameron Diaz , as witnessed by the movie A Life Less Ordinary, 1997. hasStarredWith 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. For the domain of vegetables, Ian defines the relation yummy? as tomatoes okra cucumbers carrots potatoes and nothing else. In one particular game of WaterWorld, the relation hasPirate turned out to be K T R U E . If unary and binary relations make sense, what about ternary, etc., relations? Sure! In general, a k-ary relation (or, relation of arity k) over the domain D is a subset of 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 Rx y is true , we'll simply write Rx y . In fact, notice that once you choose some particular pair of x and y, then Rx 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.) prime18 is a proposition that's false, assuming the standard interpretation of prime. safe A is a proposition that is true on some boards and not others.

Relations as functions The relation nhbr, 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 nhbr, you would have been equally happy with its indicator function fnhbr, where (for example) fnhbr B C and fnhbr B Q . Similarly, if you know that fhasPirate K and that fhasPirate L , then this is enough information to conclude that K hasPirate and 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. For the indicator function 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 f, what, exactly, is the corresponding set? 00 11 24 39 … i i2 … In set-builder notation, this is xy y x2 In general, for an indicator function f, the corresponding set would be xy f xy (Note that we don't need to write … f xy ; as computer scientists comfortable with Booleans as values, we see this is redundant.) For the relation 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? f hasPirate x x K x T x R x U x E . In general, for a (unary) relation R, 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 Venus Sol Ceres Mars is actually a (unary) function. On the other hand, 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 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 nhbr.

Binary Relation Notation Although we introduced relations with prefix notation, e.g., < i j, 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. We'll call this relation hasStarredWith over the domain of actors. Some sample points in this relation: hasStarredWith Ewan McGregor Cameron Diaz , as witnessed by the movie A Life Less Ordinary, 1997. 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?