LA-1.3

Available

Equivalence Relations

Equivalence relations partition sets into disjoint classes of "equivalent" elements. This fundamental concept underlies quotient spaces in linear algebra, modular arithmetic, and the construction of new algebraic structures from old ones.

3-4 hours Foundation Level 10 Objectives

Learning Objectives

Define relations on sets and identify their properties
Verify if a relation is reflexive, symmetric, and transitive
Construct equivalence classes from an equivalence relation
Understand the bijection between equivalence relations and partitions
Apply quotient structures in algebraic contexts
Connect equivalence relations to quotient vector spaces
Prove theorems about equivalence classes
Work with the canonical projection map
Verify well-definedness of operations on quotient sets
Count partitions and equivalence relations on finite sets

Prerequisites

Basic set theory (sets, subsets, operations)
Understanding of functions and their properties
Field axioms from LA-1.1 (Algebraic Structures)
Proof techniques (direct proof, contrapositive)
Modular arithmetic basics

Historical Context

The concept of equivalence relations emerged in the late 19th century as mathematicians sought to formalize the notion of "sameness up to some property."

Gauss (1801) introduced modular arithmetic in Disquisitiones Arithmeticae, using congruence to classify integers—an early example of equivalence relations.

Dedekind and Cantor developed set theory in the 1870s-1880s, providing the language for relations and partitions.

Emmy Noether (1920s) championed the abstract approach, using quotient structures systematically in algebra. Today, equivalence relations are foundational in every area of mathematics.

1. Relations

A relation is a way of associating elements of a set with each other. We start with the general concept before specializing to equivalence relations.

Definition 1.1: Relation

A relation on a set $S$ is a subset $R \subseteq S \times S$ .

If $(a, b) \in R$ , we write $a \sim b$ or $aRb$ and say " $a$ is related to $b$ ."

Example 1.1: Examples of Relations

Less than on ℤ: $R = \{(a, b) : a < b\}$
Divisibility on ℤ: $R = \{(a, b) : a \mid b\}$
Congruence mod n: $R = \{(a, b) : n \mid (a - b)\}$
Equality: $R = \{(a, a) : a \in S\}$ (the diagonal)

Definition 1.2: Properties of Relations

A relation $\sim$ on $S$ is:

Reflexive: $a \sim a$ for all $a \in S$
Symmetric: $a \sim b \Rightarrow b \sim a$ for all $a, b \in S$
Transitive: $a \sim b$ and $b \sim c \Rightarrow a \sim c$ for all $a, b, c \in S$

Example 1.2: Checking Properties

Consider the relation "≤" on $\mathbb{R}$ :

Reflexive? Yes: $a \leq a$ for all $a$
Symmetric? No: $1 \leq 2$ but $2 \not\leq 1$
Transitive? Yes: $a \leq b$ and $b \leq c$ implies $a \leq c$

Since ≤ is not symmetric, it's not an equivalence relation.

Remark 1.1: Other Types of Relations

Relations with different property combinations have special names:

Partial order: reflexive + antisymmetric + transitive (e.g., ≤)
Strict order: irreflexive + asymmetric + transitive (e.g., <)
Preorder: reflexive + transitive (no symmetry or antisymmetry)

Definition 1.3: Antisymmetry

A relation $\sim$ is antisymmetric if:

a \sim b \text{ and } b \sim a \Rightarrow a = b

Note: antisymmetry is NOT the same as "not symmetric."

Example 1.3: Divisibility

On $\mathbb{Z}^+$ , the divisibility relation $a \mid b$ is:

Reflexive: $a \mid a$ (every number divides itself)
Antisymmetric: if $a \mid b$ and $b \mid a$ , then $a = b$
Transitive: if $a \mid b$ and $b \mid c$ , then $a \mid c$
Not symmetric: $2 \mid 4$ but $4 \nmid 2$

So divisibility is a partial order, not an equivalence relation.

2. Equivalence Relations

