4.3 Equivalence Relations and Partitions

Section 4.2 gave us four independent relation properties. We now combine three of them to model a familiar idea: two objects may be different, yet count as equivalent according to a chosen rule.

For example, $7$ and $19$ are different integers, but both leave remainder $1$ when divided by $3$. Two files may be different byte sequences, yet have the same file type. The word “equivalent” is meaningful only after we specify the criterion.

The three requirements for equivalence

A relation $\sim$ on a set $A$ is an equivalence relation when it is:

1. reflexive: $a\sim a$ for every $a\in A$;

2. symmetric: $a\sim b$ implies $b\sim a$;

3. transitive: $a\sim b$ and $b\sim c$ imply $a\sim c$.

The symbol $\sim$ is commonly used for an equivalence relation, but the three properties—not the symbol—make it one.

Consider the relation “has the same parity as” on $\mathbb Z$, where parity means being even or odd.

• Every integer has the same parity as itself, so the relation is reflexive.

• If $a$ has the same parity as $b$, then $b$ has the same parity as $a$, so it is symmetric.

• If $a$ has the same parity as $b$, and $b$ has the same parity as $c$, then $a$ and $c$ have the same parity, so it is transitive.

Therefore “has the same parity as” is an equivalence relation.

By contrast, “is within distance $2$ of” on the integers is reflexive and symmetric but not transitive. We have

but $1\not\sim5$. The missing transitive connection prevents equivalence.

Equivalence classes

Let $\sim$ be an equivalence relation on $A$. For an element $a\in A$, the equivalence class of $a$ is

It contains exactly the elements considered equivalent to $a$.

For the same-parity relation on

the classes are

Also,

The notation $[a]$ names a set, not a single transformed value.

Three facts explain why equivalence classes form clean groups:

Every element belongs to its own class

Reflexivity gives $a\sim a$, so

No element is left unclassified.

Related representatives have the same class

Suppose $a\sim b$. If $x\in[a]$, then $x\sim a$. Combining $x\sim a$ with $a\sim b$ and using transitivity gives $x\sim b$, so $x\in[b]$. This proves $[a]\subseteq[b]$.

Symmetry gives $b\sim a$, and the same reasoning proves $[b]\subseteq[a]$. Therefore

Classes are equal or disjoint

If $[a]$ and $[b]$ share an element $x$, then $x\sim a$ and $x\sim b$. Symmetry gives $a\sim x$, and transitivity gives $a\sim b$. The previous fact then yields

Thus two equivalence classes can never overlap partially: they are identical or have empty intersection.

Partitions describe the same grouping from the other direction

A partition of a set $A$ is a collection of subsets, called blocks, satisfying:

1. every block is nonempty;

2. different blocks are disjoint;

3. the union of all blocks is $A$.

For example,

is a partition of $\{1,2,3,4,5,6\}$.

An equivalence relation produces a partition: collect its distinct equivalence classes.

Conversely, a partition produces an equivalence relation. Given a partition $\mathcal P$, define

This relation is reflexive because each element shares a block with itself, symmetric because “same block” works in either direction, and transitive because if $a$ shares a block with $b$ and $b$ shares a block with $c$, the disjoint-block rule forces all three into that one block.

So equivalence relations and partitions are two views of the same structure:

Drag artifacts into classification zones—or use the keyboard move controls—and watch the induced relation matrix appear. The challenge system includes incomplete, overlapping, and valid classifications, making the connection between three relation properties and three partition rules tangible.

Congruence modulo $m$

Parity divides the integers into two classes. Modular congruence generalizes this idea to any positive integer modulus.

First recall divisibility: for integers $d$ and $n$ with $d\ne0$,

means that $n=dk$ for some integer $k$.

For a positive integer $m$, we say that integers $a$ and $b$ are congruent modulo $m$ when $m$ divides their difference:

For example,

because

Also,

because $-1-4=-5=5(-1)$. Negative integers cause no problem; the quotient witness may be negative.

Why congruence is an equivalence relation

We verify the three properties from their definitions.

Reflexive. For every integer $a$,

so $m\mid(a-a)$ and $a\equiv a\pmod m$.

Symmetric. If $a\equiv b\pmod m$, then $a-b=mk$ for some integer $k$. Therefore

so $b\equiv a\pmod m$.

Transitive. If $a\equiv b\pmod m$ and $b\equiv c\pmod m$, then

for integers $k,\ell$. Adding gives

Since $k+\ell$ is an integer, $a\equiv c\pmod m$.

Residue classes and quotient sets

Every integer has exactly one remainder among

when divided by $m$. These remainders label the $m$ distinct equivalence classes:

For modulus $4$,

The set of all distinct equivalence classes is called a quotient set:

This slash notation does not mean ordinary division. It means “collapse integers that are congruent modulo $m$ into the same class.”

Change the modulus and launch positive or negative integers around a clock. Values orbit into their residue stations, while equivalence tests visualize whether their difference completes a whole number of turns.

Section bridge

Equivalence relations group elements that should be treated as the same. The next section studies a different combination of properties: reflexive, antisymmetric, and transitive. That combination does not form clusters; it describes precedence, containment, and hierarchy.