The main idea of an equivalence relation is that it is something like equality, but not quite. Usually there is some property that we can name, so that equivalent things share that property. For example Albert Einstein and Adolf Eichmann were two entirely different human beings, if you consider all the different criteria that one can use to distinguish human beings there is little they have in common. But, if the only thing one was interested in was a person's initials, one would have to say that Einstein and Eichmann were equivalent. Future examples of equivalence relations will be less frivolous… But first, the formal definition:

Probably the most important equivalence relation we've seen to date is “congruence mod \(m\)” which we will denote using the symbol \(\equiv_m\). This relation may even be more interesting than actual equality! The reason for this seemingly odd statement is that “congruence mod \(m\)” gives us non-trivial equivalence classes. Equivalence classes are one of the most potent ideas in modern mathematics and it's essential that you understand them, so we'll start with an example. Consider congruence mod \(5\). What other numbers is (say) 11 equivalent to? There are many! Any number that leaves the same remainder as 11 when we divide it by 5. This collection is called the equivalence class of 11 and is usually denoted using an overline — \(\overline{11}\), another notation that is often seen for the set of things equivalent to 11 is \(11/\equiv_5\). \begin{equation*} \overline{11} = \{ \ldots, -9, -4, 1, 6, 11, 16, \ldots \} \end{equation*}

It's easy to see that we will get the exact same set if we choose any other element of the equivalence class (in place of 11), which leads us to an infinite list of set equalities, \begin{equation*} \overline{1} = \overline{6} = \overline{11} = \ldots \end{equation*}

And similarly, \begin{equation*} \overline{2} = \overline{7} = \overline{12} = \ldots \end{equation*}

In fact, there are really just 5 different sets that form the equivalence classes mod 5: \(\overline{0}\), \(\overline{1}\), \(\overline{2}\), \(\overline{3}\), and \(\overline{4}\). (Note: we have followed the usual convention of using the smallest possible non-negative integers as the representatives for our equivalence classes.)

What we've been discussing here is one of the first examples of a quotient structure. We start with the integers and “mod out” by an equivalence relation. In doing so, we “move to the quotient” which means (in this instance) that we go from \(\Integers\) to a much simpler set having only five elements: \(\{ \overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4} \}\). In moving to the quotient we will generally lose a lot of information, but greatly highlight some particular feature — in this example, properties related to divisibility by 5.

Given some equivalence relation \(\relR\) defined on a set \(S\) the set of equivalence classes of \(S\) under \(\relR\) is denoted \(S/\relR\) (which is read “\(S\) mod \(\relR\)”). This use of the slash — normally reserved for division — shouldn't cause any confusion since those aren't numbers on either side of the slash but rather a set and a relation. This notation may also clarify why some people denote the equivalence classes above by \(0/\equiv_5\), \(1/\equiv_5\), \(2/\equiv_5\), \(3/\equiv_5\) and \(4/\equiv_5\).

The set of equivalence classes forms a partition of the set \(S\).

