Proving an Equivalence RelationDate: 01/31/2003 at 23:47:14 From: Shelley Subject: Discrete Math Let R1 and R2 (1 and 2 are subscripts; notation will continue as such) be equivalence relations on sets S1 and S2, respectively. Define a relation R on S1 X S2 (Cartesian Product) by letting (x1, x2)R(y1, y2) mean that x1R1y1 and x2R2y2. PROVE that R is an equivalence relation on S1 X S2, and describe the equivalence classes of R. How can I describe the elements of R, and show them to be transitive, symmetric, and reflexive, when I don't really even know the elements of R1 and R2? How can I represent this situation clearly? Usually I am told WHAT the relation IS (such as R means x + y or something). In this problem the question is vague; I don't know anything about the numbers (real or integer or...), and I don't know anything about the relations R1 or R2 or R. Is the "Cartesian product" I mention the same as your discussion of "composites" of sets in Relations on a Set, as Mappings http://mathforum.org/library/drmath/view/51847.html Date: 02/01/2003 at 09:04:36 From: Doctor Jacques Subject: Re: Discrete Math Hi Shelley, Let us first write down explicitly what we want to prove. We want to prove that: ------ 1. R is reflexive, i.e. zRz for every z in S1 x S2. This means that, for every x_1 in S1 and x_2 in S2, we have: (x_1,x_2) R (x_1,x_2) 2. R is symmetric. This means that, for every x_1, y_1 in S1 and x_2, y_2 in S2 we have: (x_1,x_2) R (y_1,y_2) --> (y_1,y_2) R (x_1,x_2) 3. R is transitive. This means that, for every x_1, y_1, z_1 in S1 and x_2, y_2, z_2 in S2, we have (x_1,x_2) R (y_1,y_2) AND (y_1,y_2) R (z_1,z_2) --> (x_1,x_2) R (z_1,z_2) ------ and we have to prove that using the definition of R and the properties of R1 and R2. The logical way to proceed would therefore be to express those statements in terms of R1 and R2. Let us do just that. (1) R is reflexive. By definition, (x_1,x_2) R (x_1,x_2) means (x_1 R1 x_1) and (x_2 R2 x_2). As you correctly wrote, both these statements are true because R1 and R2 are equivalences. (2) R is symmetric. Assume that (x_1,x_2) R (y_1,y_2). This means, by the definition of R, that we have: x_1 R1 y_1 x_2 R2 y_2 As R1 and R2 are symmetric, this implies that: y_1 R1 x_1 y_2 R2 x_2 And this is precisely the definition of what is meant by (y_1,y_2) R (x_1,x_2), i.e. what we wanted to prove. (3) R is transitive. The proof of this is exactly similar to the previous two proofs, I'll let you have a try. About equivalence classes ------------------------- Given an equivalence relation R on a set A, equivalence classes are subsets of A in which all elements are pairwise "equivalent" (where "equivalent" is defined by the relation R). For example, consider the set of real numbers, and the relation given by: x R y <---> |x| = |y| (|x| means the absolute value of x) You should have no trouble showing that R is an equivalence relation. In this case, equivalence classes are sets of real numbers in which all elements have the same absolute value. There is an equivalence class with one element : {0}. All other equivalence classes consist of 2 elements : {x, -x} for all x <> 0. In general, it is possible to prove the following facts: 1. Every element of A is contained in a single equivalence class, the set of elements equivalent to A, or, more formally, the set: {x | a R x} 2. Equivalence classes are pairwise disjoint : the intersection of two disctinct equivalence classes is empty. You should have studied the proofs; if this is not the case, please feel free to write again. Now, in our example, the equivalence class of an element (a_1,a_2) of S1 x S2 is the set: { (x_1,x_2) | (a_1,a_2) R (x_1,x_2) } Using the definition of R, this means: { (x_1,x_2) | (a_1 R1 x_1) and (a_2 R2 x_2) } As you see, we do not really need to know what the relations R1 and R2 are, or the elements of S1 and S2 (they don't even need to be numbers), to prove properties of R. Of course, if we wanted to actually describe R explicitly, we would need to have a description of R1 and R2; but this is not what is asked here. In some sense, this is what mathematics is all about: we try to prove properties of sets or objects, based on properties of other objects, but without needing to have a specific example of these objects - we prove the properties that are true for all possible examples. Do not hesitate to write again if you want to discuss this further. - Doctor Jacques, 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/