From a Relation to a Group of Elements
In “Equivalence Relations,” a relation on a set \(A\) was called an equivalence relation when it is reflexive, symmetric, and transitive. Those conditions do more than certify that a relation behaves consistently. They allow us to collect together the elements that the relation treats as equivalent. The resulting set is called an equivalence class.
Fix an equivalence relation \(\sim\) on \(A\). If \(a\in A\), define the equivalence class of \(a\), denoted by \([a]\), to be the set of all elements of \(A\) equivalent to \(a\):
Definition (Equivalence Class). Let \(\sim\) be an equivalence relation on a set \(A\), and let \(a\in A\). The equivalence class of \(a\) is $$ [a]=\{x\in A:x\sim a\}. $$ The element \(a\) is called a representative of this class. The representative is an element of \(A\); the equivalence class \([a]\) is a set whose elements are elements of \(A\).
The relation determines which elements belong to the class. In particular, \([a]\) is not automatically the singleton set \(\{a\}\). It contains \(a\) itself by reflexivity, and it may also contain other elements related to \(a\). The notation \([a]\) is common, but other symbols such as \(C(a)\) may be used when brackets have another meaning.
First Properties of a Class
The definition immediately connects an element to its class: \(x\in[a]\) precisely when \(x\sim a\). Since \(\sim\) is reflexive, \(a\sim a\), so \(a\in[a]\). Consequently, every equivalence class is nonempty. This fact depends on the representative being an element of \(A\); the notation \([a]\) is not defined here for an \(a\) outside the underlying set.
Symmetry means that \(x\sim a\) is equivalent to \(a\sim x\). Thus, either order can be used to describe the class: $$ [a]=\{x\in A:x\sim a\}=\{x\in A:a\sim x\}. $$ The equality here follows because symmetry gives the same membership condition in both set descriptions.
Worked Example: Equality Produces Singleton Classes
Let \(A=\{p,q,r\}\), where \(p,q,r\) are distinct, and let \(\sim\) be equality on \(A\). The class of \(q\) is $$ [q]=\{x\in A:x=q\}=\{q\}. $$ Indeed, \(q\) satisfies the defining condition, while \(p\ne q\) and \(r\ne q\), so neither belongs to \([q]\). The other classes are \([p]=\{p\}\) and \([r]=\{r\}\). Equality relates no distinct elements, which is why each class has just one element. This conclusion is specific to the equality relation; other equivalence relations can give larger classes.
Worked Example: Congruence Classes Modulo \(4\)
On \(\mathbb Z\), let \(x\sim y\) mean \(x\equiv y\pmod 4\), as defined in “Equivalence Relations.” The class of \(1\) is $$ [1]=\{x\in\mathbb Z:x\equiv1\pmod4\}. $$ By the definition of congruence, \(x\in[1]\) exactly when \(x-1=4k\) for some \(k\in\mathbb Z\). Rearranging gives \(x=4k+1\), so $$ [1]=\{4k+1:k\in\mathbb Z\}. $$ For example, \(9\in[1]\) because \(9-1=8=4\cdot2\), and \(-3\in[1]\) because \(-3-1=-4=4\cdot(-1)\). In contrast, \(6\notin[1]\), since \(6-1=5\) is not divisible by \(4\). The integers \(1\) and \(9\) are different, but they represent the same class.
When Do Two Classes Agree?
A representative can be replaced by another element in its class without changing the class itself. The precise criterion is that two elements represent the same class exactly when they are equivalent to each other. This is a new and useful characterization of equivalence classes.
Theorem (Equality of Equivalence Classes). Let \(\sim\) be an equivalence relation on \(A\), and let \(a,b\in A\). Then $$ [a]=[b]\quad\Longleftrightarrow\quad a\sim b. $$
Proof. First suppose \(a\sim b\). We prove the two set inclusions. Let \(x\in[a]\). By the definition of \([a]\), \(x\sim a\). Since \(a\sim b\), transitivity gives \(x\sim b\). Therefore \(x\in[b]\), and \([a]\subseteq[b]\). Now let \(y\in[b]\). Then \(y\sim b\). Symmetry applied to \(a\sim b\) gives \(b\sim a\). By transitivity, \(y\sim a\), so \(y\in[a]\). Hence \([b]\subseteq[a]\), and equality by double inclusion gives \([a]=[b]\).
Conversely, suppose \([a]=[b]\). Reflexivity gives \(a\sim a\), so \(a\in[a]\). Since \([a]=[b]\), it follows that \(a\in[b]\). By the definition of \([b]\), this means \(a\sim b\). Both implications hold, proving the equivalence. \(\square\)
The proof shows exactly where the assumptions enter. Transitivity and symmetry establish the inclusions when \(a\sim b\); reflexivity places \(a\) in its own class for the reverse implication. If one of these properties were missing, the conclusion would not follow from this argument.
Worked Example: Choosing a Different Representative
Use congruence modulo \(4\), and compare the classes of \(1\) and \(9\). Since $$ 9-1=8=4\cdot2, $$ we have \(9\equiv1\pmod4\). The theorem therefore gives \([9]=[1]\). Directly, \([9]=\{x\in\mathbb Z:x\equiv9\pmod4\}\), and the condition \(x-9=4k\) is equivalent to \(x-1=4(k+2)\), which ranges over all integer multiples of \(4\) as \(k\) ranges over \(\mathbb Z\). Thus both descriptions give \(\{4k+1:k\in\mathbb Z\}\). The elements \(1\) and \(9\) are different representatives of the same set.
Two Classes Are Equal or Disjoint
For arbitrary subsets, two sets can overlap without being equal. Equivalence classes have a stronger property: if two classes share even one element, they must be the same class. Thus distinct equivalence classes cannot partially overlap. The nonempty intersection supplies the link needed to show that their representatives are equivalent.
Theorem (Equivalent Classes Are Equal or Disjoint). Let \(\sim\) be an equivalence relation on \(A\), and let \(a,b\in A\). Then either \([a]=[b]\) or $$ [a]\cap[b]=\varnothing. $$
Proof. Suppose \([a]\cap[b]\ne\varnothing\). By the definition of nonempty intersection, there is an element \(x\) such that \(x\in[a]\) and \(x\in[b]\). Hence \(x\sim a\) and \(x\sim b\). Symmetry gives \(a\sim x\), and transitivity applied to \(a\sim x\) and \(x\sim b\) gives \(a\sim b\). The theorem on equality of equivalence classes now implies \([a]=[b]\).
Therefore, if the classes are not equal, their intersection cannot be nonempty. By the characterization of the empty set, this means \([a]\cap[b]=\varnothing\). This proves the stated alternative. \(\square\)
The theorem does not say that any two classes are equal. It says that overlap forces equality; otherwise the classes have no elements in common. This is a particularly useful test: to prove two classes equal, it is enough to establish that their representatives are equivalent. To show they are different, it is enough to show their classes have no common element.
Classes Defined by a Function
The equivalence relation formed from equal function values provides another way to interpret classes. Suppose \(f\) is a rule assigning to each \(x\in A\) a value \(f(x)\) (functions are defined formally in a later tutorial). Declare \(x\sim_f y\) when \(f(x)=f(y)\). The earlier result that equal function values define an equivalence relation lets us form its classes. For any \(a\in A\), $$ [a]=\{x\in A:f(x)=f(a)\}. $$ In words, the class consists of all inputs that have the same output as \(a\). The output \(f(a)\) is fixed, while the class collects every input producing it.
Worked Example: Absolute Value on the Integers
Define a relation on \(\mathbb Z\) by \(x\sim y\) if and only if \(|x|=|y|\). This is the relation obtained by assigning each integer \(n\) the value \(|n|\), so it is an equivalence relation. Consider the class of \(5\): $$ [5]=\{n\in\mathbb Z:|n|=5\}=\{-5,5\}. $$ To verify the listed elements, \(|5|=5\) and \(|-5|=5\). If an integer \(n\) belongs to the class, then \(|n|=5\), which means \(n=5\) or \(n=-5\); there are no other elements. The class of \(-5\) is also \(\{-5,5\}\), as predicted because \(|5|=|-5|\). The class of \(3\), namely \(\{-3,3\}\), is disjoint from \([5]\) because neither integer in one set is in the other.
Classes Collect the Whole Underlying Set
Every element of \(A\) belongs to at least one class: if \(a\in A\), reflexivity gives \(a\sim a\), and therefore \(a\in[a]\). Since every class is defined using elements of \(A\), each class is a subset of \(A\). Together these facts show that the classes cover \(A\). Using the notation \(\{[a]:a\in A\}\) for the collection of all classes, the cover statement is $$ A=\bigcup_{a\in A}[a]. $$ Here the union is a union of sets, one class for each possible representative. The equality does not imply that different representatives always give different sets: as the equality criterion shows, equivalent representatives yield the same class.
This construction explains why equivalence classes are useful. Rather than keep track of every individual element, we can group elements that are equivalent under the chosen relation. For congruence modulo \(4\), for example, the integers fall into classes according to their remainder behavior. For a function, the groups consist of inputs producing equal outputs. Which elements are grouped together depends on the relation, so changing the relation can change the classes even when the underlying set stays the same.
| Equivalence relation | Underlying set | Example class |
|---|---|---|
| Equality | \(\{p,q,r\}\) | \([q]=\{q\}\) |
| Congruence modulo \(4\) | \(\mathbb Z\) | \([1]=\{4k+1:k\in\mathbb Z\}\) |
| Equal absolute values | \(\mathbb Z\) | \([5]=\{-5,5\}\) |
Check Your Understanding
- Let \(\sim\) be an equivalence relation on \(A\). Write the set-builder definition of \([a]\), including the requirement on \(a\).
- Why must \(a\in[a]\) for each \(a\in A\)?
- If \(a\sim b\), what is the relationship between \([a]\) and \([b]\), and which theorem gives it?
- If \([a]\cap[b]\ne\varnothing\), what can you conclude about \([a]\) and \([b]\)?
- For the relation \(x\sim y\) on \(\mathbb Z\) defined by \(|x|=|y|\), list the elements of \([4]\).