Math Homewok needed for VFLORIDA

Closures of Relations Composition of Relations Revisited Recall in the text the matrix of the relation S R is written as MS R and MS R = MR MS. The purpose of the following example is to remind you of the process and to reaffirm why it is necessary to write the product of the matrices “backwards”. Example 1. Assume that a University has a tutoring center and would like to determine which subjects are available to be tutored which days of the week. Assume that the courses to be tutored are: A = {Discrete(D), Precaculus(P),C++, Calculus(Cal)}. Assume that there are three tutors available B = {John(J), Melissa(M), Al(A)}. Also assume that the days that the tutoring center is open are Monday through Friday, that is C = {M, T, W, R, F}. Assume that: John can tutor Discrete , C++ and Calculus and he is available on M,R and F. Melissa can tutor Precaculus and C++ and she is available on M, W and R. Al can tutor Discrete , Precalculus and Calculus and he is available on T, W and F. If R is the relation from A(courses) to B(tutors) and S is the relation from B to C(days). We want to find S R, which course are available to be tutored on which days of the week. The easiest was of doing this is to use matrices.

Let MR = . Recall, to write this matrix prefix the first column by the elements

of A and the first row by the elements of B. You may want to do this.

1 0 1 0 1 1 1 1 0 1 0 1

⎡ ⎤ ⎢ ⎥ ⎢ ⎢ ⎢ ⎥ ⎣ ⎦

⎥ ⎥

⎥ ⎥

⎥ ⎥

Let MS = . Recall, to write this matrix prefix the first column by the

elements of B and the first row by the elements of C. You may want to do this.

1 0 0 1 1 1 0 1 1 0 0 1 1 0 1

⎡ ⎤ ⎢ ⎢ ⎢ ⎥⎣ ⎦

So that MS R = MR MS = . The reader should prefix the first column

by the elements of A and the first row by the elements of C to determine which courses are available for tutoring which days of the week.

1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1

⎡ ⎤ ⎢ ⎥ ⎢ ⎢ ⎢ ⎥ ⎣ ⎦

Another interesting result comes from using regular arithmetic instead of Boolean arithmetic on the above product (MRMS).

1

MS R = MRMS = . This tells us, for example, that there are 2 tutors

available to tutor Calculus on Friday. Determine how many tutors are available to tutor the courses on which days.

1 1 1 1 2 1 1 2 1 1 2 0 1 2 1 1 1 1 1 2

⎡ ⎤ ⎢ ⎥ ⎢ ⎢ ⎢ ⎥ ⎣ ⎦

⎥ ⎥

Closure Operations on Relations In the text for section 8.4 read the first several pages to have an overview of closures in general and the concentrate transitive closure which begins on page 547. Example 7 is a good example to study in detail. The material below explains what transitive closure means. One important operation on relations is composition. This operation enabled us to generate new relations from previously known relations. We now wish to consider the situation of constructing a new relation R* from a previously known relation R where, first, R*contains R and, second, R*satisfies the transitive property. Consider a telephone network in which the main office a is connected to, and can communicate to, individuals b and c. Both b and c can communicate to another person, d; however, assume the main office cannot communicate with d. Assume communication is only one way, as indicated by the following relation. This situation can be described by the relation R = {(a, b), (a, c), (b, d), (c, d)}. We would like to change the system so that the main office a can communicate with person d and still maintain the previous system. We, of course, want the most economical system. This can be rephrased as follows: Find the smallest relation R* which contains R as a subset and which is transitive. Since R* must contain R as a subset R* must include the pairs (a, b), (a, c), (b, d), (c, d) therefore so far R* looks like R*= {(a, b), (a, c), (b, d),(c, d), …}. Next, since both (a, b) and (b, d) are elements of R* and R* must be transitive R*must contain (a, d) and we have R*= {(a, b), (a, c), (b, d),(c, d), (a, d)}. The reader should check to see if any other pairs have to be included to make it transitive. The answer is no. Definition: Transitive Closure. Let A be a set and R be a relation on A. The transitive closure of R, denoted by R*, is the smallest relation that contains R as a subset and that is transitive. Example 2. Let A = {1, 2, 3, 4}, and let S = {(l, 2), (2, 3), (3, 4)} be a relation on A. This relation is called the successor relation on A since each element is related to its successor. How do we compute S*? By inspection we note that (1, 3) must be in S*. Let's analyze why. This is so since (1, 2) ∈ S and (2, 3) ∈ S, and the transitive property forces (1,3) to be in S*. In general, it follows that if (a, b) ∈ S and (b, c)∈ S, then (a, c) ∈ S*. This condition is exactly the membership requirement for the pair (a, c) to be in the composition S S = S2. So every element in S2 must be

2

an element in S*. So far, S* contains at least S ∪ S2. In particular, for this example, since S = {(l, 2), (2, 3), (3, 4)} and S2 = {(l, 3), (2, 4)}, we have S S∪ 2 = {(l, 2), (2, 3), (3, 4), (1, 3), (2, 4)}. Is the relation S ∪ S2 transitive? Again, by inspection, (1, 4) is not an element of S S∪ 2, but it must be an element of S* since (1, 3) and (3, 4) are in S*. From above, (1, 3) ∈S2 and (3, 4) ∈ S, and the composite S2 S = S produces (1, 4). This shows that S S3 3 ⊆ *. This process must be continued until the resulting relation is transitive. If A is finite, as is true in this example, the transitive closure will be obtained in a finite number of steps. Here, S* = S ∪ S S 3 . 2 ∪ Note if you determined S4 or S5 or S6 etc. you would simply get S3. Theorem If S is a relation on a set A and if #A = n, then the transitive closure S* = S S S .... . ∪ 2 ∪ 3 nS∪ Note in the above example |A| = 4 but the transitive closure was obtained by computing S3. So in the above theorem you need only go as far “as at most n”. Let's now consider the matrix analogue of the transitive closure through an example. This will give us Theorem 3 of the text. Example 3. Consider the relation R ={(l, 4), (2, 1), (2, 2), (2, 3), (3, 2), (4, 3), (4, 5), (5, I)} on the set A={1, 2, 3, 4, 5}, note |A| = 5. The matrix MR of R is

MR =

0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

and sine R R can be computed by the matrix MR R = MRMR and since MRMR is the product of a matrix with itself MRMR = . 2RM

2 RM =

0 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

3 RM =

1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

3

4 RM =

1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

5 RM =

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

So R* = R R∪ 2 ∪ R3 ∪ R4 R∪ 5 because |A| = 5. This equation can be expressed in matrix form as:

MR* = MR ∨ 2RM ∨ 3 RM ∨

4 RM ∨

5 RM =

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

.

Equivalence Relations For this topic read the definition and examples 1 through 3 and then try the exercises.

4