# Proving Equivalence Relations, Constructing and Defining Operations on Equivalence Classes

I think I have an intuitive sense of how ordered pairs can function to specify equivalence classes when used in the construction of integers and rationals, for example. I put the cart before the horse, however, and am less well versed in how to prove an equivalence relation, construct equivalence classes, and define operations on equivalence classes.

I have received feedback that one may not define operations on equivalence classes by appealing to individual elements (e.g., it is insufficient to indicate
[(a,b)] + [(c,d)] = [(a+c,b+d)]).

How does one prove equivalence relations, construct equivalence classes, and define operations on those classes? If the answer is too long for this forum, is there a good demonstration available online?

• In the context of equivalence relations, the operation + has no meaning. – William Elliot Nov 12 '18 at 21:44

## 3 Answers

Equivalence relations can be defined on any set $$X$$.

For a relation $$R$$ on a set $$X$$, $$R$$ is an equivalence relation if $$R$$ is reflexive, symmetric, and transitive. So to check/prove that a relation $$R$$ on $$X$$ is an equivalence relation, you need to check that $$R$$ satisfies those three properties.

Now given an equivalence relation $$R$$ on $$X$$, for any $$x\in X$$, the equivalence class of $$x$$ is $$[x]_R=\{y\in X:yRx\}$$. So the equivalence class of some $$x\in X$$ is the set of all $$y\in X$$ that are related to $$x$$. These equivalence classes are not really "constructed" as much as determined by $$R$$.

And you can define whatever operation you want on equivalence classes.

EXAMPLE: Let $$X$$ be the set of strings of length 1 to 4 formed by the English alphabet and define a relation $$R$$ on $$X$$ by $$xRy$$ iff $$x$$ has the same length as $$y$$. You can show that $$R$$ is an equivalence relation.

Now take any string from $$X$$, say 'xyza', then the equivalence class of 'xyza' is $$[xyza]_R=\{y\in X:yRxyza\}$$, the set of strings with the same length as 'xyza', i.e. the set of strings with length 4.

There are many operations you can define on the equivalence classes but the important thing is that any such operation can only have one output. You could say, given two equivalence classes $$[x]$$ and $$[y]$$, define the operation $$+$$, by $$[x]+[y]=[xy]$$. So $$+$$ outputs the set of all strings with the same length as 'xy', the string formed by concatenating 'x' and 'y'.

While the constructions involved do vary from example to example, I think that modular arithmetic is a good prototype: it illustrates a lot of ideas that you will encounter again and again when working with equivalence relations.

Modular arithmetic is all about the equivalence relation $$\sim_{{\rm mod \ } n}$$ on the set of integers $$\mathbb Z$$, where $$a \sim_{{\rm mod \ n }} b \iff n \ | \ (b - a).$$

Step 1: Proving that the relation is an equivalence relation.

This amounts to checking the three conditions below:

• Reflexivity: For any $$a \in \mathbb Z$$, it is the case that $$a \sim_{{\rm mod \ n }} a$$.

• Symmetry: For any $$a, b \in \mathbb Z$$, if $$a \sim_{{\rm mod \ n }} b$$, then $$b \sim_{{\rm mod \ n }} a$$.

• Transitivity: For any $$a, b, c \in \mathbb Z$$, if $$a \sim_{{\rm mod \ n }} b$$ and $$b \sim_{{\rm mod \ n }} c$$, then $$a \sim_{{\rm mod \ n }} c$$.

All three of these conditions should be quite straight-forward to check!

Step 2: Specifying an equivalence class.

When naming an equivalence class, it's quite convenient to refer to it as "the equivalence class that contains the element $$x$$", where $$x$$ is some element in the set. Indeed, any given element $$x$$ is contained in precisely one equivalence class; the elements that lie within this equivalence class are precisely those elements of the set that are equivalent to $$x$$ via the equivalence relation.

For example,

$$_{\sim_{{\rm mod \ } n}} =\{ \ \dots \ , \ 1-2n \ , \ 1-n \ , \ 1 \ , \ 1+n \ , \ 1+2n \ , \ \dots \ \}$$

is the equivalence class that contains the element $$1$$; the elements inside this equivalence class are precisely those elements in $$\mathbb Z$$ that are equivalent to $$1$$ under $$\sim _{{\rm mod \ } n}$$.

Step 3: Enumerating all equivalence classes

If you are asked to list all of the equivalence classes for an equivalence relation, it helps to remember that the equivalence classes form a partition of your set, i.e. every element of the set is contained in precisely one equivalence class. (We already used this fact in step 2.)

In our example, the distinct equivalence classes are:

$$_{\sim_{{\rm mod \ } n}} \ , \ _{\sim_{{\rm mod \ } n}} \ , \ \dots, [n - 1]_{\sim_{{\rm mod \ } n}} .$$

And how do we know that we haven't missed out any equivalence classes from this list? Because every element in $$\mathbb Z$$ is contained in one of the equivalence classes in this list.

Step 4: Inducing operations on equivalence classes

Quite often, we have a binary operation on the elements of the original set, and we want to define a similar binary operation on the equivalence classes. For example, there is an operation on $$\mathbb Z$$ called addition ($$+$$), so it would be nice if we can define some sort of analogous addition operation on the equivalence classes modulo $$n$$. Of course, whatever addition operation we define on the equivalence classes should be closely related to the original addition operation on integers, otherwise it would be difficult to think of it as being addition.

The most natural definition we can write down for addition of equivalence classes would be something like this:

$$[a]_{\sim_{{\rm mod \ } n}} + [b]_{\sim_{{\rm mod \ } n}} = [a + b]_{\sim_{{\rm mod \ } n}}.$$

But in writing something like this, we have to be very careful. Suppose $$a'$$ is some other element such that $$a \sim_{{\rm mod \ } n } a'$$, and suppose $$b'$$ is some other element such that $$b \sim_{{\rm mod \ } n } b'$$. Then $$[a]_{\sim_{{\rm mod \ } n}} = [a']_{\sim_{{\rm mod \ } n}}, \ \ \ [b]_{\sim_{{\rm mod \ } n}} = [b']_{\sim_{{\rm mod \ } n}}.$$

So $$[a]_{\sim_{{\rm mod \ } n}} + [b]_{\sim_{{\rm mod \ } n}} = [a']_{\sim_{{\rm mod \ } n}} + [b']_{\sim_{{\rm mod \ } n}} = [a' + b']_{\sim_{{\rm mod \ } n}}.$$

Thus, in order for our definition of addition to be consistent, it better be the case that $$[a + b]_{\sim_{{\rm mod \ } n}} = [a' + b']_{\sim_{{\rm mod \ } n}}.$$

Let's summarise all of this: in order for our definition of addition on equivalence classes to be consistent, we require that

$$a \sim_{{\rm mod \ } n } a'\ , \ b \sim_{{\rm mod \ } n } b' \implies a + b\sim_{{\rm mod \ } n } a'+ b'.$$

Fortunately, this is true! So the definition works, and we are good to go!

But be careful: not all operations on integers descend to operations on the equivalence classes. For example, we can't define division on equivalence classes in this way, because the consistency test will fail.

I found this resource which seems beginner-level and has worked examples specifically regarding integer construction: https://www.math.wustl.edu/~freiwald/310integers.pdf