Equivalence Relations and Partitions

Introduction

The notion of equality is central to mathematics, but often we wish to consider objects as equivalent when they share certain properties, even if they are not identical. Equivalence relations formalize this idea, providing a rigorous way to treat different objects as being the same in some specified sense.

When we say two fractions are equivalent (1/2=2/4), or two geometric figures are congruent, or two integers have the same remainder upon division by n we are invoking equivalence relations. This concept is fundamental throughout mathematics, from abstract algebra to topology.

Relations

A relation R on a set A is a subset of the Cartesian product A×A If (a,b)∈R we say that a is related to b and write a*R*b or a∼b

Definition of Equivalence Relation

A relation ∼ on a set A is an equivalence relation if it satisfies three properties for all a,b,c∈A

Reflexivity

a∼a

Every element is equivalent to itself.

Symmetry

a∼b⟹b∼a

If a is equivalent to b then b is equivalent to a

Transitivity

a∼b* and *b∼c⟹a∼c

If a is equivalent to b and b is equivalent to c then a is equivalent to c

Equivalence Classes

Given an equivalence relation ∼ on a set A and an element a∈A the equivalence class of a is the set of all elements equivalent to a

[a]={x∈A:x∼a}

The element a is called a representative of the class [a] By reflexivity, a∈[a] so every equivalence class is nonempty.

Properties of Equivalence Classes

Two elements have the same equivalence class if and only if they are equivalent: [a]]=[[*b]⟺a∼b

Two equivalence classes are either identical or disjoint: [a]]=[[*b] or [a]]∩[[*b]=∅ There is no middle ground.

The union of all equivalence classes equals A every element belongs to exactly one equivalence class.

Partitions

A partition of a set A is a collection 𝒫={(A_i)}(i∈I) of nonempty subsets of A such that:

The subsets are pairwise disjoint: (A_i)∩(A_j)=∅ for i≠j

The subsets cover A (⋃_i∈I^)((A_i))=A

The subsets (A_i) are called the parts or blocks of the partition.

The Fundamental Theorem

There is a natural bijection between equivalence relations on a set and partitions of that set.

Given an equivalence relation ∼ on A the collection of equivalence classes forms a partition of A

Conversely, given a partition 𝒫 of A define a∼b if and only if a and b belong to the same part. This defines an equivalence relation whose equivalence classes are exactly the parts of 𝒫

Quotient Sets

The quotient set (or quotient space) of A by an equivalence relation ∼ is the set of all equivalence classes:

A/∼={[a]:∈A}

For congruence modulo n, the quotient set is ℤ/n*ℤ={[0],[1],…,[n-1]}, which has n elements.

The canonical projection π:A→A/∼ defined by π*(a)=[a] sends each element to its equivalence class. This map is surjective.

Well-Defined Operations on Quotients

When defining operations on a quotient set, we must ensure they are well-defined, meaning the result depends only on the equivalence class and not on the choice of representative.

For ℤ/n*ℤ we define addition and multiplication by [a]]+[[*b]]=[[*a+b] and [a]]⋅[[*b]]=[[*a⋅b] To verify well-definedness, suppose [a]=[a′] and [b]=[b′]. Then a≡a′*(mod(n)) and b≡b′*(mod(n)) so a+b≡a′+b′*(mod(n)) confirming [a+b]=[a′+b′]

Equivalence Relations in Algebra

Equivalence relations that are compatible with algebraic operations lead to quotient structures in abstract algebra.

A congruence on a group G is an equivalence relation ∼ such that a∼a′ and b∼b′ imply a*b∼a′b′. Such relations correspond exactly to normal subgroups, and the quotient is the quotient group.

Similarly, congruences on rings correspond to ideals, yielding quotient rings.

Counting Equivalence Classes

The number of equivalence classes in a finite set can be computed using the orbit-counting theorem (Burnside's lemma) in cases arising from group actions.

For an equivalence relation with k equivalence classes of sizes (n_1),(n_2),…,(n_k) we have |A|=(n_1)+(n_2)+⋯+(n_k)

Generating Equivalence Relations

Given any relation R on a set A there is a smallest equivalence relation containing R called the equivalence relation generated by R It is constructed by taking the reflexive, symmetric, and transitive closure of R

Explicitly, a∼b in the generated equivalence relation if there is a chain a=(x_0),(x_1),…,(x_n)=b where each consecutive pair is related by R or R(−1) (including a=b.

Applications

Equivalence relations appear throughout mathematics whenever we want to identify objects that are the same in some respect.

In topology, the quotient space construction uses equivalence relations to glue points together. The torus, for example, arises from identifying opposite edges of a square.

In linear algebra, the dimension of a vector space can be defined using equivalence classes of bases.

In logic, logical equivalence (p↔q) is an equivalence relation on propositions.

Summary

An equivalence relation on a set A is a relation that is reflexive, symmetric, and transitive. Each equivalence relation partitions A into disjoint equivalence classes, and conversely, every partition determines an equivalence relation.

The quotient set A/∼ collects all equivalence classes into a new set. Operations on the quotient must be well-defined, depending only on equivalence classes and not on representatives.

Common examples include congruence modulo n on the integers, equivalence of fractions defining the rationals, and similarity of matrices in linear algebra.

Equivalence relations provide a rigorous way to treat different objects as identical when they share relevant properties, forming the foundation for quotient constructions throughout algebra, topology, and analysis.