Symmetric, Transitive, and Reflexive RelationsDate: 11/10/98 at 11:30:27 From: Mike Subject: Discrete math Suppose R is a symmetric and transitive relation on A. Suppose that for each a in A there is b in A such that (a,b) and is in R. Show: R is an equivalence relation. Suppose R is a reflexive and transitive relation on A. Define a new relation, T = { (a,b) | both (a,b) and (b,a) are in R}. Show: T is an equivalance relation. Suppose R is a reflexive relation on A. Show: R is an equivalence relation <==> [ (a,b) and (a,c) in R ==> (b,c) in R] Let Z = {positive integers}. Define A = ZxZ. Define a relation, R, on A by: R = { ((a,b), (c,d)) | a*d = b*c}. Prove that R is an equivalence relation on A. Date: 11/16/98 at 19:39:59 From: Doctor Teeple Subject: Re: Discrete math Hi Mike, Before we get to these proofs, let's review the ideas of relations and equivalence relations. That way, we'll have definitions to refer to when we try the proofs. Suppose we have a set A and a relation R on A. Then R is just a set of ordered pairs that are made up from the elements of A. For example, if A = {1, 2, 3}, we can define a relation R = {(1,2), (2,3), (3,1), (3,2)}. Note that this is only one relation we could define on A. There are plenty of other ones. To show that a relation R is an equivalence relation, we need to prove that it has three properties. We need to show that it is reflexive, symmetric, and transitive. It helps to have the exact definitions written down, so go ahead and do that now. Here's what I have: reflexive: For every element a in A, (a,a) is in R. symmetric: If an ordered pair (a,b) in R, (b,a) is in R. transitive: If ordered pairs (a,b) and (b,c) in R, (a,c) in is R. All three of these must hold to have an equivalence relation. We can check the relation we defined above to see whether it is an equivalence relation. First check reflexivity. Recall R = {(1,2), (2,3), (3,1), (3,2)}. For R to be reflexive it must contain (1,1), (2,2), and (3,3). Since R doesn't even contain (1,1), it is not reflexive. Here is an equivalence relation R2 on A: R2 = {(1,1), (1,3), (2,2), (3,1), (3,3)}. Do a quick mental check to see that all three properties hold. Okay, now we're ready to start the proofs. Sorry for the detour, but it helps to have the definitions in front of you. For the first one, we are already given that R is a symmetric and transitive relation on A. So we only need to check that R is reflexive, which means that for each a in A, (a,a) is in R. Look at the next line given in the problem: "Suppose that for each a in A there is b in A such that (a,b) and is in R." This is very similar to the definition for reflexivity. We know that for each a in A, (a,b) is in R. But we need to show that (a,a) is in R. We also have some other information we can use. Remember that we know R is symmetric and transitive. Use the definition of symmetric and the fact we know that (a,b) is in R. In the next step we reason that because R is symmetric, and we know that for each a in A, (a,b) is in R, we know that for each a in A, (b,a) is in R, but that doesn't get us the fact that (a,a) is in R. However, we also know that R is transitive. Try finishing the proof using the facts that R is transitive and for each a in A, (a,b) and (b,a) are in R. Once you have finished the first proof, the second two are very similar. For both you need to show just one more of the three properties required. Look at the definitions of the property in question and then look at what you're given about the relation that you need to prove is an equivalence relation. The last proof is a little tricky because the elements of A that you make your ordered pairs from are actually themselves ordered pairs, so we may want to alter the definitions above to make it easier to see what we need to prove. Try rewriting them with ordered pairs. For instance, instead of using "a" to represent an arbitrary element of A, we could call (a,b) an arbitrary element of A. Please write back if you need clarification of any of this or if you need more help in figuring out the rest of the proofs. If the definitions are giving you trouble, do lots of examples. That will help you get a better feel for relations and equivalence relations. And keep referring back to the definitions. They'll help in the proofs. Good luck! - Doctor Teeple, The Math Forum http://mathforum.org/dr.math/ Date: 10/08/2002 at 21:24:05 From: Chris Subject: Possible error The answer given by Dr. Math implied that it was possible to prove that ~ was an equivalence relation. I'm not completely sure, but I think that I have seen this problem before in a textbook. The textbook gave the proof and asked why it was false. It then stated: If ~ is symmetric and transitive, then we can not conclude that ~ is reflexive. Here is the argument: Call this argument: PROOF1 We know that a~b => b~a We know that a~b and b~c => a~c Suppose a~b Then b~a by symmetry. So a~b and b~a. Then a~a by transitivity. Thus, ~ is an equivalence relation. Here is an counterexample: Suppose a>a and a>a. Then a~a. But a cannot be greater than a. This is a contradiction. So, a is not related to a. Thus, ~ is not reflexive. It is easy to show that ~ is symmetric and transitive. So...this counterexample shows that symmetry and transitivity do not imply reflexivity. I think that the problem with PROOF1 is that it relies on a~b. "If a~b, then a~a" We can write this as "a~b only if a~a" Looking at a truth table... If P, then Q P Q P=>Q ----------- F F T F T T T F F <-- We can ignore this line since P=>Q was proven true. T T T It is easy to see that P is true only if Q is true. But notice that Q can be true or false. F F => T F T => T For ~ to be an equivalence relation, Q must be true. PROOF1 does not guarantee that Q is true. It merely says that Q is true when a~b. I hope I did not make a mistake in my logic, Chris Date: 10/09/2002 at 01:46:27 From: Doctor Mike Subject: Re: Possible error Hi Chris, You are right that symmetry and transitivity are not enough to prove reflexivity. But that isn't what Dr. Math was claiming to be able to do. There was an extra assumption that each item "a" is related to something. That extra assumption, in addition to symmetry and transitivity, allows proof of reflexivity. Your example's definition says that a is related to b means a<b and also b>a. This can never happen, so you have described what could be called the "empty relation." Nothing is related to anything else. It is symmetric because whenever a is related to b (which NEVER happens) then b is related to a. Similar to the transitivity property; it also is in the "if ... then" form, so when the if part is not true, the whole expression is true. Perhaps you have seen made up sentences like this. "If X is a real number and X squared is negative, then I'm a monkey's uncle." This is a true sentence even though I'm not a monkey's uncle, because the first part is false. You referred to truth tables so you are probably familiar with these ideas. I hope this helps this helps you see what Dr. Math was getting at. - Doctor Mike, The Math Forum 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/