Equivalence relations

Equivalence relation, a mathematical concept, is a type of relation on a given set that provides a way for elements of that set to be identified with (meaning considered equivalent to for some present purpose) other elements of that set. Equivalence relation is defined in a branch of mathematics called set theory, a vital branch underpinning all branches of mathematics and those fields that use mathematics. The power of an equivalence relation lies in its ability to partition a set into the disjoint union of subsets called equivalence classes. Because of its power to partition a set, an equivalence relation is one of the most used and pervasive tools in mathematics.

Introduction

Given a set, what can a mathematician do with it? The mathematician can consider the elements of it. For example, the mathematician can consider the elements of the set of non-negative integers: {0, 1, 2 …}. Moreover, in this example (call it "clockwork" arithmetic), suppose the mathematician wants to consider time measured in hours. How can the mathematician express the idea that 12 is equivalent to, or as mathematicians also say identified with, 24 or 48? In general, take any non-negative integer. Divide this integer by 12 and keep the remainder. Any non-negative number that gives the same remainder in this way is equivalent to any other such number. Hence, 2 is equivalent to 14, 26, 38 …. By positing that any non-negative number is equivalent to its remainder after division by 12, the mathematician succeeds in gaining a new perspective on the set of non-negative integers. The definition of equivalence relation is based on this simple idea of considering some elements to be equivalent to others under the equivalence relation.

Relation

Before discussing equivalence relation, it is necessary to review the general concept of relation on a given set. Let X be the given set. A relation, R, on X is a subset of the Cartesian product of X with itself, XxX. Hence any particular element, x, of X has the relation R with any element, y, of X if and only if (x, y) is an element of R. Note R is just a subset of the Cartesian product; the interpretation of R is key here. Equivalence relation is a special case of relation.

The Definition of Equivalence Relation

Let X be a set and let x, y, and z be elements of X. An equivalence relation, ~, on X is a relation on X such that:

Reflexive Property: x is equivalent to x for all x in X.

Symmetric Property: if x is equivalent to y, then y is equivalent to x.

Transitive Property: if x is equivalent to y and y is equivalent to z, then x is equivalent to z.

In the language of sets, one can rewrite the three properties of equivalence relation as follows:

Reflexive Property: (x, x) is in ~ for all x in X.

Symmetric Property: if (x, y) is in ~, then (y, x) is in ~.

Transitive Property: if (x, y) and (y, z) are in ~, then (x, z) is in ~.

A third common way to rewrite the three properties of equivalence relation is:

Reflexive Property: x ~ x for all x in X.

Symmetric Property: if x ~ y, then y ~ x.

Transitive Property: if x ~ y and y ~ z, then x ~ z.

where x ~ y means that (x, y) is an element of the equivalence relation ~.

Note that X may be empty. In this case, ~ is empty too. If X is non-empty, then ~ is non-empty too.

Elementary Examples of Equivalence Relation

There are two obvious equivalence relations on a set, X, that follow easily from the definition: the relation of equality and the Cartesian product. The relation of equality is defined by x ~ y if and only if x = y in X. This relation is sometimes called the trivial equivalence relation. Because the reflexive property is simply a restatement of x ~ y if and only if x = y in X, this relation is also the smallest possible equivalence relation on X since every other equivalence relation must contain this one as a subset. The easiest way to see this fact is to consider the reflexive property in the language of sets. Moreover, the other two properties follow, for the relation of equality, from the reflexive property. Hence, the relation of equality is an equivalence relation.

Another equivalence relation on X, the Cartesian product XxX, is the largest relation on X. That XxX is the largest relation follows from the definition of relation on X. That it is also an equivalence relation requires the verification of the three properties. Fortunately, the three properties of equivalence relation are, again, easily satisfied. For all x in X, (x, x) is an element of XxX. Hence the Cartesian product is reflexive. Let x, y, and z be in X. By the definition of Cartesian product, (x, y), (y, x), (y, z), and (x, z) are all elements of XxX. Thus, the symmetric and transitive properties also hold. Hence, the Cartesian product XxX, the largest relation on X, is an equivalence relation.

An Example of an Equivalence Relation in Number Theory

