Observe that every x ∈ N can be written either as x = 3n, or x = 3n + 1, or x = 3n + 2, depending on the remainder when x is divided by 3. Clearly, the relation ≡ is reflexive; it is also transitive:

Let a ≡ b and b ≡ c; then there are k,n, mN, and r,s,t   2 such that a = 3k + r, b = 3n + s, c = 3m + t. Since a ≡ b, we must have r = s, and since b ≡ c, we have s = t; thus, r = s = t, and we see that a = 3k + r, c = 3m + r,  which tells us that a ≡ c. Hence, ≡ is transitive.

However, ≡ is not antisymmetric; take for example a = 4, and b = 7; then 4 ≡ 7 and 7 ≡ 4, since they both have remainder 1 when divided by 3. But this example indicates that ≡ has another property: If a ≡ b then b ≡ a, for any a,b ∈ N. Many important relations have this property in addition to being reflexive and transitive,  so they have been given a special name.

Definition 1.1. A relation R on a set A is called symmetric if ha,biR implies hb,aiR for all a,bA; in other words, R is symmetric if R = R˘.

R is called an equivalence relation if R is reflexive, transitive and symmetric.

Example 1.1. The following are all equivalence relations:

1. Let A be the set of all squares and define the relation R by aRb if a and b have the same area.

2. Let A be the set of all straight lines in the plane and define R by gRh if g = h or g and h are parallel.

3. Let A be the set of all cars in Iceland and define R by cRd if c and d have the same colour.

4. Let A = N × N, i.e. the set of all pairs (n, m) where n and m are natural numbers. Define the relation R on A by hn,miRhs,ti if n · t = m · s. We will show that R is an equivalence relation, i.e. we prove that R has the three defining properties of an equivalence:

(a) Show that R is reflexive, i.e. 〈n,m〉R〈n,m〉for alln, m ∈ N.

(b) R is transitive, i.e.

hn,miRhp, qi and 〈p,q〉R〈s, t〉 imply that 〈n,m〉R〈s, t〉.

(c) R is symmetric, i.e. if 〈n,m〉R〈s,t〉 then 〈s,t〉R〈n,m〉.

We show only 4a, the rest will be left as an exercise. Let 〈n,m〉∈ A. From our definition of R we know that 〈n,m〉R〈n,m〉iff n · m = n · m; this equation is true for all natural numbers, so we obtain 〈n,m〉R〈n,m〉; hence R is reflexive.

The importance of equivalence relations lies in the fact that they induce a grouping of the base set into subsets. Let us look at two examples:

Example 1.2.

1. Let A be a set of objects each of which has only one colour;

these could be blocks or balls or similar things. If we are teaching a child to distinguish colours, we might ask the child to make heaps of those objects which have the same colour. By doing this, we are in fact training the child to work with the relation R on A, which is defined by xRy if x and y have the same colour.

A heap of objects then would be the set {y ∈ A : xRy} for some fixed x ∈ A; we would point to one object (our fixed x), say, a blue tile, and would ask the child to collect all blue objects (all y of the same colour).

Note that each object of A is in exactly one pile.

2. At the beginning of the section we have looked at the relation R on N, where xRy if x and y have the same remainder when divided by 3. This groups the natural numbers into three subsets:

A = {0, 3, 6, 9,. ..},

B = {1, 4, 7, 10,. . .},

C = {2, 5, 8, 11,. . .}.

Observe that A = {n ∈ N : 0Rn}, B = {n ∈ N : 1Rn}, C = {n ∈ N : 2Rn}. Also, A,B, C are pairwise disjoint, and their union is all of N.

Definition 1.2. Let A be a non-empty set. A family P of non-empty subsets of A is called a partition of A, if every element of A is in exactly one element of P.

In other words,

1. For all S, T ∈ P we have S ∩ T = ∅,

2. The union of all elements of P is A.

The elements of the partition are called the classes of P. A partition of A is also called a classification.

Example 1.3.

1. The set of all students on a course can be partitioned in to the classes

(a) C1 - the set of first year students.

(b) C2 - the set of second year students.

(c) C3 - the set of third year students.

(d) C4 - the set of fourth year students.

2. Let A be a set of 23 men standing on a football field. We can partition A into two classes of eleven elements each (the teams), and one class with one element (the referee).

3. We can partition the set of all human beings at a specified time into classes

according to the day and month of birth. This gives us 366 different classes.

 If P is a partition of A, and if its classes are defined by certain properties, then each element of a specific class has the property which defines the class; in other words all the elements of a class are indistinguishable or equivalent with respect to the defining property of the class.

Our next aim is to show that equivalence relations and partitions are just two sides of the same coin: Each equivalence relation induces a unique partition and vice versa.

Definition 1.3. 1. Let R be an equivalence relation on A; for eachx ∈ A, the set {y ∈ A : xRy} is called the R – class of x, and it is denoted by Rx. The set {Rx : x ∈ A} of all R – classes is denoted by P(R).

2. Let P be a partition of A; the relation E(P) is defined on A as follows:

(1.1)               〈x,y〉∈ E(P) if x and y are in the same class of P.

The main Theorem is the following:

Theorem 1.1.

1. Let R be an equivalence relation on A; then P(R) is a partition of A.

2. Let P be a partition of A; then E(P) is an equivalence relation on A.

3. E(P(R)) = R and P(E(P)) = P.

Proof. 1. By Definition 1.2 we have to show three things:

(a). Each R-class is not empty.

(b). If Rx and Ry are different R-classes, then their intersection is empty,

(c). The union of all R-classes is all of A, i.e. each element of A is in one Rclass.

Since R is reflexive, we have for each x ∈ A that xRx; this implies x ∈ Rx. Thus,  every R-class is non – empty, and each element of Ais in (at least) one R-class;  this proves (a) and (c).

To prove (b), we first show the following:

Claim. If y ∈ Rx, then Ry = Rx.

Proof. Suppose that y ∈ Rx.

“⊆”: Let z ∈ Ry. Then, by definition of Rx, resp. Ry, we have xRy and yRz.

Since R is transitive, this implies xRz, and hencez ∈ Rx.

“⊇”: For the converse, z ∈ Rx. Then, xRz, and we know from before that xRy as well. Since R is symmetric, we obtain that yRx. Again using transitivity we see that yRz, i.e. z ∈ Ry. This shows that Rx ⊆ Ry.

Now, let Rx and Ry be different R-classes. Assume that Rx ∩ Ry ≠∅; then there exists some z ∈ Rx ∩ Ry; since z ∈ Rx we have xRz, and since z ∈ Ry we have yRz. As R is symmetric, this implies that also zRy, giving us xRz and zRy. The transitivity of R then implies that xRy, i.e. x and y are in the same R-class. It follows from our claim that Rx = Ry, which contradicts our hypothesis that they be different. So, our assumption must be wrong, and therefore, Rx ∩ Ry = ∅.

2. By definition of a partition, each element x of A is in exactly one class. Since each x is a member of its own class we have xE(P)x, and thus E(P) is reflexive.

If x is in the same class as y, then obviously y is in the same class as x; thus,  xE(P)y implies yE(P)x, and E(P) is symmetric.

Finally, let xE(P)y and yE(P)z; then, x and y are in the same class, and y and z are in the same class. Since different classes have no common elements, x and z must be in the same class, i.e. xE(P)z. This shows that E(P) is transitive.

3. For the first part, let xE(P(R))y; then x and y are in the same class of P(R),

i.e. Rx = Ry, which implies xRy.