From a Relation to a Class of Equivalent Elements
A relation on a set records which pairs of elements are related. Some relations express a notion of sameness that is broader than equality: two integers can be considered the same when they have the same remainder modulo a fixed positive integer. Equivalence relations formalize this kind of sameness. Their equivalence classes collect all the elements that count as equivalent to a chosen element.
Let \(X\) be a set. A relation \(\sim\) on \(X\) is a subset of \(X\times X\); we write \(x\sim y\) when the ordered pair \((x,y)\) belongs to that relation. The notation is chosen to suggest that \(x\) and \(y\) are regarded as equivalent, but the notation alone does not guarantee any particular properties.
- Reflexive: \(x\sim x\) for every \(x\in X\).
- Symmetric: if \(x\sim y\), then \(y\sim x\), for every \(x,y\in X\).
- Transitive: if \(x\sim y\) and \(y\sim z\), then \(x\sim z\), for every \(x,y,z\in X\).
The definition of a class uses elements of \(X\) only. Reflexivity ensures that the representative itself belongs to its class: \(x\sim x\), so \(x\in[x]_{\sim}\). If \(X=\varnothing\), the three conditions hold vacuously and there are no elements, hence no equivalence classes. For a nonempty \(X\), each element has a nonempty class.
Congruence Modulo an Integer
For integers \(a,b\) and a positive integer \(m\), say that \(a\) is congruent to \(b\) modulo \(m\), written \(a\equiv b\pmod m\), when \(m\) divides \(a-b\). In other words, \(a-b=km\) for some \(k\in\mathbb{Z}\). The positivity requirement \(m>0\) is part of the convention here.
Proof. Let \(a,b,c\in\mathbb{Z}\). For reflexivity, \(a-a=0=0m\), so \(m\) divides \(a-a\) and \(a\equiv a\pmod m\). For symmetry, suppose \(a\equiv b\pmod m\). Then \(a-b=km\) for some \(k\in\mathbb{Z}\), so \(b-a=(-k)m\); since \(-k\in\mathbb{Z}\), \(b\equiv a\pmod m\). For transitivity, suppose \(a\equiv b\pmod m\) and \(b\equiv c\pmod m\). There are integers \(k,\ell\) such that \(a-b=km\) and \(b-c=\ell m\). Adding gives \(a-c=(k+\ell)m\), with \(k+\ell\in\mathbb{Z}\), so \(a\equiv c\pmod m\). All three conditions hold. \(\square\)
Worked Example: A Class Modulo 5
Find the congruence class of \(-7\) modulo \(5\). By definition, it consists of all integers \(y\) for which \(y-(-7)=y+7\) is divisible by \(5\). Thus \(y\) belongs to the class exactly when \(y+7=5k\) for some \(k\in\mathbb{Z}\). Solving for \(y\) gives \(y=5k-7\).
Since \(5k-7=5(k-2)+3\), and \(k-2\) ranges over all integers as \(k\) does, the class can also be written as \(\{5j+3:j\in\mathbb{Z}\}\). The representative \(-7\) is in this set: \(-7=5(-2)+3\). Another member is \(3\), since \(3-(-7)=10=2\cdot5\). Therefore \([-7]_{\equiv}=[3]_{\equiv}\), and the class is precisely the integers with remainder \(3\) upon division by \(5\).
Check: for any integer \(j\), \((5j+3)-(-7)=5j+10=5(j+2)\), a multiple of \(5\). Conversely, if \(y-(-7)\) is divisible by \(5\), the calculation above gives \(y=5j+3\) for an integer \(j\). Both inclusions are verified.
This computation illustrates why a class is not usually a single element. It contains every representative that differs from the chosen one by a multiple of \(m\). For example, the class modulo \(5\) containing \(0\) consists of all multiples of \(5\), including \(0,5,-5,10\), and so on.
What Equivalence Classes Tell Us
Proof. Reflexivity gives \(x\sim x\), which means \(x\in[x]_{\sim}\). For the forward implication, suppose \([x]_{\sim}=[y]_{\sim}\). Since \(x\in[x]_{\sim}\), the equality implies \(x\in[y]_{\sim}\). By the definition of that class, \(x\sim y\).
For the reverse implication, suppose \(x\sim y\). We show that the two classes have the same elements. If \(z\in[x]_{\sim}\), then \(z\sim x\). Together with \(x\sim y\), transitivity gives \(z\sim y\), so \(z\in[y]_{\sim}\). Thus \([x]_{\sim}\subseteq[y]_{\sim}\). If \(z\in[y]_{\sim}\), then \(z\sim y\). Symmetry applied to \(x\sim y\) gives \(y\sim x\); transitivity now gives \(z\sim x\), so \(z\in[x]_{\sim}\). Hence \([y]_{\sim}\subseteq[x]_{\sim}\). The two inclusions prove equality. \(\square\)
The theorem says that equivalent representatives name exactly the same class. It also gives a useful way to prove two classes equal: first verify that their representatives are equivalent. The converse is useful when class equality is known and the relation between the representatives is what must be established.
Worked Example: Classes from Absolute Value
On \(\mathbb{R}\), define \(x\sim y\) when \(|x|=|y|\). First check the conditions. For each \(x\), \(|x|=|x|\), so the relation is reflexive. If \(|x|=|y|\), then \(|y|=|x|\), so it is symmetric. If \(|x|=|y|\) and \(|y|=|z|\), then \(|x|=|z|\), so it is transitive. Thus it is an equivalence relation.
To compute the class of \(3\), solve \(|y|=|3|=3\). The equation \(|y|=3\) has exactly the solutions \(y=3\) and \(y=-3\), so \([3]_{\sim}=\{-3,3\}\). For the class of \(0\), solve \(|y|=|0|=0\). The only solution is \(y=0\), so \([0]_{\sim}=\{0\}\).
Check: \(|-3|=3=|3|\), so \(-3\sim3\), as required for the two elements to be in the same class. Also, \(|0|=0\), and no nonzero real number has absolute value \(0\); this confirms the stated class of \(0\).
Worked Example: Differences by Integers
On \(\mathbb{R}\), define \(x\sim y\) when \(x-y\in\mathbb{Z}\). For reflexivity, \(x-x=0\in\mathbb{Z}\). For symmetry, if \(x-y\in\mathbb{Z}\), then \(y-x=-(x-y)\in\mathbb{Z}\). For transitivity, if \(x-y\in\mathbb{Z}\) and \(y-z\in\mathbb{Z}\), then \(x-z=(x-y)+(y-z)\in\mathbb{Z}\), because the sum of two integers is an integer. Thus this is an equivalence relation.
The class of \(1/3\) consists of the real numbers \(y\) satisfying \(y-1/3\in\mathbb{Z}\). Writing that integer as \(k\) gives \(y=1/3+k\), so \([1/3]_{\sim}=\{1/3+k:k\in\mathbb{Z}\}\). The number \(4/3\) lies in the same class because \(4/3-1/3=1\in\mathbb{Z}\). The theorem therefore gives \([4/3]_{\sim}=[1/3]_{\sim}\).
Check: the general expression \(1/3+k\) differs from \(1/3\) by \(k\in\mathbb{Z}\), so every displayed element is in the class. Conversely, if \(y-1/3\in\mathbb{Z}\), setting \(k=y-1/3\) gives \(y=1/3+k\). In particular, \(4/3=1/3+1\) appears in the class.
A Common Mistake: Assuming Every Relation Is an Equivalence
The three conditions must all be checked. For example, the relation \(\leq\) on \(\mathbb{R}\) is reflexive and transitive, but it is not symmetric: \(1\leq2\) while \(2\not\leq1\). If one mechanically forms the set \(\{y\in\mathbb{R}:y\leq2\}\), it is a set defined from the relation, but it is not an equivalence class. The theorem about equal or disjoint equivalence classes does not apply to it, because its relation is not an equivalence relation.
A different error is to treat a congruence class as only its displayed representative. Modulo \(5\), writing \([-7]_{\equiv}=\{-7\}\) is incorrect: it ignores that \(3-(-7)=10=2\cdot5\), so \(3\) is also in the class. The defining test is not whether an integer equals the representative; it is whether its difference from the representative is divisible by \(5\).
Equivalence relations are useful whenever a problem identifies objects according to a specified notion of sameness. The relation determines which elements belong together, while the class records all elements equivalent to a chosen representative. The same element can have many valid representatives, but the theorem above ensures that equivalent representatives produce the same set.
Check Your Understanding
For each question, use the three defining conditions explicitly where needed.
- On \(\mathbb{Z}\), define \(a\sim b\) when \(a-b\) is divisible by \(4\). Verify that this is an equivalence relation and find the class of \(-1\).
- On \(\mathbb{R}\), define \(x\sim y\) when \(x^2=y^2\). Verify the equivalence-relation conditions and find \([5]_{\sim}\).
- On \(\mathbb{Z}\), is the relation \(a\sim b\) when \(a<b\) an equivalence relation? Identify each condition that holds or fails.
- For an equivalence relation \(\sim\), prove directly from the definition that \(z\in[x]_{\sim}\) if and only if \(z\sim x\).
- Suppose \([x]_{\sim}=[y]_{\sim}\). Which defining property shows that \(x\in[x]_{\sim}\), and how does that fact imply \(x\sim y\)?