Section 3  Equivalence Relations

For another even more intuitive approach to equivalence relations click here.

In this section relations that relate elements of the same set are examined. Such a relation is said to be a relation on a set. For example, "is a brother or sister of" is a relation on the set of all people in some family. The open statement x >y imposes a relation on the set J of all integers.

There are many relations on a set U because there are many subsets of the product set UxU. Any subset could serve as a truth set, generating a relation through the statement

x ~ y    if and only if   (x,y) is in the subset.

Some relations relate each element (object) to itself u ~ u because all the ordered pairs (u,u) are in the truth set.

[3.1r] A relation on a set is reflexive if it relates every element in the set to itself.  x ~ x. (Equivalently, every ordered pair (x,x) is in the truth set.)

Example. If ~ is a relation on the set {a,b,c,d,e} defined by:

a~a, a~c, a~e, b~a, b~b, b~d, c~a, c~c, c~d, c~e, d~b, d~d, e~a, e~c, e~e
Then ~ is reflexive, because among all these elements related to elements there is:
a~a, b~b, c~c, d~d, e~e
Every element in the set is related to itself. However if e~e is removed, then not every element is related to itself, and the resulting relation is not reflexive. Click here to see more examples of reflexive relations.

To invert a relation, interchange all the elements that are related:   The relation y ~ x is called the inverse of the relation x ~ y. Note: Strictly speaking, the inverse relation ~ may or may not be the same as the original relation ~ because they may or may not generate equal truth sets.

Example. If    John is related to Jim   , then the inverse is    Jim is related to John. Here the relations before and after inversion are the same.

Another example. The inverse of x > y is y > x which is equivalent to x < y. Obviously, the relations > and < are different.

[3.1s] A relation on a set is symmetric if it relates one element to a second element, then the same relation relates the second element to the first (the inverse).  if x ~ y then y ~ x.

The examples show that the the inverse of a true relation may be true or it may be false. The name comes from the fact that symmetric relations on the coordinate plane produce a relaltion-set that is symmetric about the line y=x. Click here to see more examples and discussions of symmetric relations.

[3.1t] A relation on a set is transitive if any first element in the set is related to a second element, and the second element in turn is related to a third element, then the first element is related to the third element.

if x ~ y and if y ~ z then x ~ z

The relation   "... is smaller than ..."   is transitive. If   x is smaller than y   and if  y is smaller than z,  then   x is smaller than z.


Let a,b,c be names of objects. If x = y then x and y are names of the same object. This defines equality. Trivially, a=a, b=b, c=c. So equality is reflexive. It is also symmetric: if a=b then b=a etc. Finally, it is transitive: if a=b and b=c then a=c etc.

The idea of equality can be extended to equivalence. Any object x is equivalent to an object y if x can be replaced by y. This means that x and y have enough common properties that other properties, if any, can be ignored.
Any object is equivalent to itself. (It can be taken out and put back.)
If one object is equivalent to another, then the second object is equivalent to the first. (Either can be substituted for the other.)
If one object is equivalent to another, and the second object is equivalent to the third, then the first object is equivalent to the third. (Any object can be substituted for any other.)

This idea of equivalence can be expressed as a special kind of relation.

[3.2] A relation is an equivalence relation if it is reflexive, symmetric and transitive.

The relation "... is a brother or sister of ..." is an equivalence relation among people, if every person is allowed to be a brother or sister of himself/herself.

But the relation "... is smaller than ..." is not an equivalence relation. It is not reflexive:   x is smaller than x   cannot happen. Also it is not symmetric:  if   x is smaller than y   then   y cannot be smaller than x
The relation "... is smaller than or equal to ..." is reflexive and transitive, but not symmetric.


Let U = {1,2,3,4,5,6,7,8}. The following three colors have been assigned to the numbers:

1(blue), 2(red), 3(red), 4(green), 5(red), 6(green), 7(blue), 8(green).

The relation "... has the same color as ..." translates into the following listing of the true relation ~:

(blue)    1~1, 1~7, 7~1, 7~7
(red)    2~2, 2~3, 2~5, 3~2, 3~3, 3~5, 5~2, 5~3, 5~5
(green)    4~4, 4~6, 4~8, 6~4, 6~6, 6~8, 8~4, 8~6, 8~8.

The listing

1~1, 2~2, 3~3, 4~4, 5~5, 6~6, 7~7, 8~8
shows that every number is related to itself. Therefore the relation ~ is reflexive.

The rearrangements of the listings

(blue)    1~7, 7~1,
(red)    2~3, 3~2,   2~5, 5~2,   3~5, 5~3
(green)    4~6, 6~4,   4~8, 8~4,   6~8, 8~6
show that the relation ~ is symmetric.

Click here to see a similar argument for transitivity.
However, intuitively speaking, if one number has the same color as a second number, and that second number has the same color as the third number, then all three numbers have the same color. Therefore, the first number has the same color as the third.

Therefore the relation ~ is an equivalence relation on U.

All numbers in U have been given colors. Suppose that set V is an expansion of U: V = {1,2,3,4,5,6,7,8,9}. The number 9 has not been assigned a color (even though it appears as black in order to be seen). The above relation ~ on V does not relate 9 to any number, not even to itself. Therefore on V the relation is not reflexive. (But it is, however, symmetric and transitive. Click here to see the reasons for this last statement.)

