9.10: Equivalence Relations

Definition \(\PageIndex{1}\)

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

Congruence modulo \(n\) is an important example of an equivalence relation:

• It is reflexive because \(x \equiv x \pmod n\).
• It is symmetric because \(x \equiv y \pmod n\) implies \(y \equiv x \pmod n\).
• It is transitive because \(x \equiv y \pmod n\) and \(y \equiv z \pmod n\) imply that \(x \equiv z \pmod n\).

There is an even more well-known example of an equivalence relation: equality itself.

Any total function defines an equivalence relation on its domain:

Definition \(\PageIndex{2}\)

If \(f : A \rightarrow B\) is a total function, define a relation \(\equiv_f\) by the rule:

\[\nonumber a \equiv _f a' \text{ IFF } f(a) = f(a').\]

From its definition, \(\equiv_f\) is reflexive, symmetric and transitive because these are properties of equality. That is, \(\equiv_f\) is an equivalence relation. This observation gives another way to see that congruence modulo \(n\) is an equivalence relation: the Remainder Lemma 8.6.1 implies that congruence modulo \(n\) is the same as \(\equiv_r\) where \(r(a)\) is the remainder of \(a\) divided by \(n\).

In fact, a relation is an equivalence relation iff it equals \(\equiv_f\) for some total function \(f\) (see Problem 9.47). So equivalence relations could have been defined using Definition 9.10.2.

Equivalence Classes

Equivalence relations are closely related to partitions because the images of elements under an equivalence relation are the blocks of a partition.

Definition \(\PageIndex{3}\)

Given an equivalence relation \(R : A \rightarrow A\), the equivalence class, \([a]_R\), of an element \(a \in A\) is the set of all elements of \(A\) related to \(a\) by \(R\).

Namely,

\[\nonumber [a]_R ::= \{x \in A \mid a R x\}.\]

In other words, \([a]_R\) is the image \(R(a)\).

For example, suppose that \(A = \mathbb{Z}\) and \(a R b\) means that \(a \equiv b \pmod 5\). Then

\[\nonumber [7]_R = \{\ldots, -3, 2, 7, 12, 22, \ldots\}.\]

Notice that 7,12, 17, etc., all have the same equivalence class; that is, \([7]_R = [12]_R = [17]_R = \cdots .\)

There is an exact correspondence between equivalence relations on \(A\) and partitions of \(A\). Namely, given any partition of a set, being in the same block is obviously an equivalence relation. On the other hand we have:

Theorem \(\PageIndex{4}\)

The equivalence classes of an equivalence relation on a set \(A\) are the blocks of a partition of \(A\).

We’ll leave the proof of Theorem 9.10.4 as a basic exercise in axiomatic reasoning (see Problem 9.46), but let’s look at an example. The congruent-mod-5 relation partitions the integers into five equivalence classes:

\(\begin{aligned} \{\ldots, -5, 0, 5, 10, 15, 20, \ldots\} \\ \{\ldots, -4,1,6,11,16,21, \ldots\} \\ \{\ldots, -3,2,7,12,17,22, \ldots\} \\ \{\ldots, -2,3,8,13,18,23, \ldots\} \\ \{\ldots, -1,4,9,14,19,24, \ldots\} \end{aligned}\)

In these terms, \(x \equiv y \pmod 5\) is equivalent to the assertion that \(x\) and \(y\) are both in the same block of this partition. For example, \(6 \equiv 16 \pmod 5\), because they’re both in the second block, but \(2 \not\equiv 9 \pmod 5\) because 2 is in the third block while 9 is in the last block.

In social terms, if “likes” were an equivalence relation, then everyone would be partitioned into cliques of friends who all like each other and no one else.