correlation

Week 11 An Introduction to the Concept of Relations Think of your family tree. It consists of your brothers, sisters, cousins, second cousins, aunts, uncles, parents, grandparents, great grandparents etc. On this set of relatives there is defined a relation (ship), that is, person a appears above person b in your family tree if and only if person a is an ancestor of person b. Think of an ancestor, say your great grandmother, and picture your family tree diagram with her listed at the top of the page and all her descendants listed below. This is an example of a “mathematical” diagram or graph called a tree or a partial ordering diagram. The ordering is called partial because, for example, you and your siblings and your cousins are all on the same level. Note there is a direction in this graph, namely from the top down so this is a directed graph. Another mental image. Think of the administrative structure of a business, from the CEO at the top to the next layer of VP’s to the Managers etc. Again, this is a partial ordering under the relation; person appears above person b if and only if person a is the boss of person b. Note there is a direction in this graph, namely from the top down so this is a directed graph. A third image. Think of all the major field courses you need to take for your degree. Certainly some of them are prerequisites of others. Draw a”tree”; here it might be more readable to draw the tree from the bottom to the top. That is, course x appears below course y in this list of courses tree if and only if course x is a prerequisite of course y. Each of the above are graphs or models of different situations. But, on reflection we can visualize similarities in the graphs of these diverse situations. In the next several sections we would like to learn how to describe the above and other situations mathematically. One of the key notations we will use in the next several weeks is that of the Cartesian product of two sets. Let’s recall the definition of this concept before we proceed. Definition: Let A and B be any two sets the Cartesian product of A and B, denoted A X B (read as A cross B), is the set of all ordered pairs (a, b) where a takes on all elements from the set a and b takes on all elements from the set B. In notation:  A X B = (a,b) a A , b B  Some comments:

1. If A = {1, 2} and B = {a, b, c} then A X B = {(1, a), (2,a), (1, b), 2, b), (1, c), 2, c)} and |A X B | = |A| x |B| = 2×3 = 6

2. In general, if |A| = n and |B| = m the |A X B| = nm 3. R X R is the “algebraic” description of the xy-plane, and R X R is also

written as R2 which is read as R two. Of course Before you begin to read the following, think again about the concepts of functions and that of graphs of functions. Let’s recall some basic facts about functions.

 

 

A. Doerr

2

1. In high school we first learned how to manipulate linear equations algebraically. Next, we learned through an example, like y = 2x + 3, what this meant and then how to graph this function.

2. Next, you probably learned the “functional notation”, for example f(x) = 2x + 3. 3. A third notation for the same function you learned in an earlier part of this course,

namely, define f: R  R by the formula f(x) = 2x + 3. In this notation concepts like, domain, codomain, composition and the precise definition of a function were discussed.

4. We could talk about this very same function the following way. A function, f from R to R is the subset of the xy- plane, that is of R x R where f = {(x,y)| x R and y = 2x + 3}. Here the focus is that f is a set of ordered pairs of real numbers (x, y) with certain restrictions. What are they?

So discussions about the function f(x) = 2x + 3 centered about how to describe it algebraically and then how to graph it. In discrete graph theory our discussions parallel that of the above (let’s call the above continuous graph theory). We will define the analogue of the definition of a function namely that of a relation, then graph it. The resulting graph is called a directed graph of the relation. Precise definitions, examples and illustrations follow in the notes below and in the text. Compare the definition of relation given below to item 4 above. Is every function (from A to B) a relation (from A to B)? YES. Is every relation (from A to B) a function (from A to B)? NO A Procedure for studying the sections on relations from the text

1. In section 9.1 of the text, study examples 1 through 6. Temporarily skip properties of relations in section 1. Study this when you cover partial ordering relations in section 6.

2. Skip section 9.2 of the text. Study section 9.3 of the text, representing relations

using digraphs through example 9. At this point you should be able to write the relation as a set of ordered pairs of each of the graphs in exercises 23 through 28 of section 9.3. This is also covered in section 6.2 of the notes “Graphs of relation” which begins on page 8 below. Here are a couple of examples which are in the text:

Example 1. I will describe the graph given in exercise 24, section 9.3 on representing relations, as a set of ordered pairs. Keep in mind I must give you 2 things a set A, and the relation, R which acts on A. Looking at the graph in exercise 24 we see that the set A is the set {a, b, c}. Next we have to define relation R on A (Note, that is R is a subset of A x A, that is, R is a relation from A to A). So here is the description. Define R on A by R = {(a, a), (b, b), (c, c), (b, a), (a, c), (b, c)}. Note, there is a directed edge, an “arrow” for each ordered pair, since there are 6 directed edges in the graph there should be 6

 

 

