The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Proving an Equivalence Relation

Date: 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 

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 

   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 

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 
Associated Topics:
High School Sets

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.