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
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.

-------------------------

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search