Lab: Investigating the Closure of Relations

Goal: This project is designed to be a first look at relations, on a finite set. This would be an excellent exploration for a lecture, with interaction by students. Students who have a good feel for properties of relations on finite sets may find it easier to understand these properties in a more general setting (e.g., a relation on an infinite set). We determine how to express a relation in matrix form and find the reflexive, symmetric, and transitive closures of these relations.

A relation on a set S is defined to be some ordered pairs, that is a subset of . If the set is infinite, we have a rule to determine whether an ordered pair belongs to a relation, but when the set S is finite, we can simply list the set of ordered pairs in the relation. For example, we have the relation on the set .

  1. First, create a directed graph to represent this relation, and this can be done with Peter Schofield’s Network Graphs file in DERIVE. For your convenience, this graph is in the answer file Relations.dfw.
  2. Now look and the graph and identify what the concepts symmetric, reflexive, and transitive mean as visualized in a graph. The first two concepts need to be true for ALL elements of S, whereas the idea of a relation being transitive is more elusive to students, as there is a logical implication within the definition. The students can see that there is a quick visual check of reflexive and symmetric properties on a graph, but that transitive requires much more work.
  3. Let’s create a matrix associated with the graph. The matrix consists of zeroes and ones, and so is called a Zero-One matrix. This is a slight variation on the adjacency matrix associated with a directed graph, with an entryequal to 1 if the pair is in the relation (or a directed edge from vertex i to j), and 0 if not. This requires an ordering of rows and columns, and it is usual to follow the natural ordering on S. So our matrix would be:

(recall that 1 is an element of S and an isolated vertex in the associated graph).

  1. Now let’s examine the matrix M of the relation. Some discussion questions for the class: Why is the matrix necessarily square? If the relation is reflexive, what would you find in the matrix? How about symmetric? Hey, what is the definition of a symmetric matrix and is that relevant to this discussion? Can you tell if the relation is transitive from a matrix?
  2. Since it is difficult to determine whether a relation is transitive from either a matrix or a graph, it is natural to discuss the closure of a property on a relation. That is, expanding the set of ordered pairs to include only those additional pairs necessary for the relation to have the given property.
  3. What pairs would we add to our relation to make it reflexive? How is this found in a matrix? Here we need not a SUM of matrices, but rather an OR operator. This is sometimes referred to as the Boolean OR of zero-one matrices. The new relation is called the reflexive closure of the original relation.
  4. Returning to our original relation, what pairs would we add to make it a symmetric relation? How is this found in a matrix? We need the OR operator again to form the symmetric closure of the relation.
  5. The discussion of how to track the pairs in a relation in order to find the transitive closure is not so clear, and your discussion with students will reflect their level of understanding. Thinking in terms of the graph of the relation, the powers of the matrix of the relation will track the number of paths connecting one element of set S to another, but we only care if there is at least one such path. So we need the Boolean product of the matrix of the relation with itself. That is, you compute a regular product, but substitute OR for + and AND for x.
  6. Now, back to DERIVE. In the file Relations.dfw, there are seven lines of stack to create the Boolean OR operator, Boolean product of matrices, and Boolean powers of a matrix. Thanks to Terence Etchells, LiverpoolJohnMooresUniversity, for helping Lisa create these operators. Also in the file is the adjacency matrix of our relation above. From this matrix, predict, and then compute the reflexive and symmetric closures of the relation via the matrix and the functions refl_cl(#1) and symmetric_cl(#1), where #1 is the line number of your particular matrix. The simplifications should match your prediction.
  7. Nearly done! Now try to find the transitive closure of your original relation. First try to work this through from the ordered pairs, or your graph, to predict the result. Then compute some Boolean powers of the matrix using the function Power(#1, n), where #1 again is the correct line number of your matrix and n is a power of your choosing. You have to compute powers until there is no change in the matrix entries, in order to verify that you have included all transitive results.
  8. Build a relation of your own choosing on the set S and find the reflexive, symmetric, and transitive closures.
  1. Finally, how can we use this to help students make the transition to relations that are described verbally or symbolically? We suggest you try to describe such a relation on a finite set and use the student understanding of ordered pairs to help him/her build a verbal/symbolic proof. As an example, consider the following data set below. We define a relation on the set of names {L, J, M, C, T} as: the name A is related to name B if the people are the same height. Then we can build the ordered pairs in the relation, determine that it is in fact an equivalence relation, and try to prove that the relation is reflexive, symmetric, and transitive, using the verbal description instead. You could also try this with a relation that is not an equivalence, so as to also examine the closure.

Name / Height (inches)
Lisa / 68
Jon / 70
Manu / 64
Jas / 70
Tom / 70

The Boolean OR and product from DERIVE:

#1 sum(x, y) ≔ x + y - x·y

#2 add(v) ≔ FIRST(ITERATE([sum(s, sum(FIRST(v_), FIRST(REST(v_)))), REST(v_)], [s, v_], [0, v], DIM(v) - 1))

#3 BProd(A, B, inner, outer) ≔

Prog

If DIM(A↓1) ≠ DIM(B COL 1)

RETURN " Cols of A must = rows of B"

inner ≔ DIM(A)

outer ≔ DIM(B↓1)

B ≔ B`

VECTOR(VECTOR(add(mult(A↓r, B↓s)), s, 1, outer), r, 1, inner)

#4 Power(u, n) ≔ ITERATE(BProd(v, u), v, u, n - 1)

#5 symmetric_cl(u) ≔ VECTOR(VECTOR(sum(), s, 1, DIM(u)), r, 1, DIM(u))

#6 refl_cl(u) ≔ VECTOR(VECTOR(sum(, (IDENTITY_MATRIX(DIM(u))), s, 1, DIM(u)), r, 1, DIM(u))