The proof that the equivalence classes of any equivalence relation R on a set A form a partition of A is as follows (assuming the axiom of choice so that representatives can be chosen from each of the equivalence classes):

First, show that U Rx (x is an element of A) is equal to A:
Let y be an element of U Rx. Therefore, y belongs to some Rz, so y R z, and thus y is an element of A, because R only relates elements of A. We then have that U Rx is a subset of A. Similarly, if u is an element of A, by the reflexivity property of R, u R u, so u is an element of Ru, so u is an element of U Rx. So we have that A is a subset of U Rx.
We can then conclude that A = U Rx.

Next, show that the equivalence classes are pairwise disjoint.
I will prove this with an indirect argument. If the intersection of Rx and Ry is not the empty set, then there is an element u of A such that u R x and u R y. By the symmetry and transitivity properties of R, this implies that x R y. Let z be an element of Rx. Then z R x and thus z R y by transitivity. Therefore z is an element of Ry. So Rx is a subset of Ry. Similarly, it can be proven that Ry is a subset of Rx, by considering an element w of Ry. Therefore Rx = Ry. Therefore, if the intersection of Rx and Ry is not the empty set, then the two sets are equal.
We can then conclude that the equivalence classes are pairwise disjoint.

It can then be concluded that the equivalence classes under R form a partition of A.
A note on notation: U Rx is the union of all Rx, and x R y means that x is related to y under R.

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

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

Log in or register to write something here or to contact authors.