Definition 1.3: Equivalence Relation

An equivalence relation on a set $S$ is a relation that is reflexive, symmetric, and transitive.

Example 1.3: Congruence Modulo n

On $\mathbb{Z}$ , define $a \equiv b \pmod{n}$ iff $n \mid (a - b)$ .

Reflexive: $n \mid (a - a) = 0$ ✓
Symmetric: If $n \mid (a - b)$ , then $n \mid (b - a)$ ✓
Transitive: If $n \mid (a - b)$ and $n \mid (b - c)$ , then $n \mid (a - c)$ ✓

This is the equivalence relation behind modular arithmetic.

Definition 1.4: Equivalence Class

Given an equivalence relation $\sim$ on $S$ , the equivalence class of $a \in S$ is:

[a] = \{b \in S : a \sim b\}

Any element of $[a]$ is called a representative of the class.

Example 1.4: Equivalence Classes for Mod 3

In $\mathbb{Z}$ with congruence mod 3:

$[0] = \{..., -6, -3, 0, 3, 6, 9, ...\}$
$[1] = \{..., -5, -2, 1, 4, 7, 10, ...\}$
$[2] = \{..., -4, -1, 2, 5, 8, 11, ...\}$

Note that $[0] = [3] = [6]$ , $[1] = [4] = [7]$ , etc.

Example 2.1: Same Absolute Value

On $\mathbb{R}$ , define $a \sim b$ iff $|a| = |b|$ .

Reflexive: $|a| = |a|$ ✓
Symmetric: $|a| = |b| \Rightarrow |b| = |a|$ ✓
Transitive: $|a| = |b|$ and $|b| = |c| \Rightarrow |a| = |c|$ ✓

Equivalence classes: $[r] = \{r, -r\}$ for $r > 0$ , and $[0] = \{0\}$ .

Example 2.2: Same Remainder

On $\mathbb{Z}^+$ , define $a \sim b$ iff $a$ and $b$ leave the same remainder when divided by 5.

This is an equivalence relation with 5 classes:

$[0] = \{5, 10, 15, 20, ...\}$
$[1] = \{1, 6, 11, 16, ...\}$
$[2] = \{2, 7, 12, 17, ...\}$
$[3] = \{3, 8, 13, 18, ...\}$
$[4] = \{4, 9, 14, 19, ...\}$

Corollary 2.1: Class Membership

For any equivalence relation:

a \in [b] \iff a \sim b \iff [a] = [b]

Example 2.3: Similarity of Matrices

On the set of $n \times n$ matrices over $F$ , define $A \sim B$ iff $B = P^{-1}AP$ for some invertible $P$ .

This is an equivalence relation (similarity):

Reflexive: $A = I^{-1}AI$
Symmetric: $B = P^{-1}AP \Rightarrow A = PBP^{-1} = (P^{-1})^{-1}B(P^{-1})$
Transitive: $B = P^{-1}AP$ and $C = Q^{-1}BQ \Rightarrow C = (PQ)^{-1}A(PQ)$

Similar matrices share eigenvalues, trace, determinant, and rank.

Example 2.4: Isomorphism of Groups

On the class of groups, define $G \sim H$ iff $G \cong H$ (isomorphic).

This is an equivalence relation on groups. Each class contains all groups with the same structure.

Remark 2.1: Equivalence as Abstraction

Equivalence relations allow us to ignore irrelevant differences and focus on essential structure. "Same up to isomorphism," "same up to similarity," and "same up to a constant" are all examples of this powerful idea.

Theorem 1.1: Equivalence Classes Are Disjoint or Equal

Let $\sim$ be an equivalence relation on $S$ . For any $a, b \in S$ :

[a] \cap [b] \neq \emptyset \implies [a] = [b]

Equivalently, either $[a] = [b]$ or $[a] \cap [b] = \emptyset$ .

Proof of Theorem 1.1:

