]>
A relation on a nonempty set that is reflexive, symmetric, and transitive is said to be an equivalence relation on . As the name and notation suggest, an equivalence relation is intended to define a type of equivalence among the elements of . Like partial orders, equivalence relations occur naturally in most areas of mathematics, including probability. The equivalence class of an element is the set of all elements that are equivalent to :
The most important result is that an equivalence relation on a set defines a partition of .
Suppose that is an equivalence relation on a set .
Sometimes the set
of equivalence classes is denoted
.
The idea is that the equivalence classes are new objects
obtained by identifying
elements in
that are equivalent. Conversely, every partition of a set defines an equivalence relation on the set.
Suppose that is a collection of non-empty sets that partition a given set . Show that the relation defined below is an equivalence relation on :
Sometimes the equivalence relation associated with a given partition is denoted .
The process of forming a partition associated with an equivalence relation, and the process of forming an equivalence relation associated with a partition are inverses of each other.
Suppose that is a nonempty set.
Every function defines an equivalence relation on its domain, known as the equivalence relation associated with . Moreover, the equivalence classes have a simple description in terms of the inverse images of .
Suppose that . Define a relation on by if and only if .
Suppose again that .
Suppose that is a fixed interval of , and that is the set of differentiable functions from into . Consider the equivalence relation associated with the derivative operator on . For , give a simple description of .
Let be a positive integer. Define the relation on by if and only if .
The equivalence relation is known as congruence modulo .
Equivalence relations associated with functions are universal: every equivalence relation is of this form:
Suppose that is an equivalence relation on a set . Define by . Show that is the equivalence relation associated with .
Suppose that and are equivalence relations on a set . Let denote the intersection of and (thought of as subsets of ). Equivalently, if and only if and . Show that
Suppose that we have a relation that is reflexive and transitive, but fails to be a partial order because it's not anti-symmetric. The relation and its inverse naturally lead to an equivalence relation, and then in turn, the original relation defines a true partial order on the equivalence classes. This is a common construction. The details are given in the next exercise.
Suppose that is a relation on a set that is reflexive and transitive.
Suppose that and are sets and that is a partial order on . Suppose also that . Define the relation on by if and only if . Show that is reflexive and transitive. The equivalence relation on constructed in the previous exercise is the equivalence relation associated with the function . Hence the relation can be extended to a partial order on the equivalence classes corresponding to .
Linear algebra provides several examples of important and interesting equivalence relations. To set the stage, let denote the set of matrices with real entries.
First recall that the following are row operations on a matrix:
Row operations are essential for inverting matrices and solving systems of linear equations. If and are matrices, then and are said to be row equivalent if can be transformed into by a finite sequence of row operations.
Show that row equivalence is an equivalence relation on . Hint: Note that each row operation can be reversed by another row operation.
Next recall that matrices and are said to be similar if there exists an invertible matrix such that . Similarity is very important in the study of linear transformations, change of basis, and the theory of eigenvalues and eigenvectors.
Show that similarity is an equivalence relation on .
Equivalence relations play an important role in the construction of complex mathematical structures from simpler ones. Often the objects in the new structure are equivalence classes of objects constructed from the simpler structures, modulo an equivalence relation that captures the essential properties of equality
for the new objects.
The construction of number systems is a prime example of this general idea. The next exercise explores the construction of rational numbers from integers.
Define a relation on by if and only if .