Skip to main content

Section 8.4 Equivalence Relations

In mathematics, sometimes objects which are technically different are considered equal. This notion of a generalized form of equality is made precise with the concept of an equivalence relation.

Subsection 8.4.1 Equivalence Relations

Let \(R\) be a relation on a set \(A\text{.}\)

Definition 8.4.1.

  • \(R\) is reflexive if for all \(a \in A\text{,}\) \(a R a\text{.}\)

  • \(R\) is symmetric if for all \(a, b \in A\text{,}\) if \(a R b\text{,}\) then \(b R a\text{.}\)

  • \(R\) is transitive if for all \(a, b, c \in A\text{,}\) if \(a R b\) and \(b R c\text{,}\) then \(a R c\text{.}\)

Definition 8.4.2.

A relation \(R\) is an equivalence relation if it is reflexive, symmetric, and transitive.

Intuitively, equivalence relations are a generalization of “equality” in that related elements \(a, b\) share some property common.

The canonical example of an equivalence relation is equality \(=\) on \(\mathbb{R}\) (or on any subset of \(\mathbb{R}\text{,}\) or on \(\mathbb{C}\text{,}\) etc.).

Subsection 8.4.2 Congruence Modulo \(n\) as an Equivalence Relation

The relation of congruence modulo \(n\) is an equivalence relation.

  • Let \(a \in \mathbb{Z}\text{.}\) Then, \(a - a = 0\text{,}\) and \(n \mid 0\text{,}\) so \(n \mid (a - a)\text{.}\)

  • Let \(a, b \in \mathbb{Z}\text{,}\) with \(a \equiv b \pmod{n}\text{.}\) Then, \(n \mid (a - b)\text{,}\) so \(a - b = kn\) for some \(k \in \mathbb{Z}\text{.}\) Then, \(b - a = (-k)n\text{,}\) and since \(-k \in \mathbb{Z}\text{,}\) \(n \mid (b - a)\text{.}\) Thus, \(b \equiv a \pmod{n}\text{.}\)

  • Let \(a, b, c \in \mathbb{Z}\text{,}\) with \(a \equiv b \pmod{n}\) and \(b \equiv c \pmod{n}\text{.}\) Then, \(n \mid (a - b)\) and \(n \mid (b - c)\text{.}\) Then, \(a - b = kn\) and \(b - c = ln\) for some \(k, l \in \mathbb{Z}\text{.}\) Then,

    \begin{equation*} a - c = (b + kn) - (b - ln) = kn + ln = (k + l)n \end{equation*}
    Then, \(k + l \in \mathbb{Z}\text{,}\) so \(n \mid (a - c)\text{,}\) and so \(a \equiv c \pmod{n}\text{.}\)

Subsection 8.4.3 Other Examples

Greater than \(>\) and less than \(\lt\) on \(\mathbb{R}\) is not reflexive, not symmetric, but is transitive.

“Q: What will a logician choose: a half of an egg or eternal bliss in the afterlife? A: A half of an egg! Because nothing is better than eternal bliss in the afterlife, and a half of an egg is better than nothing.”

Let \(R\) be \(\leq\) or \(\geq\) on \(\mathbb{R}\text{.}\) Then \(R\) is reflexive, not symmetric, and is transitive.

Let \(R\) be \(=\) on \(\mathbb{R}\text{.}\) Then \(R\) is reflexive, symmetric, and transitive.

Let \(R\) be “divides” on \(\mathbb{Z}\text{,}\) i.e. \(\mid\) is the relation such that for \(a, b \in \mathbb{Z}\text{,}\) \(a \mid b\) if there exists an integer \(k\) such that \(b = ka\text{.}\)

Then, \(R\) is reflexive, not symmetric, and is transitive.

Let \(R\) be the relation on \(\mathbb{R}\) such that \(x R y\) if \(x^2 = y^2\text{.}\)

Let \(S\) be the set of all triangles in the plane. Then, define a relation on \(S\) such that \(a \sim b\) if triangles \(a\) and \(b\) are congruent (have the same side lengths and same angles). Then, this is an equivalence relation. Triangles which are at different positions, but have the same size and shape, are considered equal.

Let \(\mathcal{R}\) be “have equal parity” on \(\mathbb{Z}\text{,}\) i.e. \(a\) has equal parity with \(b\) if \(a\) and \(b\) are either both even or both odd. Then, \(R\) is reflexive, symmetric, and transitive.

First, note that \(a\) and \(b\) have equal parity if and only if \(2 \mid (a - b)\text{.}\)

  • Let \(a \in \mathbb{Z}\text{.}\) Then, \(a - a = 0\text{,}\) and \(2 \mid 0\text{,}\) so \(2 \mid (a - a)\text{.}\) Thus, \(a R a\text{.}\)

  • Let \(a, b \in \mathbb{Z}\) with \(a R b\text{.}\) Then, \(2 \mid (a - b)\text{,}\) so there exists \(k \in \mathbb{Z}\) such that \(a - b = 2k\text{.}\) Then, \(b - a = 2(-k)\) with \(-k \in \mathbb{Z}\text{,}\) so \(2 \mid (b - a)\text{.}\) Thus, \(b R a\text{.}\)

  • Let \(a, b, c \in \mathbb{Z}\) with \(a R b\) and \(b R c\text{.}\) Then, \(2 \mid (a - b)\) and \(2 \mid (b - c)\text{.}\) Thus, there exists \(m, n \in \mathbb{Z}\) such that \(a - b = 2m\) and \(b - c = 2n\text{.}\) Thus, since \(m - n \in \mathbb{Z}\text{,}\) we have,

    \begin{equation*} a - c = (2m + b) - (b - 2n) = 2m - 2n = 2(m - n) \end{equation*}
    Thus, \(2 \mid (a - c)\text{,}\) and so \(a R c\text{.}\)