Suppose $c \in [a] \cap [b]$ . Then $a \sim c$ and $b \sim c$ .

By symmetry, $c \sim b$ . By transitivity, $a \sim b$ .

Now take any $x \in [a]$ . Then $a \sim x$ . Since $b \sim a$ (symmetry) and $a \sim x$ , we have $b \sim x$ (transitivity), so $x \in [b]$ .

Thus $[a] \subseteq [b]$ . By a symmetric argument, $[b] \subseteq [a]$ .

∎

3. Partitions

Definition 1.5: Partition

A partition of a set $S$ is a collection $\mathcal{P} = \{P_i\}_{i \in I}$ of non-empty subsets of $S$ such that:

The sets cover $S$ : $\bigcup_{i \in I} P_i = S$
The sets are pairwise disjoint: $P_i \cap P_j = \emptyset$ for $i \neq j$

Theorem 1.2: Equivalence Relations ↔ Partitions

There is a bijective correspondence between equivalence relations on $S$ and partitions of $S$ .

Equivalence → Partition: The equivalence classes form a partition.
Partition → Equivalence: Define $a \sim b$ iff $a$ and $b$ are in the same part.

Proof of Theorem 1.2:

Equivalence → Partition:

Non-empty: Each $[a]$ contains $a$ (reflexivity).
Cover: Every $a \in S$ is in $[a]$ .
Disjoint: By Theorem 1.1.

Partition → Equivalence:

Reflexive: $a$ is in the same part as $a$ .
Symmetric: If $a$ and $b$ are in the same part, so are $b$ and $a$ .
Transitive: If $a, b$ share a part and $b, c$ share a part, then all three share the same part (since parts are disjoint).

∎

Example 3.1: Partition of Integers

The partition of $\mathbb{Z}$ into even and odd integers:

\mathcal{P} = \{\{..., -4, -2, 0, 2, 4, ...\}, \{..., -3, -1, 1, 3, 5, ...\}\}

This corresponds to the equivalence relation $a \sim b$ iff $2 \mid (a - b)$ .

Example 3.2: Partition of a Finite Set

Let $S = \{1, 2, 3, 4, 5, 6\}$ . The following are valid partitions:

$\{\{1, 2, 3, 4, 5, 6\}\}$ — one part (coarsest)
$\{\{1, 2\}, \{3, 4\}, \{5, 6\}\}$ — three parts
$\{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}\}$ — six parts (finest)
$\{\{1, 3, 5\}, \{2, 4, 6\}\}$ — odd/even

Example 3.3: Non-Partition

The following are NOT valid partitions of $\{1, 2, 3, 4\}$ :

$\{\{1, 2\}, \{3\}\}$ — doesn't cover 4
$\{\{1, 2\}, \{2, 3\}, \{4\}\}$ — parts overlap (2 is in two parts)
$\{\{1, 2, 3, 4\}, \emptyset\}$ — empty set is not allowed

Theorem 3.1: Counting Partitions

For a finite set $S$ with $|S| = n$ , the number of partitions is finite (the Bell number $B_n$ ).

For an infinite set, there are uncountably many equivalence relations.

Definition 3.1: Refinement

A partition $\mathcal{Q}$ is a refinement of partition $\mathcal{P}$ if every part of $\mathcal{Q}$ is contained in some part of $\mathcal{P}$ .

Equivalently, $\mathcal{Q}$ is "finer" and $\mathcal{P}$ is "coarser."

Remark 3.1: Lattice of Partitions

The partitions of a set form a lattice under refinement. The finest partition is $\{\{a\} : a \in S\}$ (equality). The coarsest is $\{S\}$ (everything equivalent).

Example 3.4: Refinement Example

On $\{1, 2, 3, 4, 5, 6\}$ , the partition $\{\{1, 3, 5\}, \{2, 4, 6\}\}$ (odd/even) is coarser than $\{\{1\}, \{3, 5\}, \{2\}, \{4, 6\}\}$ .