Clockwork arithmetic provides an example of a simple equivalence relation found in number theory. This equivalence relation has already been introduced above. Consider the set of non-negative integers. Let n and m be non-negative integers. Define an equivalence relation, ~, by n ~ m if and only if n º m (mod 12) where n º m (mod 12) means that n and m give the same remainder after each is divided by 12. To prove that this relation is an equivalence relation, one must show that it satisfies the three properties of equivalence relation. Clearly ~ is reflexive since the reminder of a number divided by 12 is unique. In symbols, the reflexive property is denoted n º n (mod 12). Also, the symmetric property is obvious since it does not matter whether the remainder of n or m is found first or second. In symbols, n º m (mod 12) <=> m º n (mod 12), where <=> denotes forward and backwards logical implication. Finally, the transitive property is also obvious since if n and m have the same remainder and m and p have the same remainder, then n and p have the same remainder. In symbols, n º m º p (mod 12).

Introduction to Equivalence Classes

In the clockwork arithmetic example, the elements of the subset of the set of non-negative integers that are multiples of 12 (including 0) are all equivalent to one another under the defined equivalence relation since they each have reminder 0 after division by 12. This subset is an example of an equivalence class under the equivalence relation. In this example, there are eleven other such equivalence classes: eleven subsets such that the elements of each subset has 1 to 11 as the remainder after division by 12. Hence, another equivalence class is the subset of the non-negative integers that begins {1, 13, 25, 37, ...}. Equivalence class is crucial to using equivalence relations. A definition is needed.

The Definition of Equivalence Class

Let X be a set. Let ~ be an equivalence relation on X. Let x be an element of X. The equivalence class of x is the subset of X that contains all elements of X that are equivalent to x under ~. In symbols, the equivalence class of x is the subset of X: {y : x ~ y and y is an element of X}.

The Equivalence Class Representative is, in General, Not Unique

For equivalence classes with more than one element, a naming problem arises. If both x and y are in equivalence class, then which element should represent the equivalence class, x or y? The answer is either one. To prove that the element that represents an equivalence class does not matter, one must show that the equivalence class of x and the equivalence class of y as defined above are the same subsets of X for x ~ y. Let A be the equivalence class of x and B be the equivalence class of y. Then x is in A and y is in B. Let a be any element in A and b be any element in B. From the definition of equivalence class, one can see that x ~ a and y ~ b. Hence, by the transitive property, x ~ b. Thus, B is contained in A. By the symmetric property, y ~ x. Hence, by the transitive property, y ~ a. Hence, A is contained in B. Therefore, A = B, and it does not matter which element of an equivalence class is chosen to represent that equivalence class. In the following, this fact will be freely used.

An Example of Equivalence Class

Every equivalence relation produces equivalence classes. In the clockwork arithmetic example, there are twelve equivalence classes: {0, 12, ...}, {1, 13, ...}, ..., {11, 23, ...}. The first equivalence class listed, {0, 12, ...}, can be called the equivalence class of 0, 12, or 24. Truly it can be called the equivalence class of any multiple of 12 including 0. As mentioned above, the name of an equivalence class can be any element of that equivalence class. Can confusion arise if two equivalence classes share a common element? No. The reason is that any two different equivalence classes are disjoint. This fact can easily be gleaned in this example by looking at the equivalence classes listed above. To prove this fact in general, one needs a theorem.

A Partition Theorem

Let X be a non-empty set and ~ an equivalence relation on X. The equivalence classes of ~ form a partition (a disjoint collection of non-empty subsets whose union is the whole set) of X.

The reflexive property of equivalence relation says that every element of X is equivalent to at least one element of X, namely itself. Hence, that element and, thus, every element, belong to some equivalence class. (Note that this fact is assumed in the above definition of equivalence class.) Since every element of X belongs to an equivalence class, X is contained in the union of the equivalence classes. To finish the proof, one must show that the equivalence classes are disjoint: for any two different equivalence classes A and B, A is disjoint from B. Let x be in both A and B. Let a be any element in A and b be any element in B. Since a and x are in A, a ~ x. Since b and x are in B, x ~ b. Hence by the transitive property, a ~ b. Thus any element of A is equivalent to any element of B. Consequently, A and B are the same subset. The upshot of this equality is that if two equivalence classes have one common element, they are the same equivalence class. Thus any pair of different equivalence classes are disjoint. Therefore, the equivalence classes of X form a partition of X.

Also note that if X is empty, ~ and the partition are both empty.

A converse of this partition theorem also exists.

A Converse of the Partition Theorem

Let X be a set and P be a partition of X. P corresponds to an equivalence relation, ~, on X where, for x and y elements of X, x ~ y if and only if x and y lie in the same element of P.