A. Doerr

3

ordered pairs. Can you represent this relation by a 3 by 3 yes/no matrix? You should be able to do so after you study section 3. Example 2. Describe exercise 27, of section 9.3 of the text as a set of ordered pairs. I first note there are 9 directed edges so I should list 9 ordered pairs. Let A = {a, b, c, d}. Define the relation R on A by R = {(a, a),(b, b),(d, d),(a, b),(b, a),(a, c),(c, a),(b, c),(c, b)}. Can you write the yes/no matrix of R? See section 3.

3. There are 3 key properties listed in section 9.1 of the text. The properties are: reflexive, antisymmetric and transitive. Study these definitions. The definitions of these terms are also given in section 6.3 of the notes page 11. The reason for theses definitions is to introduce a special type of relation called a partial ordering relation. When a relation is a partial ordering relation we can draw a much cleaner version of its graph called a partially ordered graph or a Hasse graph. This topic is covered in the text in section 3 week 13 but you may wish to study it now through the notes in section 6.3, page 11 below.

4. Next go to section 3 of the text, Representing Relations Using Matrices. The

parallel section in the notes is section 6.4. You might find this helpful. The remark given in the notes, Section 6.4, after Theorem 6.4.1 on page 17 gives a convenient, and much faster way of determining the yes/no matrix of a relation. I will write the (yes/no) matrix of example 1 above using this method.

Example 3. Write the yes/no or Boolean matrix of the relation given in example 1. First from the notes we realize that there is a 1 (a true) for each ordered pair (or directed edge) in the relation R. Since R contains 6 ordered pairs there are 6 1’s in the matrix. We will use the texts notation for the matrix of R, namely MR. Since the domain and the codomain are the same set A = {a, b, c} we will prefix both the rows and the columns of MR by the elements in A in the order listed, namely a, b, c. For ease in typing I will first

write the matrix in table form as

a b c

a 1 0 1

b 1 1 1

c 0 0 1

 

so MR =

1 0 1

1 1 1

0 0 1

        

 

For more practice of matrices of relations read the following:

Examples:

1. Let A = {1, 2, 3} and let B = {x, y} and let S be the relation from A to B defined by S = {(1, x), (2,x), (2,y), (3, y)} Then the (yes/no)matrix of S is called MS where MS is a 3 by 2 matrix. To easily find this matrix first list a 3 x 2 matrix

 

 

A. Doerr

4

_ _

_ _

_ _

         . Next write the domain of S, namely A, as a additional column before this matrix and write the codomain of S, namely B as a additional row above this matrix. Now your matrix looks like this

1 _ _

2 _ _

3 _ _

x y

         . Next, since the pair (1,x) belong to the relation indicate a “yes” or 1 in the row 1 and

column x of the matrix. Since the pair (1, y) does not belong to the given relation indicate a no or 0 in column 1, row y. Since there are four pairs in the given relation there are four 1’s in the matrix. So your matrix looks like

1 1 0

2 1 1

3 0 1

x y

         . The additional column and row were just used for assistance so MS =

1 0

1 1

0 1

        

.

2. Let A ={a,b,c,d} and let R = {(a, a) (b, b), ( c, c), (a, b), (b, c), (d, a), (d, b)} be a relation on A

(i.e. from A to A). First we observe that the domain and the codomain are the same set , namely A. The (yes/no) matrix of R is 4 x 4 matrix because both the domain, A, and the codomain, A, each contain 4 elements. This matrix has seven 1’s in it because the relation has 7 pairs. So MR is

1 1 0 0

0 1 1 0

0 0 1 0

1 1 0 0

a b c d

a

b

c

d

             . Often this matrix is simply written as

 

1 1 0 0

0 1 1 0

0 0 1 0

1 1 0 0

             .

3. Note, given the matrix in example you should be able to work “backwards” to find the relation,

That is, if A ={a, b, c, d} and if the matrix of R is MR =

1 1 0 0

0 1 1 0

0 0 1 0

1 1 0 0

           

. What is R?

Example 4. Describe the relation, S on the set A = {1, 2, 3, 4} whose yes/no matrix is

MS =

1 0 1 0

0 1 0 1

1 0 0 1

0 0 1 1