The second partition refines the first: every part of the second is contained in a part of the first.

Theorem 3.2: Meet and Join of Partitions

Given two partitions $\mathcal{P}$ and $\mathcal{Q}$ :

The meet (finest common coarsening) is the coarsest partition refining both
The join (coarsest common refinement) is the finest partition coarsened by both

Remark 3.2: Connection to Equivalence Relations

If $\sim_1$ corresponds to $\mathcal{P}$ and $\sim_2$ to $\mathcal{Q}$ , then the meet partition corresponds to the intersection of relations (as subsets of $S \times S$ ).

4. Quotient Sets

Definition 1.6: Quotient Set

The quotient set of $S$ by $\sim$ is the set of all equivalence classes:

S / {\sim} = \{[a] : a \in S\}

Example 1.5: ℤ/nℤ

The quotient $\mathbb{Z}/n\mathbb{Z}$ (or $\mathbb{Z}_n$ ) is:

\mathbb{Z}_n = \{[0], [1], [2], \ldots, [n-1]\}

This has exactly $n$ elements. Operations on $\mathbb{Z}_n$ are induced from $\mathbb{Z}$ :

[a] + [b] = [a + b], \quad [a] \cdot [b] = [ab]

Remark 1.1: Well-Definedness

When defining operations on quotient sets, we must verify well-definedness: the result should not depend on which representative we choose.

For $\mathbb{Z}_n$ : if $[a] = [a']$ and $[b] = [b']$ , we need $[a + b] = [a' + b']$ . This works because $n \mid (a - a')$ and $n \mid (b - b')$ implies $n \mid ((a + b) - (a' + b'))$ .

Theorem 1.3: Canonical Projection

The map $\pi: S \to S/\!\sim$ defined by $\pi(a) = [a]$ is a surjection called the canonical projection.

Theorem 1.4: Universal Property of Quotients

If $f: S \to T$ is a function such that $a \sim b \Rightarrow f(a) = f(b)$ , then there exists a unique function $\bar{f}: S/\!\sim \to T$ such that $f = \bar{f} \circ \pi$ .

Proof of Theorem 1.4:

Define $\bar{f}([a]) = f(a)$ .

Well-defined: If $[a] = [b]$ , then $a \sim b$ , so $f(a) = f(b)$ by assumption.

Unique: If $g: S/\!\sim \to T$ also satisfies $f = g \circ \pi$ , then $g([a]) = g(\pi(a)) = f(a) = \bar{f}([a])$ .

∎

Definition 1.7: Induced Function

The function $\bar{f}$ from Theorem 1.4 is called the function induced by $f$ on the quotient.

Example 1.6: Induced Function Example

Let $f: \mathbb{Z} \to \mathbb{Z}_5$ be $f(n) = n \mod 5$ .

This induces $\bar{f}: \mathbb{Z}/5\mathbb{Z} \to \mathbb{Z}_5$ with $\bar{f}([n]) = n \mod 5$ .

In fact, $\bar{f}$ is an isomorphism!

Example 4.1: Quotient of ℤ by 2ℤ

Consider $\mathbb{Z}/2\mathbb{Z}$ with $a \sim b$ iff $2 \mid (a - b)$ .

The equivalence classes are:

$[0] = \{..., -4, -2, 0, 2, 4, ...\}$ (even integers)
$[1] = \{..., -3, -1, 1, 3, 5, ...\}$ (odd integers)

So $\mathbb{Z}/2\mathbb{Z} = \{[0], [1]\}$ has exactly 2 elements.

Corollary 4.1: Cardinality of Quotients

If $S$ is finite and $\sim$ has $k$ equivalence classes, then $|S/\!\sim| = k$ .

If all classes have the same size $m$ , then $|S| = k \cdot m$ .

Remark 4.1: Notation Warning

The notation $S/\!\sim$ means "quotient of $S$ by $\sim$ ." For modular arithmetic, $\mathbb{Z}/n\mathbb{Z}$ or $\mathbb{Z}_n$ denotes the quotient by congruence mod $n$ .