The colors of the numbers in the set U make it easier to see the effect of the relation ~ on U. It is possible to get the same effect without colors. First collect all blue numbers into a subset. Then collect all the red numbers into another subset. Finally collect all green numbers into a subset. The result are three distinct subsets:

{1,7}, {2,3,5}, {4,6,8}
Change the relation ~ to read "... is in the same subset as ...".

Using this new definition of the relation ~, every pair of numbers in the same subset are related. Let

[a] = the subset of all numbers which are related to a
So a number x is in [a] if and only if x ~ a. Then
[1] = {1,7},   [2] = {2,3,5},   [3] = {2,3,5},   [4] = {4,6,8},   [5] = {2,3,5},   [6] = {4,6,8},   [7] = {1,7},   [8] = {4,6,8}.
From the collection [1], [2], [3], [4], [5], [6], [7], [8] the three subsets appear with repetitions:
[1] = [7] = {1,7}
[2] = [3] = [5] = {2,3,5}
[4] = [6] = [8] = {4,6,8}
. They are known as equivalence classes induced by the equivalence relation ~ on the set U.

The three subsets {1,7}, {2,3,5}, {4,6,8} have additional important properties: they break U into non-overlapping pieces. More formally, (1) Their union is all of U. (2) They are disjoint. Therefore, they form a partition of U. (See section 5 in chapter 2 for a discussion of partitions)

There are three properties of equivalence classes. To give these let U be any set, and ~ any equivalence relation on U. For each element u in U, form the equivalence class [u] of all elements x in U that are related to u: x ~ u.

[3.3r] Every element u is in its own equivalence class [u].
As a result of the reflexivity of the relation: u ~ u (The first u is one of the x's above.). So u is in [u].

[3.3s] In any equivalence class every element is related to every element.
Let x,y be any elements in the equivalence class [u]. Then x ~ u and y ~ u. Using symmetry, x ~ u and u ~ y. Using transitivity, x ~ y. Therefore, every pair of elements in the equivalence class are related.

[3.3t] Two equivalence classes are either disjoint or they are equal.
Suppose equivalent classes [a] and [b] are not disjoint. Then it must be shown that [a] = [b].
  [a],[b] not disjoint =>
     there is some element c in their intersection =>
     c is in both [a] and [b] =>
     c ~ a and c ~ b =>
     a ~ c and c ~ b    (symmetry) =>
     a ~ b and b ~ a    (transitivity and symmetry) =>
     a is in [b] and b is in [a]    (definition of equivalence classes) =>
     all elements in [b] are related to a and all elements in [a] are related to b     ([3.3s]) =>
     [b] is a subset of [a] and [a] is a subset of [b] =>
     [a] = [b].

[3.4] Theorem The equivalence classes of any equivalence relation on a set form a partition of that set.

By [3.3r] the equivalence classes cover all of the set, that is, their union is all of the set. If two equivalence classes are identical, remove one of them. By [3.3t] what is left is a disjoint collection of subsets.

The converse of [3.4] is also true:
[3.5] If a collection of subsets form a partition of a set, then the relation ~ defined by:

x ~ y if and only if x and y are in the same subset
is an equivalence relation on the set.

Click here for a proof of [3.5].


Very important results come from applying [3.5] and [3.4] to the familiar system

J = {... -3, -2, -1, 0, 1, 2, 3, ...}
of integers with the usual operations of addition, subtraction and multiplication.

The subsets of even and odd integers:

    2J = {... -6, -4, -2, 0, 2, 4, 6, ...}
2J+1 = {... -5, -3, -1, 1, 3, 5, 7, ...}
form a partition of the set of integers J. Notice that the subset 2J+1 of odd integers is obtained from the set 2J of even integers by adding 1 to every number in 2J. By [3.5] the relation
            x ~ y    if and only if   x,y are both even or both odd
is an equivalence relation. But on J this is the same relation if it is defined as:
x ~ y    if and only if    x - y is divisible by 2.
This means that the subsets of even and odd integers become equivalence classes:
[0] = 2J
    [1] = 2J+1
In the book on groups, these equivalence classes 0 and 1, written without brackets, can be added, subtracted and multiplied to become a finite system J2 = {0,1} of integers mod 2

There is a similar derivation of J3 = integers mod 3. Start with equiivalence classes

3J = {... -9, -6, -3, 0, 3, 6, 9, ...}
3J+1 = {... -8, -5, -2, 1, 4, 7, 10, ...}
3J+2 = {... -7, -4, -1, 2, 5, 8, 11, ...}.
The relation ~ defined by
x ~ y    if and only if   x - y is divisible by 3
induces the equivalence classes:
[0] = 3J
[1] = 3J+1
[2] =3J+2
The equivalence classes form the system J3 = {0,1,2}.

Let n be any integer greater than 1. For integers mod n   Jn = {0,1,2,3,...,n-1}, and the equivalence classes are:

[0] = nJ = {... -3n, -2n, -n, 0, n, 2n, 3n, ... }
[1] = nJ+1 = {... -3n+1, -2n+1, -n+1, 1, n+1, 2n+1, 3n+1, ...}
[2] = nJ+2 = {... -3n+2, -2n+2, -n+2, 2, n+2, 2n+2, 3n+2, ...}
....................................................................................................................
[n-1] = nJ+n-1 = {... -3n+n-1, -2n+n-1, -n+n-1, n-1, n+n-1, 2n+n-1, 3n+n-1, ...}

Click here for a discussion of a system called "real numbers mod 1".