In words, if you take the union of all the pieces of the partition you'll get the set \(S\), and any pair of sets from the partition that aren't identical are disjoint. Partitions are an inherently useful way of looking at things, although in the real world there are often problems (sets we thought were disjoint turn out to have elements in common, or we discover something that doesn't fit into any of the pieces of our partition), in mathematics we usually find that partitions do just what we would want them to do. Partitions divide some set up into a number of convenient pieces in such a way that we're guaranteed that every element of the set is in one of the pieces and also so that none of the pieces overlap. Partitions are a useful way of dissecting sets, and equivalence relations (via their equivalence classes) give us an easy way of creating partitions — usually with some additional structure to boot! The properties that make a relation an equivalence relation (reflexivity, symmetry and transitivity) are designed to ensure that equivalence classes exist and do provide us with the desired partition. For the beginning proof writer this all may seem very complicated, but take heart! Most of the work has already been done for you by those who created the general theory of equivalence relations and quotient structures. All you have to do (usually) is prove that a given relation is an equivalence relation by verifying that it is indeed reflexive, symmetric and transitive. Let's have a look at another example.

In Number Theory, the square-free part of an integer is what remains after we divide-out the largest perfect square that divides it. (This is also known as the radical of an integer.) The following table gives the square-free part, \(sf(n)\), for the first several values of \(n\).

It's easy to compute the square-free part of an integer if you know its prime factorization — just reduce all the exponents mod 2. For example¹This is the size of largest sporadic finite simple group, known as “the Monster.” \begin{gather*} 808017424794512875886459904961710757005754368000000000\\ = 2^{46}\cdot 3^{20}\cdot 5^9\cdot7^6\cdot 11^2\cdot 13^3\cdot 17 \cdot 19\cdot 23\cdot 29\cdot 31\cdot 41\cdot 47\cdot 59\cdot 71 \end{gather*} the square-free part of this number is \begin{gather*} 5\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31\cdot 41\cdot 47\cdot 59\cdot 71\\ = 3504253225343845 \end{gather*} which, while it is still quite a large number, is certainly a good bit smaller than the original!

We will define an equivalence relation \(\relS\) on the set of natural numbers by using the square-free part: \begin{equation*} \forall x, y \in \Naturals, \; x \relS y \; \iff sf(x) = sf(y) \end{equation*}

In other words, two natural numbers will be \(\relS\)-related if they have the same square-free parts.

Before we proceed to the proof that \(\relS\) is an equivalence relation we'd like you to be cognizant of a bigger picture as you read. Each of the three parts of the proof will have a similar structure. We will show that \(\relS\) has one of the three properties by using the fact that \(=\) has that property. In more advanced work this entire proof could be omitted or replaced by the phrase “\(\relS\) inherits reflexivity, symmetry and transitivity from equality, and is therefore an equivalence relation.” (Nice trick isn't it? But before you're allowed to use it you have to show that you can do it the hard way …)

We'll end this section with an example of an equivalence relation that doesn't “inherit” the three properties from equality.

A graph is a mathematical structure consisting of two sets, a set \(V\) of points (a.k.a. vertices) and a set²Technically, \(E\) is a so-called multiset in many instances — there may be several edges that connect the same pair of vertices. \(E\) of edges. The elements of \(E\) may be either ordered or unordered pairs from \(V\). If \(E\) consists of ordered pairs we have a directed graph or digraph — the diagrams we have been using to visualize relations! If \(E\) consists of unordered pairs then we are dealing with an undirected graph. Since the undirected case is actually the more usual, if the word “graph” appears without a modifier it is assumed that we are talking about an undirected graph.

The previous paragraph gives a relatively precise definition of a graph in terms of sets, however the real way to think of graphs is in terms of diagrams where a set of dots are connected by paths. (The paths will, of course, need to have arrows on them in digraphs.) Below are a few examples of the diagrams that are used to represent graphs.

Two graphs are said to be isomorphic if they represent the same connections. There must first of all be a one-to-one correspondence between the vertices of the two graphs, and further, a pair of vertices in one graph are connected by some number of edges if and only if the corresponding vertices in the other graph are connected by the same number of edges.

This word “isomorphic” has a nice etymology. It means “same shape.” Two graphs are isomorphic if they have the same shape. We don't have the tools right now to do a formal proof (in fact we need to look at some further prerequisites before we can really precisely define isomorphism), but isomorphism of graphs is an equivalence relation. Let's at least verify this informally.

Reflexivity Is a graph isomorphic to itself? That is, does a graph have the “same shape” as itself? Clearly!

Symmetry If graph \(A\) is isomorphic to graph \(B\), is it also the case that graph \(B\) is isomorphic to graph \(A\)? I.e. if \(A\) has the “same shape” as \(B\), doesn't \(B\) have the same shape as \(A\)? Of course!

Transitivity Well … the answer here is going to be “Naturally!” but let's wait to delve into this issue when we have a usable formal definition for graph isomorphism. The question at this stage should be clear though: If \(A\) is isomorphic to \(B\) and \(B\) is isomorphic to \(C\), then isn't \(A\) isomorphic to \(C\)?