Example 4.2: Circle as Quotient

The circle $S^1$ can be viewed as the quotient $\mathbb{R}/\mathbb{Z}$ , where $x \sim y$ iff $x - y \in \mathbb{Z}$ .

Each equivalence class is $[t] = \{t + n : n \in \mathbb{Z}\}$ , with unique representative in $[0, 1)$ .

5. Counting Partitions

Definition 5.1: Bell Numbers

The Bell number $B_n$ counts the number of partitions (equivalently, equivalence relations) on an $n$ -element set.

Example 5.1: Bell Numbers

The first few Bell numbers are:

$B_0 = 1$ (one way to partition the empty set)
$B_1 = 1$
$B_2 = 2$ : $\{\{a,b\}\}$ or $\{\{a\},\{b\}\}$
$B_3 = 5$
$B_4 = 15$
$B_5 = 52$

Theorem 5.1: Bell Number Recurrence

Bell numbers satisfy:

B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k

Proof:

Consider where element $n+1$ goes in a partition of $\{1, \ldots, n+1\}$ .

Choose $k$ elements from $\{1, \ldots, n\}$ to be in the same class as $n+1$ : $\binom{n}{k}$ ways.

Partition the remaining $n-k$ elements: $B_{n-k}$ ways.

Wait—the recurrence uses $B_k$ , not $B_{n-k}$ . By substitution $j = n - k$ , we get the standard form.

∎

Remark 5.1: Stirling Numbers

The Stirling number of the second kind $S(n, k)$ counts partitions of an $n$ -element set into exactly $k$ non-empty parts.

B_n = \sum_{k=0}^{n} S(n, k)

Example 5.2: Computing B₃

List all partitions of $\{a, b, c\}$ :

$\{\{a, b, c\}\}$ — one part
$\{\{a, b\}, \{c\}\}$
$\{\{a, c\}, \{b\}\}$
$\{\{b, c\}, \{a\}\}$
$\{\{a\}, \{b\}, \{c\}\}$ — three parts

Total: $B_3 = 5$ .

Theorem 5.2: Dobinski's Formula

The Bell numbers can be computed as:

B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}

Example 5.3: Using Stirling Numbers

The Stirling numbers $S(4, k)$ for partitions of a 4-element set:

$S(4, 1) = 1$ (all in one part)
$S(4, 2) = 7$
$S(4, 3) = 6$
$S(4, 4) = 1$ (each in its own part)

Check: $B_4 = 1 + 7 + 6 + 1 = 15$ . ✓

5. Connection to Quotient Spaces

In linear algebra, if $V$ is a vector space and $W$ is a subspace, we define an equivalence relation:

v \sim u \iff v - u \in W

The equivalence classes are cosets:

[v] = v + W = \{v + w : w \in W\}

The quotient set $V/W$ becomes a vector space (the quotient space) with operations:

[v] + [u] = [v + u], \quad \alpha[v] = [\alpha v]

We will study this in detail in LA-2.5: Direct Sums & Quotient Spaces.

Theorem 6.1: Dimension of Quotient Space

If $V$ is finite-dimensional and $W$ is a subspace, then:

\dim(V/W) = \dim(V) - \dim(W)

Example 6.1: Quotient of ℝ³

Let $V = \mathbb{R}^3$ and $W = \{(x, y, 0) : x, y \in \mathbb{R}\}$ (the $xy$ -plane).

The cosets are horizontal planes: $[v] = \{(x, y, z_0) : x, y \in \mathbb{R}\}$ for each $z_0$ .

$\dim(V/W) = 3 - 2 = 1$ . Indeed, $V/W \cong \mathbb{R}$ .

Example 6.2: Quotient Group

In group theory, if $N \trianglelefteq G$ is a normal subgroup, define:

g \sim h \iff gh^{-1} \in N

