Definition 6.2.1.1.
A relation \(R\) on a set \(A\) is called an equivalence relation if \(R\) is reflexive, symmetric, and transitive.
Subsection 6.2.1 A special class of binary relation
Equivalence relations are important throughout mathematics and computer science. It makes the notion of equivalent objects precise.
Definition 6.2.1.2.
This is a notion that makes precise when two thing are “the same” up to differences that we are willing to ignore. We have seen this before.
For example, we regularly think of a \$1 note as “the same” as four quarters, though they are different. According to the United States Mint, a quarter is \(5.670\) grams. That means $1000 in quarters weighs about \(50\) pounds. On the other hand, a $1 note weighs about \(1\) gram, so $1000 in $1 notes weighs about \(2.2\) pounds. Would you rather run a race carrying $1000 in $1 notes or quarters ?
1
www.usmint.gov/learn/coin-and-medal-programs/coin-specificationsFor a more mathematical example, we think of \(\frac{2}{6}\) as equal to \(\frac{1}{3}\text{.}\) In what sense are they the same ? In this case, two objects are equal as rational numbers, but differ in representation.
Remark 6.2.1.3.
We often use \(\sim\) instead for equivalence relations, so if \(a\) and \(b\) are equivalent, we might write \(a \sim b\text{.}\)
We need to verify that \(R\) is reflexive, symmetric, and transitive. Recall that these are characterized by universal conditions. To show something is true “for all \(x\) in \(A\)”, we fix a generic element \(a\) in \(A\text{,}\) and show that the conditions are satisfied for the generic element \(a\text{.}\) Then since the condition is satisfied for the generic element, it is satisfied by all the elements. How do we do this in practice ?
Proof Technique 6.2.1.4. Show \(R\) is an equivalence relation.
Suppose \(R\) is a relation on a set \(A\text{,}\) and we want to prove \(R\) is an equivalence relation. The proof has three parts.
-
Conclude \(R\) is an equivalence relation.
Example 6.2.1.5. Same absolute value relation.
Let \(R\) be the relation on \(\ZZ\) defined by \(a\,R\,b\) if and only if \(\abs{a} = \abs{b}\text{.}\)
Show that \(R\) is an equivalence relation.
Solution.
We check the three defining characteristics.
- Reflexive
- Let \(a \in \ZZ\text{.}\) Then \(\abs{a} = \abs{a}\text{,}\) so \(aRa\text{.}\) Thus \(R\) is reflexive.
- Symmetric
- Let \(a, b \in \ZZ\text{.}\) Suppose \(a\,R\,b\) so that \(\abs{a} = \abs{b}\text{.}\) Then \(\abs{b} = \abs{a}\text{,}\) so \(bRa\text{.}\) Thus \(R\) is symmetric.
- Transitive
- Let \(a,b, c \in \ZZ\text{.}\) Suppose \(a\,R\,b\) and \(bRc\) so that \(\abs{a} = \abs{b}\) and \(\abs{b} = \abs{c}\text{.}\) Then \(\abs{a} = \abs{c}\text{,}\) so \(aRc\text{.}\) Thus \(R\) is transitive.
Therefore \(R\) is an equivalence relation.
Example 6.2.1.6. Differerence is an integer relation.
Is \(R\) an equivalence relation ?
Solution.
We check the three defining characteristics.
- Reflexive
- Let \(a \in \RR\text{.}\) Then \(a - a = 0 \in \ZZ\text{,}\) so \(aRa\text{.}\) Thus \(R\) is reflexive.
- Symmetric
- Let \(a, b \in \RR\text{.}\) Suppose \(a\,R\,b\) so that \(a - b = k \in \ZZ\text{.}\) Then \(b - a = -k \in \ZZ\text{,}\) so \(bRa\text{.}\) Thus \(R\) is symmetric.
- Transitive
- Let \(a,b, c \in \RR\text{.}\) Suppose \(a\,R\,b\) and \(bRc\) so that \(a - b = k \in \ZZ\) and \(b - c = \ell \in \ZZ\text{.}\) Then \(a - c =(a-b)+(b-c)= k + \ell \in \ZZ\) and because the sum of integers is an integer, we have \(aRc\text{.}\) Thus \(R\) is transitive.
Therefore \(R\) is an equivalence relation.
Theorem 6.2.1.7.
Let \(m\gt 1\) be an integer. Let \(R\) be the relation on \(\ZZ\)
\begin{equation*}
R = \{(a, b) \in \ZZ^2 \given a \equiv b \pmod{m}\}.
\end{equation*}
Then \(R\) is an equivalence relation.
Proof.
We check the three defining conditions.
- Reflexive
- Let \(a \in \ZZ\text{.}\) Then \(m \mid (a - a)\text{,}\) so \(a \equiv a \pmod{m}\text{.}\) Then \(aRa\text{.}\) Thus \(R\) is reflexive.
- Symmetric
- Let \(a, b \in \ZZ\text{.}\) Suppose \(a\,R\,b\) so that \(a \equiv b \pmod{m}\text{.}\) Then \(a - b = km\) for some integer \(k\text{.}\) Then \(b - a = (-k)m\text{,}\) so \(b \equiv a \pmod{m}\text{.}\) Then \(b R a\text{.}\) Thus \(R\) is symmetric.
- Transitive
- Let \(a, b, c \in \ZZ\text{.}\) Suppose \(a\,R\,b\) and \(b R c\) so that \(a \equiv b \pmod{m}\) and \(b \equiv c \pmod{m}\text{.}\) Then \(a = b + km\) for some integer \(k\text{,}\) and \(b = c + \ell m\) for some integer \(\ell\text{.}\) Then\begin{equation*} a = b + km = (c + \ell m) + km = c + (\ell + k)m. \end{equation*}Since \(k\) and \(\ell\) are integers, \(k + \ell\) is an integer. Then \(a \equiv c \pmod{m}\text{,}\) and so \(a R c\text{.}\) Thus \(R\) is transitive.
Therefore \(R\) is an equivalence relation.
https-//xkcd.com/1793/) The key is portion control, which is why I’ve switched to eating smaller cans of frosting instead of full bottles.