To show that ~ is an equivalence relation on X, one must show that it satisfies the three properties of equivalence relations. Let x, y, and z be elements of X. Because x lies in only one element of P since P is a partition, x ~ x. If x ~ y, then x and y lie in the same element of P (and no others). Thus y ~ x. If x ~ y and y ~ z, then x and y lie in the same element of P (and no others) and so do y and z. Thus x ~ z. Hence, ~ is an equivalence relation corresponding to P.

Note that, by construction, the equivalence classes of ~ are the elements of P.

The Correspondence of Equivalence Relation and Partition

Let X be a set. By the partition theorem, every collection of equivalence classes (induced by an equivalence relation) is a partition of X. By the converse partition theorem, every partition is a collection of equivalence classes induced by the mentioned equivalence relation. One of the most common uses of an equivalence relation is to produce a partition. Producing an equivalence relation from a partition is less common, but also useful.

A Visual Example from Algebraic Topology

A visual example of an equivalence relation producing a partition is found in the subfield of algebraic topology called simplicial homology. Consider the mathematical object known as the simplicial complex, which the reader (for the purposes of the present exposition only) may think of as points (called vertices) lying in a plane connected by lines (called edges) that do not cross each other except possibly through a vertex and do not partially overlap. Note that every edge has a vertex at each endpoint, but a vertex may stand alone. If a vertex or an edge overlaps another vertex or edge respectively, these vertices or edges are the same vertex and edge respectively. The purposed simplicial complex is very simple and easy to visualize, but a simplicial complex in general can be composed of “pieces” that have higher dimension than the zero-dimensional vertex or the one-dimensional edge and does not necessarily lie in the plane. Also there are rules for crossing and overlapping in a simplicial complex in general that are not germane to the following. The purposed simplicial complex is also known as a special type of graph.

On the purposed simplicial complex lying in the plane, define an equivalence relation on the set of vertices as follows. Let v and w be two vertices. v ~ w if and only if there is a sequence, a1, …, an, of vertices connecting v to w (a1 = v and an = w) where [ai, ai+1] is an edge. Here n is an arbitrary positive integer and i an integer greater than or equal to 1 and less than or equal to n – 1. (Note that in this sequence of vertices, every pair of consecutive vertices are endpoints of an edge. Thus an implicit sequence of edges is also being defined.) Hence, this equivalence relation is a precise way of saying that all vertices that are connected to all others by a sequence of edges lie in the same equivalence class.

However, before one can assert that ~ is an equivalence relation, one must check that the three properties are satisfied. Let n = 1, then v ~ v; hence, the equivalence relation is reflexive. If v ~ w, then there is a sequence of vertices, a1, …, an, that connect v to w. Hence the sequence, an, …, a1, connects w to v. Thus w ~ v. If v ~ w and w ~ z, then there are two corresponding sequences of vertices that connect v to w and w to z respectively: a1, …, an and b1, …, bm. The sequence a1, …, an, b1, …, bm connects v to z. Hence, v ~ z. Therefore, ~ is an equivalence relation. Consequently, the vertices that are connected to each other by a sequence of edges partition the set of vertices of this simplicial complex. The vertices in each equivalence class are connected by edges only to fellow elements in that equivalence class. They are not connected to any other vertex. Visually, one may imagine that the vertices in each equivalence class form “islands” that a point may travel on, but there is no way for that point to move to another equivalence class since there is no path of edges to follow.

Besides allowing the reader to see a partition, the visual aspect of this example is edifying in another way. The reader should easily be able to intuit why all three properties of equivalence relation are necessary to ensure that equivalence classes partition a set. Consider the islands of vertices that are the equivalence classes. Certainly, any vertex is connected to itself. Hence, every vertex must be in some equivalence class thereby ensuring that the equivalence classes do contain all vertices. Also, if v is connected to w, then of course w is connected to v. Finally, if v is connected to w and w is connected to z, then surely v is connected to z. Although it is foolish to rely on pictures in mathematics, a good picture is helpful.

One more note on the visual example. The use of the term connected in this example means that vertices are connected by a sequence of vertices and edges. This concept is more properly called path-connected or arc-connected.

Coda

Equivalence relations are so ubiquitous in mathematics and other fields that use mathematics because they enable the user to partition a set in a particular way of the user’s design. By identifying elements of that set with some other elements of that set, the equivalence relation induces a partition of the set by equivalence classes in each of which all elements are identified with each other. With the equivalence classes in hand, the user gains a new perspective on the set that he is working on. This new perspective may be impressed into many other types of service such as forming quotient groups in algebra or homology groups in simplicial homology. The uses are almost endless.