The equivalence classes are cosets $gN$ , and $G/N$ is a group.

Example 6.3: Quotient of ℝ²

Let $V = \mathbb{R}^2$ and $W = \{(x, 0) : x \in \mathbb{R}\}$ (the $x$ -axis).

Two vectors are equivalent iff they have the same $y$ -coordinate:

(a, b) \sim (c, d) \iff b = d

Each equivalence class is a horizontal line. The quotient $V/W \cong \mathbb{R}$ .

Remark 6.1: First Isomorphism Theorem

For a linear map $T: V \to W$ , define $v \sim u \iff T(v) = T(u)$ .

This is an equivalence relation with classes $[v] = v + \ker(T)$ .

The First Isomorphism Theorem states:

V / \ker(T) \cong \text{im}(T)

Example 6.4: Projection Map

Consider the projection $\pi: \mathbb{R}^3 \to \mathbb{R}^2$ with $\pi(x, y, z) = (x, y)$ .

$\ker(\pi) = \{(0, 0, z) : z \in \mathbb{R}\}$ (the $z$ -axis).

By the First Isomorphism Theorem:

\mathbb{R}^3 / \ker(\pi) \cong \mathbb{R}^2

Theorem 6.2: Well-Definedness of Quotient Operations

The vector space operations on $V/W$ are well-defined because if $v \sim v'$ and $u \sim u'$ (i.e., $v - v', u - u' \in W$ ), then:

$(v + u) - (v' + u') = (v - v') + (u - u') \in W$
$\alpha v - \alpha v' = \alpha(v - v') \in W$

7. Worked Examples

Example 7.1: Verifying an Equivalence Relation

Problem: Is the relation " $a$ and $b$ have the same last digit" an equivalence relation on $\mathbb{N}$ ?

Solution:

Reflexive: $a$ has the same last digit as $a$ . ✓
Symmetric: If $a$ has the same last digit as $b$ , then $b$ has the same last digit as $a$ . ✓
Transitive: If $a, b$ share a last digit and $b, c$ share a last digit, then $a, c$ share a last digit. ✓

Yes, it's an equivalence relation with 10 equivalence classes (one for each digit 0-9).

Example 7.2: Finding Equivalence Classes

Problem: On $\mathbb{Z}$ , define $a \sim b$ iff $3 \mid (a + b)$ . Is this an equivalence relation?

Solution:

Reflexive: $a \sim a$ iff $3 \mid 2a$ . This fails for $a = 1$ since $3 \nmid 2$ . ✗

No, it's not reflexive, so it's not an equivalence relation.

Example 7.3: Describing a Quotient

Problem: On $\mathbb{R}$ , define $x \sim y$ iff $x - y \in \mathbb{Z}$ . Describe $\mathbb{R}/\!\sim$ .

Solution:

The equivalence class $[x]$ consists of all numbers differing from $x$ by an integer:

[x] = \{x + n : n \in \mathbb{Z}\}

Each class has exactly one representative in $[0, 1)$ .

So $\mathbb{R}/\!\sim \cong [0, 1)$ with endpoints identified—this is a circle!

Example 7.4: Counting Equivalence Classes

Problem: On the set $S = \{1, 2, 3, 4, 5, 6\}$ , define $a \sim b$ iff $a \equiv b \pmod{3}$ . How many equivalence classes are there?

Solution:

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

There are 3 equivalence classes.

Example 7.5: Well-Definedness Check

Problem: On $\mathbb{Z}_4$ , is $f([a]) = [2a]$ well-defined?

Solution: We need: if $[a] = [b]$ , then $[2a] = [2b]$ .

If $a \equiv b \pmod{4}$ , then $a - b = 4k$ for some $k$ .

So $2a - 2b = 8k = 4(2k)$ , which means $2a \equiv 2b \pmod{4}$ . ✓

Yes, $f$ is well-defined.

Example 7.6: Non-Well-Defined Function