Let \(R\) be \(\subseteq\) on \(A = \mathcal{P}(\mathbb{Z})\text{.}\) Then,

  • \(R\) is reflexive, as for all \(X \in \mathcal{P}(\mathbb{Z}), X \subseteq X\text{.}\)

  • \(R\) is not symmetric, as \(\set{1} \subseteq \set{1,2}\text{,}\) but \(\set{1,2} \nsubseteq \set{1}\text{.}\)

  • \(R\) is transitive, as if \(X \subseteq Y\) and \(Y \subseteq Z\text{,}\) then \(X \subseteq Z\text{.}\)

Subsection 8.4.4 Equivalence Classes

Definition 8.4.13.

Let \(R\) be an equivalence relation on a set \(A\text{,}\) \(x \in A\text{.}\) The equivalence class of \(x\text{,}\) denoted by \([x]_R\) (or simply \([x]\)), is the set of all elements in \(A\) that are related to \(x\text{.}\) In other words,

\begin{equation*} [x]_{R} = \set{y \in A: y R x} \end{equation*}

Note that for any \(x \in A\text{,}\) \(x \in [x]_R\text{,}\) because \(R\) is reflexive. Thus, an equivalence class is made up of exactly all the elements that are related to each other.

We say that all the elements in an equivalence class are equivalent in the sense of the equivalence relation. Any element of an equivalence class is called a representative of that class.

Let \([x] = [y]\text{.}\) Since \(x \in [x]\) and \([x] = [y]\text{,}\) we have \(x \in [y]\text{.}\) By definition of equivalence class, \(x R y\text{.}\)

Conversely, let \(x, y \in A\) with \(x R y\text{.}\) Then,

\begin{align*} [x] \amp = \set{z \in A: z R x}\\ \amp = \set{z \in A: z R y} \amp\amp \text{$z R x$ and $x R y$, so $z R y$}\\ \amp = [y] \end{align*}

If \([x] \cap [y] = \emptyset\text{,}\) then we are done. Otherwise, if \([x] \cap [y] \neq \emptyset\text{,}\) then there exists \(z \in B\text{.}\) Thus, \(z \in [x]\) and \(z \in [y]\text{,}\) so \(z R x\text{,}\) \(z R y\text{,}\) and since \(R\) is reflexive, \(x R z\text{.}\) Then, since \(R\) is transitive, \(x R y\text{.}\) Therefore, \([x] = [y]\text{.}\)

Subsection 8.4.5 Indefinite Integrals as Equivalence Classes (Calculus)

You may recall that in integral calculus, the indefinite integral (or antiderivative) of a function \(f\) is denoted by,

\begin{equation*} \int f(x) \,dx \end{equation*}

If \(F\) is an antiderivative of \(f\text{,}\) then it is often written as,

\begin{equation*} \int f(x) \,dx = F(x) + C \end{equation*}

For example,

\begin{equation*} \int 2x \,dx = x^2 + C \end{equation*}

The idea is that the indefinite integral of \(f\) is any function of the form \(F(x) + C\text{,}\) where \(C \in \mathbb{R}\) is any real number. In other words, \(\int f(x) \,dx\) is a family (or set) of functions, given by,

\begin{equation*} \int f(x) \,dx = \set{F(x): F'(x) = f(x)} \end{equation*}

Then, we know that if \(F\) is any particular function from this set, then this is equivalently,

\begin{equation*} \int f(x) \,dx = \set{F(x) + C: C \in \mathbb{R}} \end{equation*}

In fact, this set can be thought of formally as an equivalence class. Define the relation \(\sim\) on the set of functions, such that \(f \sim g\) if and only if \(f' = g'\text{,}\) equivalently, if and only if \(f\) and \(g\) differ by a constant, i.e. \(f = g + C\) for some \(C \in \mathbb{R}\text{.}\) Then, this is an equivalence relation.

First, \(f = f + 0\text{,}\) so \(f \sim f\text{.}\) Also, if \(f = g + C\text{,}\) then \(g = f + (-C)\text{.}\) Finally, if \(f = g + C\) and \(g = h + D\text{,}\) then \(f = h + (C + D)\text{.}\)

Then, the equivalence class of \(f\text{,}\) \([f]\text{,}\) is given by,

\begin{equation*} [f] = \set{g: g = f + C, C \in \mathbb{R}} = \set{f + C: C \in \mathbb{R}} \end{equation*}

Thus, the indefinite integral of \(f\) is the equivalence class of functions that only differ by a constant,

\begin{equation*} \int f(x) \,dx = [F(x)] \end{equation*}

This equivalence relation provides a generalized notion of equality. From the perspective of indefinite integrals, \(x^2\) and \(x^2 + 1\) are equal up to a constant. And, for the purposes of indefinite integration, we disregard constant differences between functions.