Equivalence Classes and Induced Partitions

Hello! Last lesson, you tested relations for reflexivity, symmetry, antisymmetry, and transitivity. Today, those tests lead to a new question: when a relation says two elements are “equivalent,” which elements belong together?

You will find equivalence classes from finite relations and collect the distinct classes into a partition of the original set. The aim is a reliable method you can use whether the relation is given as ordered pairs or as a rule.

---

From related elements to a class

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Antisymmetry is not required; two distinct equivalent elements must be related in both directions.

For an equivalence relation $R$ on a set $A$, the equivalence class of $a$ is

$$[a]=\{b\in A:aRb\}.$$

In words, $[a]$ contains every element of $A$ related to $a$. Notice the difference between $a$, which is an element, and $[a]$, which is a set. Reflexivity guarantees that $a\in [a]$.

The lecture notes Math 1365 (Intensive Mathematical Reasoning) give several short finite examples. Read these before trying the slightly different roster below.

Now consider this relation on $A=\{p,q,r,s\}$:

$$R=\{(p,p),(p,r),(r,p),(r,r),(q,q),(s,s)\}.$$

To find $[p]$, hold $p$ fixed in the first position and look for pairs $(p,b)$. The pairs $(p,p)$ and $(p,r)$ give $[p]=\{p,r\}$. Applying the same method to every element gives

$$[p]=\{p,r\},[r]=\{p,r\},[q]=\{q\},[s]=\{s\}.$$

There are four class labels here but only three distinct classes. The pair $(p,r)$ does not create a separate group called “$[r]$”: $p$ and $r$ name the same group.

Before using this grouping method, check that the relation really is an equivalence relation. All four self-pairs are present. The only pair between distinct elements, $(p,r)$, has its reverse. Within $\{p,r\}$, every possible ordered pair is present, so connected pairs stay within that group and satisfy transitivity; $q$ and $s$ have only self-pairs. Thus all three required properties hold.

---

When the relation is given by a rule

A roster is convenient for a small set, but listing every ordered pair can become tedious. Suppose

$$A=\{0,1,2,3,4,5,6,7\},$$

and $aRb$ means that $a$ and $b$ have the same remainder when divided by $3$. Equality of remainders is reflexive, symmetric, and transitive, so this is an equivalence relation.

Rather than write out $R$, choose an element and collect everything satisfying its rule. The elements with the same remainder as $0$ are $0,3,6$; those with the same remainder as $1$ are $1,4,7$; and those with the same remainder as $2$ are $2,5$. Therefore,

$$[0]=\{0,3,6\},[1]=\{1,4,7\},[2]=\{2,5\}.$$

These are all the distinct classes. For instance, $[4]=[1]$, not a fourth class, because $4$ and $1$ have the same remainder. The underlying set still matters: $8$ also has remainder $2$, but $8\notin A$, so it cannot appear in $[2]$.

This suggests an efficient routine for a finite rule-defined relation: choose an ungrouped element, find every element related to it, then repeat with an element not yet included. Once every element is accounted for, stop; calculating each remaining label would only reproduce a class you already have.

---

Why the distinct classes form a partition

A partition of $A$ is a collection of nonempty subsets that do not overlap and together contain every element of $A$. For the remainder example, the partition is

$$\{\{0,3,6\},\{1,4,7\},\{2,5\}\}.$$

The outer braces matter: this is a set of sets, not a single set of eight numbers. Each inner set is one part of the partition. Likewise, the roster example induces the partition

$$\{\{p,r\},\{q\},\{s\}\}.$$

Watch Neso Academy’s Equivalence Classes and Partitions for the reason this nonoverlapping grouping always works—not just in our two examples.

Here is the key argument in compact form. Reflexivity puts every $a\in A$ into $[a]$, so no element is left out and no class is empty. Suppose an element $x$ belongs to both $[a]$ and $[b]$. Then $aRx$ and $bRx$. Symmetry gives $xRb$, and transitivity gives $aRb$. Related elements have the same class, so $[a]=[b]$. Two classes can therefore be identical or disjoint, but never partly overlapping.

This also explains why you write each distinct class once in the partition, even though several elements may provide labels for it.

---

A diagnostic: do not group an arbitrary relation too soon

Recall the relation $Q$ from last lesson on $\{1,2,3\}$: it has every self-pair, both directions between $1$ and $2$, and both directions between $2$ and $3$, but no pair between $1$ and $3$. It is not transitive.

If we mechanically collect elements related to each starting element, we get

$$\{b:1Qb\}=\{1,2\},\{b:2Qb\}=\{1,2,3\},\{b:3Qb\}=\{2,3\}.$$

These sets partly overlap. They are not an induced partition, because $Q$ is not an equivalence relation. In particular, sharing a connection through $2$ does not let you treat $1$ and $3$ as equivalent when their required pair is missing.

For a finite problem, keep the order of work clear: first verify reflexivity, symmetry, and transitivity; then find the classes; finally list each distinct class once and check that the listed parts cover the set without overlap. If the relation is already stated to be an equivalence relation, you can begin with the classes.

---

An equivalence class $[a]$ is the set of elements related to $a$. In a finite equivalence relation, different labels may produce the same class, but distinct classes never overlap. Listing those distinct classes once gives the induced partition of the original set.

Next, you will shift from grouping elements to reading and negating mathematical statements that use words such as “every” and “some.”