Problem: On $\mathbb{Z}_4$ , is $g([a]) = [a^2]$ well-defined?

Solution: Check: $[0] = [4]$ , so we need $[0^2] = [4^2]$ .

$0^2 = 0$ and $4^2 = 16 \equiv 0 \pmod{4}$ . ✓

Check another: $[1] = [5]$ , so we need $[1^2] = [5^2]$ .

$1^2 = 1$ and $5^2 = 25 \equiv 1 \pmod{4}$ . ✓

After checking all cases, yes, $g$ is well-defined on $\mathbb{Z}_4$ .

Example 7.7: Proving Classes are Equal

Problem: In $\mathbb{Z}_{12}$ , prove that $[17] = [5]$ .

Solution: We need to show $17 \equiv 5 \pmod{12}$ .

$17 - 5 = 12$ , and $12 \mid 12$ . ✓

Therefore $[17] = [5]$ .

Example 7.8: Finding All Classes

Problem: Find all distinct equivalence classes in $\mathbb{Z}_7$ .

Solution: Every integer is congruent to exactly one of $\{0, 1, 2, 3, 4, 5, 6\}$ mod 7.

The distinct classes are:

[0], [1], [2], [3], [4], [5], [6]

There are exactly 7 equivalence classes in $\mathbb{Z}_7$ .

Example 7.9: Equivalence via Function

Problem: Let $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = x^2$ . Define $a \sim b$ iff $f(a) = f(b)$ . Describe the equivalence classes.

Solution: $f(a) = f(b)$ iff $a^2 = b^2$ iff $a = \pm b$ .

The equivalence classes are:

$[0] = \{0\}$
$[r] = \{r, -r\}$ for $r > 0$

Example 7.10: Parallel Lines

Problem: On the set of lines in $\mathbb{R}^2$ , define $\ell_1 \sim \ell_2$ iff $\ell_1 \parallel \ell_2$ (including $\ell \parallel \ell$ ). Is this an equivalence relation?

Solution:

Reflexive: Every line is parallel to itself. ✓
Symmetric: If $\ell_1 \parallel \ell_2$ , then $\ell_2 \parallel \ell_1$ . ✓
Transitive: If $\ell_1 \parallel \ell_2$ and $\ell_2 \parallel \ell_3$ , then $\ell_1 \parallel \ell_3$ (parallel lines have the same slope). ✓

Yes! Each equivalence class consists of all lines with a given slope (a "direction").

8. Common Mistakes

Mistake 1: Forgetting to check all three properties

An equivalence relation must be reflexive, symmetric, AND transitive. Failing any one means it's not an equivalence relation. Always check all three!

Mistake 2: Confusing "transitive" with "if a~b and a~c then b~c"

Transitivity says: if $a \sim b$ AND $b \sim c$ , then $a \sim c$ . The middle element must be the same in both conditions!

Mistake 3: Assuming equivalence classes have equal size

Equivalence classes partition the set, but they need not have equal cardinality. For example, on $\{1, 2, 3, 4, 5\}$ , the partition $\{\{1, 2, 3\}, \{4, 5\}\}$ has classes of size 3 and 2.

Mistake 4: Not verifying well-definedness

When defining a function on a quotient set $f([a])$ , you MUST check that the output doesn't depend on the representative. If $[a] = [b]$ , you need $f([a]) = f([b])$ .

Mistake 5: Writing [a] ∈ [b] instead of [a] = [b]

$[a]$ is a SET. You can have $a \in [b]$ (an element is in a class), but $[a] \in [b]$ is nonsense. If $a \in [b]$ , then $[a] = [b]$ .

9. Key Takeaways

Definition

Equivalence relation = reflexive + symmetric + transitive. It formalizes "sameness up to some property."

Partition Bijection

Equivalence relations ↔ Partitions. The equivalence classes form a partition; every partition defines an equivalence relation.

Quotient Sets

