Equivalences
There are a number of special kinds of relations that are ubiquitous in mathematics. We have already studied functions-as-relations. Now we will explore another common kind of relation, the equivalence, which captures the notion of equality between objects in a universe.
Like functions, equivalences are a refinement of relations. In particular, a relation that enjoys these three properties, reflexivity, symmetry, and transitivity, is considered an equivalence.
Definition (Reflexivity): a relation \(R\) is reflexive if it relates every element in the universe to itself.
\[ \forall x \ldotp (x, x) \in R \]
Definition (Symmetry): a relation \(R\) is symmetric if any pair of related elements are also related “in the opposite direction.”
\[ \forall x, y \ldotp (x, y) \in R \rightarrow (y, x) \in R \]
Definition (Transitivity): a relation \(R\) is transitive if whenever any pair of elements are related with a common element in the middle, the first and last elements are also related.
\[ \forall x, y, z \ldotp (x, y) \in R \rightarrow (y, z) \in R \rightarrow (x, z) \in R \]
These three concepts form the definition of an equivalence relation.
Definition (Equivalence): a relation an equivalence if it is reflexive, symmetric, and transitive.
The standard equality relation \((=)\) over the natural numbers \(ℕ\) is an equivalence relation as it fulfills all three properties of an equivalence:
- Reflexive
- Identical numbers are considered equal.
- Symmetric
- Order doesn’t matter when asserting equality between numbers.
- Transitive
- When declaring \(x = y\) and \(y = z\), we know that these two facts establish that \(x\) and \(y\) are the same number and \(z\) and \(y\) are the same number. From this, we can conclude that \(x\) and \(z\) must also be the same number.
Proving Equivalences
To formally show that a relation is an equivalence, we must show that it obeys each of the three properties of an equivalence. We show the outline of such a proof using the following real-world example, arithmetic expressions, e.g., \(3 + 5\) or \(3 \cdot (2 - 1)\).
Let \((\equiv)\) be the following relation:
\[ (\equiv) = \{\, (e_1, e_2) \mid \text{\( e_1 \) and \( e_2 \) are arithmetic expressions that evaluate to the same value \( v \)} \,\} \]
Claim: \((\equiv)\) is an equivalence relation.
To show that \((\equiv)\) is an equivalence relation, we must show that it is reflexive, symmetric, and transitive.
Proof. \((\equiv)\) is a reflexive, symmetric, and transitive relation:
- Reflexive
- Because an arithmetic expression evaluates to a unique value, it must be the case that \(\forall e \ldotp e \equiv e\)
- Symmetric
- Let \(e_1, e_2 \in U\) and assume that \(e_1 \equiv e_2\). By the definition of \((\equiv)\), since the pair of expressions is related, they must evaluate to the same value \(v\). Because of this fact and the definition of \((\equiv)\), we know that the pair is related in the other direction, i.e., \(e_2 \equiv e_1\).
- Transitive
- Let \(e_1, e_2, e_3 \in U\) and assume that \(e_1 \equiv e_2\) and \(e_2 \equiv e_3\). By the definition of \(R\), this means that \(e_1\) and \(e_2\) evaluate to the same value, call it \(v_1\) and \(e_2\) and \(e_3\) evaluate evaluate to the same value, call it \(v_2\). However, we know that an arithmetic expression evaluates to a unique value, so it must be the case that \(v_1\) and \(v_2\) are identical since they are both the result from evaluating \(e_2\). This means that \(e_1 \equiv e_3\) as well.
Equivalence Closures
The closure of a set \(S\) under a property \(P\) is the (smallest) set \(S^* \subseteq S\) whose elements all satisfy \(P\). The concept of closure lifts to relations in the expected way. For example, let \(U = \{\, 0, \ldotp, 10 \,\}\) and \(P\) be the property of symmetry \(\forall x, y \ldotp (x, y) \in R \rightarrow (y, x) \in R\), then if \(R\) is the relation:
\[ R = \{\, (0, 3), (2, 5), (6, 9), (5, 2) \,\}, \]
Then the symmetric closure of \(R\) is the relation \(R^*\):
\[ S = \{\, (0, 3), (3, 0), (2, 5), (5, 2), (6, 9), (9, 6) \,\}. \]
We can compute the closure of any relation under a property by repeatedly applying the property to generate new pairs to add to the relation until we can no longer add new pairs.
We can apply the notion of closure to all the properties of an equivalence relation simultaneously to form an equivalence closure of a set of elements. Intuitively, the equivalence closure of a set of elements captures all the different equalities induced by the properties of equivalences.
For example, consider an artificial set \(S = \{\, a, b, c \,\}\) and suppose we know that some relation \(R\) relates the elements as follows:
\[ (a, b) \in R, (b, c) \in R. \]
If we furthermore know that \(R\) ought to be an equivalence relation, then we can compute the equivalence closure of \(R\) as follows:
- The reflexive closure of the relation relates every element to itself: \((a, a), (b, b), (c, c) \in R\).
- The symmetric closure of the relation relates every pair “in the other direction”: \((b, a), (c, b) \in R\).
- The transitive closure of the relation connects every transitive pair of elements: \((a, c) \in R\).
- Finally, we also have to consider the symmetric closure again for this new pair: \((c, a) \in R\).
In this particular case, the equivalence closure of \(R\) is all nine possible pairs of \(S\) with itself, i.e., \(S × S\). This case captures the intuition that the two original equalities are sufficient to deduce that all the elements of \(S\) are equal.
Exercise (Closure, ‡): Consider the following relation \(R\) over universe \(\mathcal{U} = \,\{ a, b, c, d, e, f \,\}\):
\[ R = \{\, (a, b), (c, e), (d, b), (f, e) \,\}. \]
Compute the equivalence closure of \(R\).
Equivalence Classes
Intuitively, an equivalence relation captures some notion of equality between objects. We can then think about grouping together sets of mutually equal objects. For example, let’s return to arithmetic expressions. The following expressions are all equivalent to each other:
- \(10\).
- \(5 + 5\).
- \(2 \times (2 + 3)\).
Because they all evaluate to \(10\). Consider creating a set of such expressions, call it \(S_4\) with the property that they all evaluate to \(4\):
\[ S_4 = \{\, e \mid \text{ \( e \) is an arithmetic expression that evaluates to \( 4 \)} \,\}. \]
Any pair of expressions within \(S_4\) are equivalent to each other. We call such a set an equivalence class.
Definition (Equivalence Classes): an equivalence class of an equivalence relation \(R\) over universe \(U\) is a set \(S\) of elements drawn from \(U\) that are pairwise equivalent according to \(R\), i.e.,
\[ \forall x, y \in S \ldotp (x, y) \in R. \]
Recall that \(x \mod y\) is the whole-number remainder of \(x \div y\). Because of the nature of division, the result of \(x \mod y\) takes on the values \(0, \ldots, y-1\). Because of this, we can consider, e.g., the equivalences classes induced by taking a number and modding it by 3. \(x \mod 3\) takes on three values, \(0\), \(1\), and \(2\), and thus, \(\mod 3\) induces three equivalence classes:
- \(E_1 = \{\, 0, 3, 6, 9, \ldots \,\}\).
- \(E_2 = \{\, 1, 4, 7, 10, \ldots \,\}\).
- \(E_3 = \{\, 2, 5, 8, 11, \ldots \,\}\).
In the context of the modulus operator, we can say that any pair of numbers in an equivalence class are equivalent modulo 3, e.g., \(4\) and \(11\) are equivalent modulo \(3\).