An equivalence class is a subset __x__ of a set **X** with an equivalence relation ~ such that:

x ∈ **X**

__x__ = {y ∈ **X**: y~x}

This means that if you pick an element x out of a set **X**, then the equivalence class __x__ is the set of all elements of **X** that are equivalent to x. For example, let's make a set **B** such that each element is a colored ball. If we take the equivalence relation "same color", then the equivalence class of a red ball picked from **B** is the set of all red balls in **B**.

**Constructing equivalence classes**

Constructing equivalence classes is a piece of cake (if we assume the axiom of choice). The basic principle of equivalence classes is that any element of an equivalent class is a good representative of the whole class. If, for example, there were a paper bag containing the elements of an equivalence class of **B**, and we pulled out a blue ball, we would know that the paper bag contained the equivalence class of blue balls in **B**.

**Properties of equivalence classes**

As shown in the previous write-up, equivalence classes of a set **X** are pairwise disjoint, meaning that you will not find an element from one equivalence class of **X** in any other equivalence class of **X**. It is also true that **X** is the union of all of the equivalence classes of **X** with respect to ~ (~ being the specific equivalence relation you are working with). The set of all equivalence classes of **X** with respect to ~ is called the quotient set, **Q**, of **X** with respect to ~. **Q** is also a partition of **X**.

Let's take our set **B** of colored balls again. The quotient set of **B** with respect to the "same color" relation would be the set of all colors. It is important to keep the equivalence relation you are using in mind. For example, the quotient set of **B** with respect to the "same shape" relation would be completely different: it would be the set of balls.

**Equivalence classes in modular arithmetic**

Equivalence classes are a convenient and concise way to talk about modulo integers. When we describe a (mod n), what we're really talking about is:

...≡(a-2n)≡(a-n)≡a≡(a+n)≡(a+2n)≡... (mod n)

or just:

a≡a+kn (mod n) k ∈ **Z** (k is an integer)

This is exactly the definition of an equivalence class. __0__ is the equivalence class containing ...0-2n, 0-n, 0, 0+n, 0+2n....
There will be n distinct equivalence classes. The quotient set of integers modulo n, **Z**_{n}, would be {__0__, __1__,..., __n-1__}. Any other equivalence classes would be identical to one of these. For example, __2+n__=__2__. It is also true that __a__+__b__=__a+b__ and __a__·__b__=__ab__. More detailed information can be found in the integers modulo n write-up.

**Equivalence classes in the real world**

If you walk into a library, there are a whole bunch of books on a large number of shelves. If you are looking for a particular book, you're probably not going to find it by chance. Fortunately, all of the books are organized by subject, author, title, date of publication, etc. The computer at your local library is programmed to search a database containing every book according to your criteria and then produce a list of every book that satisfies them. This list is an equivalence class, with each criterion being an equivalence relation. The list of every subject would be the quotient set. Using these lists lets you find a book in minutes, as opposed to the hours you might spend fruitlessly wandering aisles.

#####
Equivalence classes like __x__ are written with the bar over the letter, but HTML doesn't support that. Grr...

Sources:

The Mathematics of Ciphers: Number Theory and RSA Cryptology, S. C. Coutinho © 1999