$S/\!\sim$ is the set of equivalence classes. Operations on $S$ that respect $\sim$ induce operations on $S/\!\sim$ .

Linear Algebra Connection

Quotient spaces $V/W$ use the equivalence $v \sim u \iff v - u \in W$ . The dimension drops: $\dim(V/W) = \dim(V) - \dim(W)$ .

Equivalence Relations Practice

Questions

Correct

Accuracy

Which property does the relation '

<

' on

\mathbb{R}

fail to satisfy?

Easy

Not attempted

\mathbb{Z}

, define

a \sim b

iff

a - b

is even. What is

[3]

Easy

Not attempted

\sim

is an equivalence relation on a set

S

with 10 elements, and there are 4 equivalence classes, what can we conclude?

Medium

Not attempted

Which of the following defines an equivalence relation on

\mathbb{R}

Medium

Not attempted

\mathbb{Z}_5

, what is

[7]

(the equivalence class of 7)?

Medium

Not attempted

How many equivalence relations are there on a 3-element set?

Hard

Not attempted

V

is a vector space and

W

a subspace, the relation

v \sim u

iff

v - u \in W

defines equivalence classes of what form?

Hard

Not attempted

Given partition

\{\{1,3,5\}, \{2,4\}, \{6\}\}

\{1,...,6\}

, is

2 \sim 4

Easy

Not attempted

|S| = 4

, how many partitions of

S

are there?

Hard

Not attempted

The relation '

a \mid b

' (divides) on

\mathbb{Z}^+

is:

Medium

Not attempted

[a] = [b]

, which must be true?

Easy

Not attempted

What is the kernel of a homomorphism

\phi: G \to H

as an equivalence relation?

Hard

Not attempted

Frequently Asked Questions

Why are equivalence relations important in linear algebra?

Quotient spaces V/W are constructed using equivalence relations: v ~ u iff v - u ∈ W. The equivalence classes [v] = v + W are the elements of V/W. This construction is fundamental for the First Isomorphism Theorem.

What's the difference between an equivalence class and a partition?

An equivalence class is a single piece of a partition—all elements equivalent to a given element. A partition is the collection of all equivalence classes, which together cover the entire set with no overlaps.

Can an element be in two different equivalence classes?

No! This is a key theorem. If [a] and [b] share any element, then [a] = [b]. Equivalence classes are either identical or disjoint—there's no middle ground.

What's a well-defined function on a quotient set?

A function f: S/∼ → T is well-defined if f([a]) doesn't depend on the representative chosen. If a ~ b, we need f([a]) = f([b]). This is crucial when working with quotient spaces.

How do modular arithmetic and equivalence relations connect?

ℤₙ is the quotient ℤ/nℤ where the equivalence relation is a ~ b iff n | (a-b). The equivalence classes are [0], [1], ..., [n-1]. Addition and multiplication are well-defined on these classes.

What is the Bell number?

The Bell number Bₙ counts the number of partitions (equivalently, equivalence relations) on an n-element set. B₀=1, B₁=1, B₂=2, B₃=5, B₄=15, B₅=52. They grow very rapidly.

What's the difference between equivalence and equality?

Equality is the finest equivalence relation: a ~ b iff a = b. General equivalence relations are 'coarser'—they identify more elements as 'equivalent' even if they're not literally equal.

What is a congruence relation?

A congruence is an equivalence relation that respects algebraic operations. For groups, a ~ b means ab⁻¹ ∈ N for a normal subgroup N. The quotient G/N inherits a group structure.

How do equivalence relations relate to functions?

Every function f: A → B induces an equivalence relation: a ~ a' iff f(a) = f(a'). The equivalence classes are the fibers f⁻¹(b). Conversely, functions on A/~ correspond to functions that are constant on equivalence classes.

What is the quotient topology?

In topology, given an equivalence relation on a space X, the quotient space X/~ has the finest topology making the projection π: X → X/~ continuous. This extends the algebraic quotient to topological spaces.