Relations on a Set, as MappingsDate: 7/19/96 at 16:41:33 From: Scott Turner Subject: Proof: Relations on a Set I have a 3 parter here and I'm pulling blanks. The book I have has very little on relations and I'm not sure where to go with this. 1. If R, S, and T are relations on a set A, show that (R o S) o T = R o (S o T) where "o" stands for composite. Basically I'm lost here because the only thing I have to go on is the definition of composite. 2. Using (1), prove by induction on n that R o R^n = R^(n+1) 3. Suppose R is symmetric. show that R^n is symmetric for all pos integers n. On this one I got lost from the start. With my base case = 1, how can I say that R is symmetric? Then I assume R^n. Well I've jumped ahead at this point and assumed that R is symmetric (can I assume twice?). Well then (a,b) and (b,a) belong to R and (a, b) and (b,a) belong to R^n. Then applying the the fact that R o R^n = R^(n+1), I get that (a, a) and (b,b) belong to R^(n+1) but this doesn't prove anything. Help. - ST Date: 7/20/96 at 21:12:1 From: Doctor Sydney Subject: Re: Proof: Relations on a Set Doing proofs with relations can be hard at first, but once you begin to get a feel for what a relation is, your intuition will kick in and help you out. Let's first go over what a relation is. A relation R on a set A is a subset of the set A x A. The set A x A is the set of ordered pairs (x,y) such that x and y are both in A. That seems simple, right? Let's look at some examples. Suppose our set A is the following: {1, 2, 3, 4, 5}. An example of a relation R is the following: R = {(1,1), (1,2), (5,4)}. [About notation: people often write xRy to mean that the ordered pair (x,y) is in R, so we might write 1R2 to indicate that (1,2) is in R above.] Let's elaborate on what a relation is by comparing it to a function. If you already feel comfortable with what a relation is, go on to the dotted line; we'll answer your questions there. Let's examine relations in more detail. Relations and functions are intricately related (no pun intended!). Understanding the set theoretic definition of a function will help us understand better what a relation is. Functions are relations with two special properties. A function F on A (defined set theoretically) is a relation such that: 1. For all x in A, there exists a y such that (x,y) is in F. 2. If (x,y) and (x,z) are in F, then y = z. That sounds complicated, but it is just a new way of thinking about functions, which are probably familiar to you. How is this definition of function similar to the one you know? Well, let's look at the definition you know. It says that f is a function if it takes values from its domain and assigns them to unique values in its range. The function will assign to an element of its domain, say x, a value we denote as f(x) in its range, right? So, x and f(x) go together; we might write them (x, f(x)). If we write down all such pairs for all x in the domain, we will have a function in the set theoretic sense! Hence, think of an element of the set called a function as an ordered pair, where the first element in the ordered pair is mapped under the function to the second element in the ordered pair. With this in mind, the above two criteria will make sense. The first says that the function assigns values in the range to ALL values in the domain; not just some. Our function wouldn't be very good if it didn't tell us where it sent all of the values in its domain, now would it? The second criterion requires that each value in the domain be assigned to no more than one value in the range. Okay, enough on functions. After all, your question is about relations! As you can see, a relation is a generalized function. A relation on a set A is the same as a function except we don't need to worry about the two criteria mentioned above. So, a relation on a set A is a set of ordered pairs (x,y) such that x and y are in A. It may help to think of relations in a way similar to the way you think of functions; when (x,y) is in R (or, similarly, when xRy), you can think of R as "mapping" x to y. Of course, since the rules for "mapping" are different for relations, x might be mapped to many different elements of A (this would happen if there were several ordered pairs in R with x as their first element), and not all elements in the "domain" of R are assigned values in the "range." Look back at the example of the relation we discussed earlier. We can think of that relation as "mapping" 1 to both 1 and 2 and also mapping 5 to 4; thus we see that it is all right to map an element to more than one element (1 was mapped to 1 and to 2). In addition, it is not necessary that all elements in A be assigned values in the "range". We can see that 2,3, and 4 are not "mapped" to any elements of A. This is okay for a relation. Relations are more flexible than functions, as you can see! Okay, enough on relations. Now we'll move on to your questions. ------------------------------------------------------------------ First, let's look at the definition of relation composition; it is the analogue of function composition modified for relations. Suppose Q and P are relations on the set A. Then Q o P is the relation defined as follows: (x,y) is an element of the set Q o P if and only if there exists a z in A such that xQz and zPy. How are you to make sense of this? Well, if x is "mapped" to y by Q o P, then decomposing the composition, we see that Q "maps" x to some z in A, and P maps that same z to y. Of course Q might "map" x to other values too - relations can do that. The important thing is that x is mapped to this z, which in turn gets mapped to y. Let's move on to the first problem. Here it is: 1. If R, S, and T are relations on a set A, show that (R o S) o T = R o (S o T) where "o" stands for composite. Basically I'm lost here because the only thing I have to go on is the definition of composite. So, how can we prove that (R o S) o T = R o (S o T)? Well, each side of the equation represents a set, right? So, to prove that two sets are equal, we need to show inclusion on both sides; that is, we need to show that (R o S) o T is a subset of R o (S o T), and then we must also show that R o (S o T) is a subset of (R o S) o T. The only things we know about relations and relation composition are their definitions, right? So that is the only information we will use in the proof. We will use definitions over and over again. Whenever you are stuck on problems like this, try to use your definitions! I'll start you off on this and hope you can figure out the rest on your own. Let's first prove that (R o S) o T is a subset of R o (S o T). When we have done that we will prove the converse. To prove that (R o S) o T is a subset of R o (S o T), we need to take an element of (R o S) o T and show that it also belongs to R o (S o T). Let's suppose that (x,y) is in (R o S) o T. Then, by the definition of composition, we have that there exists a z such that x(R o S)z and zTy, right? We get this by plugging (R o S) in for P and T for Q in the equation above. But if x(R o S)z, then this means that there exists a w such that xRw and wSz. That is again from the definition of relation composition. So, we have learned that there exist a z and a w such that zTy, wSz, and xRw. (*) What were we trying to show? We wanted to show that (x,y) is in the set R o (S o T). What would it mean for (x,y) to be in the set R o (S o T)? Again, go through the definitions in the exact same way we did above. Once you have figured out what it would mean for (x,y) to be in this set, look at what you already know about (x,y) from *. From there, I bet you can finish the proof on your own. Don't forget to prove the inclusion the other way, too! Now let's move on to your second question: 2. Using (1), prove by induction on n that R o R^n = R^(n+1) I'm not going to say much here; I have a feeling you can do this. Carefully write down your base case - it's pretty simple. Your nth case will be R o R^n = R^(n+1). You want to prove that R o R^(n+1) = R^(n+2). How might you use the first equation to get the second? Let me know if you need more help on this one. Now let's move on to three. Below is the question and what you tried to do to solve the problem. 3. Suppose R is symmetric. show that R^n is symmetric for all pos integers n. On this one I got lost from the start. With my base case = 1, how can I say that R is symmetric? Then I assume R^n. Well I've jumped ahead at this point and assumed that R is symmetric (can I assume twice?). Well then (a,b) and (b,a) belong to R and (a, b) and (b,a) belong to R^n. Then applying the the fact that R o R^n = R^(n+1), I get that (a, a) and (b,b) belong to R^(n+1) but this doesn't prove anything. You are off to a promising start; you are right that induction will work best for solving this problem. Before we look at the solution to the problem, let me respond point by point to what you wrote above. First, it is fine to say that R is symmetric because in the statement of the problem, we are told that we are dealing with a symmetric relation. Second, you must be very careful when you use the definition of symmetric relation. Above you state that (a,b) and (b,a) belong to R and that (a,b) and (b,a) belong to R^n. I assume you got that from the definition. However, the definition says something a little different. A relation R is symmetric if for all (x,y) in R, we have that (y,x) is also in R. Now remember that R and R^n are different sets. So, while (a,b) might be in R, it is not necessarily in R^n. Can you find an example of a relation R where an ordered pair is in R but not in the relation R^n for n>1? So, your statement should have read "if (a,b) is in R then so is (b,a); if (c,d) is in R^n so is (d,c)." Thus, your result that (a,a) and (b,b) are in R^(n+1) is fallacious because of the preceding mistake. Okay, now that we have that cleared up, let's attack this problem. We already said that we would do it by induction, so let's take care of our base case first. We are trying to prove that R^n is symmetric for all n if R is symmetric, so the n = 1 case corresponds to R^1 = R. So, we must show that R is symmetric. But R is symmetric by the very assumption of the problem! Whew - that was simple! Let's move on. We assume the nth case holds. Thus, we assume that R^n is symmetric. We now want to show that the (n + 1)st case holds; that is, we want to show that R^(n+1) is symmetric. How do we do that? We use the definition of symmetry. R^(n+1) is symmetric if for all (x,y) in R^(n+1) we have that (y,x) is in R^(n+1) as well. Suppose that (x,y) is in R^(n+1). We will show that (y,x) is in R^(n+1), thus finishing the inductive proof. How can we proceed from this assumption? What do we know about R^(n+1)? We know from number 2 that R^(n+1) = R o (R^n), right? By the definition of composition, we know that if (x,y) is in R o (R^n), there must exist a z in A such that xRz and z(R^n)y. Now what do we do? What do we know about R and R^n? They are symmetric! So, since xRz we must have that zRx. Similarly, because z(R^n)y, we have that y(R^n)z. I bet you can finish the problem from here. Remember that you want to prove (y,x) is in R^(n+1). Use the facts that z(R^n)y and y(R^n)z to show that (y,x) is in R^(n+1). We've already done most of the work! I hope this helps you. Please write to us if you have any more questions about relations or any other math topic. -Doctor Sydney, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/