---
title: Sets, Functions, and Equivalence Relations
module: Foundations
moduleNumber: 1
lessonNumber: 1
order: 101
summary: >
  Algebra is built on three prior notions: the set, the map between sets, and
  the equivalence relation that reorganizes a set into disjoint classes. Sets,
  maps (injective, surjective, bijective), fibers and preimages, and the
  correspondence between equivalence relations and partitions — the one
  structural fact reused in every later quotient construction.
topics: [Foundations]
sources:
  - book: Dummit & Foote
    ref: "Ch. 0 — Preliminaries; §0.1 Basics"
  - book: Judson
    ref: "Ch. 1 — Preliminaries; §1.1 A Short Note on Proofs, §1.2 Sets and Equivalence Relations"
draft: false
---

Every algebraic structure in these notes is a set carrying extra operations: a
group is a set with a multiplication, a ring a set with two, a field a ring where
division works. Before any of that come the raw materials: sets, the maps
between them, and one construction that recurs in every later chapter, the
_equivalence relation_. The quotient group, the coset decomposition, and the
residue classes of [modular arithmetic](/abstract-algebra/foundations/integers-and-modular-arithmetic)
are each an equivalence relation with algebraic operations attached.

## Sets and subsets

A **set** is a collection of objects, its **elements**. We write $a \in A$ when
$a$ is an element of $A$ and $a \notin A$ otherwise. A subset is carved out of a
larger set by a condition:

$$
B = \{\, a \in A \mid \text{(conditions on } a\text{)} \,\},
$$

read "the set of $a$ in $A$ such that …". The standard number systems recur
constantly, so we fix notation for them once:[^df-basics]

- **Integers** $\mathbb{Z} = \{0, \pm 1, \pm 2, \dots\}$ (the $\mathbb{Z}$ is for
  the German _Zahlen_).
- **Rationals** $\mathbb{Q} = \{\, a/b \mid a, b \in \mathbb{Z},\ b \neq 0 \,\}$.
- **Reals** $\mathbb{R}$, the complete ordered field of decimal expansions.
- **Complex numbers** $\mathbb{C} = \{\, a + bi \mid a, b \in \mathbb{R},\ i^2 = -1 \,\}$.
- **Positives** $\mathbb{Z}^{+}, \mathbb{Q}^{+}, \mathbb{R}^{+}$, the strictly
  positive elements of each.

The **cardinality** (or **order**) of $A$, written $|A|$, is its number of
elements when $A$ is finite. The **Cartesian product** of $A$ and $B$ is the set
of ordered pairs

$$
A \times B = \{\, (a, b) \mid a \in A,\ b \in B \,\},
$$

the ambient set inside which relations and functions are defined.

## Functions

> **Definition (Function).** A **function** (or **map**) $f : A \to B$ assigns to
> each $a \in A$ a single element $f(a) \in B$. The set $A$ is the **domain**, $B$
> the **codomain**. Notation $f : a \mapsto b$ specifies $f$ on elements:
> $f(a) = b$.

The word "single" matters. When a rule is defined by cases, one must
check it is **well defined**: no element may receive two competing values. If
$A = A_1 \cup A_2$ and one sets $f = 0$ on $A_1$ and $f = 1$ on $A_2$, the
rule is a genuine function exactly when $A_1 \cap A_2 = \varnothing$; an element
in both would be assigned both $0$ and $1$ at once. Well-definedness recurs as an
obligation whenever a later construction defines an operation on classes by
picking representatives.

### Image, preimage, and fibers

Given $f : A \to B$, three derived sets organize everything that follows.

- **Image** (or **range**): $f(A) = \{\, b \in B \mid b = f(a) \text{ for some } a \in A \,\}$,
  the elements of $B$ actually hit.
- **Preimage** of a subset $C \subseteq B$: $f^{-1}(C) = \{\, a \in A \mid f(a) \in C \,\}$,
  everything mapping into $C$.
- **Fiber** over a point $b \in B$: the preimage $f^{-1}(\{b\})$ of a single point,
  the set of all $a$ with $f(a) = b$.

The notation $f^{-1}$ here denotes the preimage operation on subsets and does not
assert that $f$ has an inverse function. A fiber can be empty (when $b$ is not in
the image) or large (when many elements share a value). The key structural fact,
used constantly, is that the nonempty fibers of $f$ **partition** the domain: every
$a \in A$ lies in exactly one fiber, namely $f^{-1}(\{f(a)\})$.

$$
% caption: A map sends each domain element to one codomain element; the fiber over $b_1$ collects every element landing on $b_1$, and the fibers tile the domain into disjoint blocks.
\begin{tikzpicture}[>=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
% domain oval
\draw[black] (0,0) ellipse (1.55 and 2.7);
\node[anchor=south, font=\footnotesize] at (0,2.8) {domain $A$};
% codomain oval
\draw[black] (6,0) ellipse (1.25 and 2.7);
\node[anchor=south, font=\footnotesize] at (6,2.8) {codomain $B$};
% fiber-over-b1 highlight in the domain
\draw[acc, dashed] (-0.7,0.55) rectangle (0.7,2.25);
\node[acc, anchor=east, font=\footnotesize] at (-0.8,1.4) {preimage of $b_1$};
% domain points
\coordinate (a1) at (0,1.85);
\coordinate (a2) at (0,1.0);
\coordinate (a3) at (0,0.05);
\coordinate (a4) at (0,-1.0);
\coordinate (a5) at (0,-1.85);
\foreach \p in {a1,a2,a3,a4,a5} \fill[acc] (\p) circle (2.2pt);
% codomain points
\coordinate (b1) at (6,1.35);
\coordinate (b2) at (6,0.0);
\coordinate (b3) at (6,-1.35);
\foreach \p in {b1,b2,b3} \fill[black] (\p) circle (2.2pt);
\node[anchor=west, font=\footnotesize] at (6.2,1.35) {$b_1$};
\node[anchor=west, font=\footnotesize] at (6.2,0.0) {$b_2$};
\node[anchor=west, font=\footnotesize] at (6.2,-1.35) {$b_3$};
% arrows
\draw[->, acc] (a1) -- (b1);
\draw[->, acc] (a2) -- (b1);
\draw[->, acc] (a3) -- (b2);
\draw[->, acc] (a4) -- (b3);
\draw[->, acc] (a5) -- (b3);
\end{tikzpicture}
$$

### Composition

If $f : A \to B$ and $g : B \to C$, the **composite** $g \circ f : A \to C$ is

$$
(g \circ f)(a) = g\bigl(f(a)\bigr).
$$

Composition reads right to left: apply $f$, then $g$. It is associative,
$h \circ (g \circ f) = (h \circ g) \circ f$, because both sides send $a$ to
$h(g(f(a)))$. This lets us draw the situation as a diagram and speak of it
**commuting**: every directed path between two nodes computes the same map.

$$
% caption: The composition triangle. The diagonal $g \circ f$ equals "go along $f$, then $g$"; the triangle commutes because both routes from $A$ to $C$ agree on every element.
\begin{tikzpicture}[>=stealth, font=\small,
  nd/.style={circle, draw, minimum size=8mm, inner sep=1pt}]
\definecolor{acc}{HTML}{4A6FA5}
\node[nd] (A) at (0,0) {$A$};
\node[nd] (B) at (3.2,2.0) {$B$};
\node[nd] (C) at (6.4,0) {$C$};
\draw[->, acc, thick] (A) -- (B) node[midway, above left, font=\footnotesize] {$f$};
\draw[->, acc, thick] (B) -- (C) node[midway, above right, font=\footnotesize] {$g$};
\draw[->, black, thick] (A) -- (C) node[midway, below, font=\footnotesize] {composite};
\end{tikzpicture}
$$

### Injective, surjective, bijective

The three ways a map can be well behaved control when it can be inverted.

> **Definition (Injective, surjective, bijective).** Let $f : A \to B$.
> $f$ is **injective** (an injection) if $a_1 \neq a_2$ forces
> $f(a_1) \neq f(a_2)$; equivalently every fiber has at most one element.
> $f$ is **surjective** (a surjection) if its image is all of $B$; every fiber is
> nonempty. $f$ is **bijective** (a bijection) if it is both, so every fiber has
> exactly one element.

Injectivity depends only on the rule; surjectivity depends on the declared
codomain, since a function always maps onto its range by definition. This is why
$B$ must be specified for the question of surjectivity to mean anything.

$$
% caption: Injective misses some targets but never doubles up; surjective covers every target but may double up; bijective is a perfect pairing, one arrow into each codomain point.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% ---- injective ----
\begin{scope}
  \node[font=\small] at (1.0,2.5) {injective};
  \draw[black] (0.15,0) ellipse (0.55 and 1.9);
  \draw[black] (1.85,0) ellipse (0.55 and 1.9);
  \foreach \y in {1.2,0.2,-0.8} \fill[acc] (0.15,\y) circle (2pt);
  \foreach \y in {1.5,0.7,-0.1,-0.9,-1.5} \fill[black] (1.85,\y) circle (2pt);
  \draw[->, acc] (0.15,1.2) -- (1.85,1.5);
  \draw[->, acc] (0.15,0.2) -- (1.85,0.7);
  \draw[->, acc] (0.15,-0.8) -- (1.85,-0.9);
\end{scope}
% ---- surjective ----
\begin{scope}[xshift=4.4cm]
  \node[font=\small] at (1.0,2.5) {surjective};
  \draw[black] (0.15,0) ellipse (0.55 and 1.9);
  \draw[black] (1.85,0) ellipse (0.55 and 1.9);
  \foreach \y in {1.5,0.7,-0.1,-0.9,-1.5} \fill[acc] (0.15,\y) circle (2pt);
  \foreach \y in {1.0,0.0,-1.0} \fill[black] (1.85,\y) circle (2pt);
  \draw[->, acc] (0.15,1.5) -- (1.85,1.0);
  \draw[->, acc] (0.15,0.7) -- (1.85,1.0);
  \draw[->, acc] (0.15,-0.1) -- (1.85,0.0);
  \draw[->, acc] (0.15,-0.9) -- (1.85,-1.0);
  \draw[->, acc] (0.15,-1.5) -- (1.85,-1.0);
\end{scope}
% ---- bijective ----
\begin{scope}[xshift=8.8cm]
  \node[font=\small] at (1.0,2.5) {bijective};
  \draw[black] (0.15,0) ellipse (0.55 and 1.9);
  \draw[black] (1.85,0) ellipse (0.55 and 1.9);
  \foreach \y in {1.1,0.1,-0.9} \fill[acc] (0.15,\y) circle (2pt);
  \foreach \y in {1.1,0.1,-0.9} \fill[black] (1.85,\y) circle (2pt);
  \draw[->, acc] (0.15,1.1) -- (1.85,1.1);
  \draw[->, acc] (0.15,0.1) -- (1.85,0.1);
  \draw[->, acc] (0.15,-0.9) -- (1.85,-0.9);
\end{scope}
\end{tikzpicture}
$$

Inverses match this classification exactly. A **left inverse** is $g : B \to A$
with $g \circ f = \mathrm{id}_A$; a **right inverse** is $h : B \to A$ with
$f \circ h = \mathrm{id}_B$.

> **Proposition (Inverses classify maps).** Let $f : A \to B$. Then $f$ is
> injective if and only if it has a left inverse; $f$ is surjective if and only if
> it has a right inverse; and $f$ is bijective if and only if there is a single
> $g : B \to A$ with $f \circ g = \mathrm{id}_B$ and $g \circ f = \mathrm{id}_A$.
> This two-sided $g$ is unique, the **inverse** of $f$, written $f^{-1}$.[^df-prop1]

A **permutation** of $A$ is a bijection $A \to A$; permutations of a finite set
are the raw material of the [symmetric group](/abstract-algebra/groups-and-symmetry/dihedral-and-symmetric-groups).
When $A$ and $B$ are finite with $|A| = |B|$, the three conditions collapse: for
such sets $f$ is bijective if and only if it is injective if and only if it is
surjective. The pigeonhole principle forbids an injection from missing a target or
a surjection from doubling up when the counts match.

> **Worked example.** Let $f : \{1,2,3,4,5,6\} \to \{a, b, c\}$ be given by
>
> $$
> f(1) = a,\quad f(2) = b,\quad f(3) = a,\quad f(4) = c,\quad f(5) = b,\quad f(6) = a.
> $$
>
> The image $\{a, b, c\}$ is all of the codomain, so $f$ is surjective; it is not
> injective, since $f(1) = f(3) = a$ with $1 \neq 3$. The three nonempty fibers
>
> $$
> f^{-1}(\{a\}) = \{1, 3, 6\},\qquad f^{-1}(\{b\}) = \{2, 5\},\qquad f^{-1}(\{c\}) = \{4\}
> $$
>
> are pairwise disjoint and cover the domain, partitioning $\{1,\dots,6\}$ into one
> block per value hit.

## Relations and equivalence

A **binary relation** on $A$ is a subset $R \subseteq A \times A$; we write
$a \sim b$ to mean $(a, b) \in R$. Most relations are structureless. Three
axioms single out the ones that behave like a generalized equality.

> **Definition (Equivalence relation).** A relation $\sim$ on $A$ is an
> **equivalence relation** if it is
> - **reflexive**: $a \sim a$ for all $a$;
> - **symmetric**: $a \sim b$ implies $b \sim a$;
> - **transitive**: $a \sim b$ and $b \sim c$ imply $a \sim c$.
>
> The **equivalence class** of $a$ is $[a] = \{\, x \in A \mid x \sim a \,\}$. Any
> member of a class is a **representative** of it.

Equality itself is the tightest example, with singleton classes. Loosening it
gives the constructions used throughout algebra. Congruence modulo $n$ declares
$a \sim b$ when $n \mid (b - a)$; its classes are the residue classes that become
$\mathbb{Z}/n\mathbb{Z}$.[^judson-cong] Similarity of matrices ($A \sim B$ when
$B = PAP^{-1}$ for some invertible $P$) is the equivalence relation whose classes
the [canonical forms](/abstract-algebra/modules-over-pids/rational-canonical-form)
lesson classifies. Even the rationals are an equivalence class construction:
$a/b$ names the class of pairs $(a, b)$ under $(p, q) \sim (r, s)$ when $ps = qr$,
which is why $1/2$ and $2/4$ denote the same number.

### Fibers as an equivalence relation

Fibers and equivalence classes are two views of one construction. Given any
surjection $f : A \to B$, define $a_1 \sim a_2$ when $f(a_1) = f(a_2)$. This is
reflexive (values equal themselves), symmetric, and transitive because ordinary
equality is, so $\sim$ is an equivalence relation, and each of its classes is a
fiber of $f$.[^df-fiber] Two elements are equivalent precisely when they land
on the same point.

## Partitions

The complementary notion cuts $A$ into pieces.

> **Definition (Partition).** A **partition** of $A$ is a collection
> $\{A_i\}_{i \in I}$ of nonempty subsets that are pairwise disjoint
> ($A_i \cap A_j = \varnothing$ for $i \neq j$) and cover $A$ ($\bigcup_i A_i = A$).
> Equivalently, $A$ is the **disjoint union** of the blocks $A_i$.

A partition sorts the elements of $A$ into bins so that every
element lands in exactly one bin. Partitions and equivalence relations are the
same data, a correspondence the next theorem makes precise.

$$
% caption: An equivalence relation cuts a set into disjoint classes that cover it; the classes are the blocks of a partition, one bin per class, every element in exactly one bin.
\begin{tikzpicture}[>=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
% outer boundary of the set X
\draw[black, thick] (0,0) rectangle (9,4);
\node[anchor=south west, font=\footnotesize] at (0.05,4.05) {a set $X$};
% partition lines
\draw[black] (3,0) -- (3,4);
\draw[black] (3,2.1) -- (0,2.1);
\draw[black] (5.6,0) -- (5.6,4);
\draw[black] (5.6,1.6) -- (9,1.6);
\draw[black] (3,2.7) -- (5.6,2.7);
% class fills (light tints) and labels
\fill[acc!12] (0.05,2.15) rectangle (2.95,3.95);
\node at (1.5,3.05) {$[a]$};
\fill[acc!12] (0.05,0.05) rectangle (2.95,2.05);
\node at (1.5,1.05) {$[b]$};
\fill[acc!12] (3.05,2.75) rectangle (5.55,3.95);
\node at (4.3,3.35) {$[c]$};
\fill[acc!12] (3.05,0.05) rectangle (5.55,2.65);
\node at (4.3,1.35) {$[d]$};
\fill[acc!12] (5.65,1.65) rectangle (8.95,3.95);
\node at (7.3,2.8) {$[e]$};
\fill[acc!12] (5.65,0.05) rectangle (8.95,1.55);
\node at (7.3,0.8) {$[f]$};
\end{tikzpicture}
$$

### The equivalence-partition correspondence

> **Theorem (Equivalence-partition correspondence).** Let $A$ be a nonempty set.
> If $\sim$ is an equivalence relation on $A$, its equivalence classes form a
> partition of $A$. Conversely, given a partition $\{A_i\}$ of $A$, declaring two
> elements equivalent when they lie in the same block defines an equivalence
> relation whose classes recover the original blocks $A_i$. The two constructions are mutually
> inverse.[^df-prop2]

The same disjoint-or-equal
argument reappears for [cosets](/abstract-algebra/subgroups-and-quotients/cosets-lagrange-and-normal-subgroups)
and for [conjugacy classes](/abstract-algebra/group-actions-and-sylow/conjugation-and-the-class-equation).

**From a relation to a partition.** Reflexivity gives $a \in [a]$, so each class is
nonempty and the classes cover $A$. It remains to show two classes are either
identical or disjoint. Suppose $[a]$ and $[b]$ share an element $z$, so $z \sim a$
and $z \sim b$. By symmetry and transitivity $a \sim b$. Now for any $x \in [a]$
we have $x \sim a \sim b$, so $x \in [b]$, giving $[a] \subseteq [b]$; the reverse
inclusion is identical. Hence overlapping classes coincide, and distinct classes
are disjoint — a partition.

**From a partition back to a relation.** Define $x \sim y$ when $x$ and $y$ share a
block. Reflexivity, symmetry, and transitivity all hold because "same block" is
inherited from equality of the block index. The classes of this relation are the
blocks. Starting from an equivalence relation, extracting its classes, and reading
off the induced relation returns the original relation, so the correspondence is a
bijection between equivalence relations on $A$ and partitions of $A$.

An immediate corollary, used constantly below:

> **Corollary.** Two equivalence classes of the same relation are either disjoint
> or equal. There is no partial overlap.

> **Worked example.** Define $\sim$ on $\mathbb{Z}$ by $a \sim b$ when
> $4 \mid (b - a)$. It is reflexive ($4 \mid 0$), symmetric ($4 \mid (b - a)$ gives
> $4 \mid (a - b)$), and transitive ($4 \mid (b - a)$ and $4 \mid (c - b)$ sum to
> $4 \mid (c - a)$), so $\sim$ is an equivalence relation. Every integer is
> congruent to its remainder on division by $4$, so there are four classes
>
> $$
> [0] = \{\dots, -4, 0, 4, \dots\},\quad [1],\quad [2],\quad [3],
> $$
>
> and each integer lies in exactly one. These four blocks are the partition of
> $\mathbb{Z}$ that underlies $\mathbb{Z}/4\mathbb{Z}$.

### The quotient set

Once the classes are recognized as objects in their own right, they form a new
set.

> **Definition (Quotient set).** The set of equivalence classes of $\sim$ on $A$
> is the **quotient** $A / {\sim}$, and the map $\pi : A \to A/{\sim}$ sending
> $a \mapsto [a]$ is the **canonical projection** (or quotient map). It is
> surjective, and its fibers are the classes.

Passing to the quotient treats equivalent elements as identical. Applied to a
group by a normal subgroup it produces the
[quotient group](/abstract-algebra/subgroups-and-quotients/cosets-lagrange-and-normal-subgroups);
applied to a ring by an ideal, the
[quotient ring](/abstract-algebra/ring-theory/ideals-quotients-and-homomorphisms).
Both are the construction above with algebraic operations lifted from
representatives to classes, and the lifting is well defined for the same reason
the modular sum was: the relation is compatible with the operation.

| Object | Set-theoretic name | Algebraic instance |
| --- | --- | --- |
| $\sim$ | equivalence relation | congruence mod $n$; conjugacy; similarity |
| $[a]$ | equivalence class | residue class; coset; conjugacy class |
| $A/{\sim}$ | quotient set | $\mathbb{Z}/n\mathbb{Z}$; quotient group; quotient ring |
| $\pi : a \mapsto [a]$ | canonical projection | reduction mod $n$; the quotient homomorphism |

## Methods of proof

Algebra is proved, not computed, and a handful of proof shapes cover most of what
follows.[^judson-proofs]

- **Direct proof.** To show $P \Rightarrow Q$, assume $P$ and deduce $Q$. The
  equivalence-class inclusions above are direct.
- **Existence and uniqueness.** To specify an object uniquely, first exhibit one (or
  construct it), then show any two candidates coincide. The
  [division algorithm](/abstract-algebra/foundations/integers-and-modular-arithmetic)
  is the model: produce $q$ and $r$, then prove they are forced.
- **Contrapositive.** $P \Rightarrow Q$ is logically identical to
  $\lnot Q \Rightarrow \lnot P$; proving the contrapositive is proving the
  original. Injectivity, "$a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$", is
  usually shown as its contrapositive "$f(a_1) = f(a_2) \Rightarrow a_1 = a_2$".
- **Contradiction.** Assume $\lnot Q$ alongside $P$ and derive an impossibility.
- **Induction.** Prove a base case, then that each case forces the next.

Two hygiene rules recur. Whenever an operation is defined on classes by acting on
representatives, one must check it is **well defined**, independent of the
representative chosen. And an "if and only if" is two proofs, one in each
direction; the [isomorphism theorems](/abstract-algebra/subgroups-and-quotients/isomorphism-theorems)
are almost entirely such two-way statements.

[^df-basics]: **Dummit & Foote**, _Abstract Algebra_, §0.1 — Basics: set-builder notation, cardinality, the Cartesian product, and the standard number systems $\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$, together with the well-definedness obligation for functions specified by cases.
[^df-prop1]: **Dummit & Foote**, _Abstract Algebra_, §0.1, Proposition 1 — a map has a left inverse iff injective, a right inverse iff surjective, and a unique two-sided inverse iff bijective; for finite sets of equal cardinality, injective, surjective, and bijective coincide.
[^judson-cong]: **Judson**, _Abstract Algebra: Theory and Applications_, §1.2 — congruence modulo $n$ presented as an equivalence relation on $\mathbb{Z}$, with $[0], [1], \dots, [n-1]$ shown to partition the integers.
[^df-fiber]: **Dummit & Foote**, _Abstract Algebra_, §0.1, Exercise 7 — for a surjection $f$, the relation $a \sim b \iff f(a) = f(b)$ is an equivalence relation whose classes are the fibers of $f$.
[^df-prop2]: **Dummit & Foote**, _Abstract Algebra_, §0.1, Proposition 2; **Judson**, §1.2, Theorem 1.5 and Corollary 1.6 — the equivalence between equivalence relations on a set and partitions of it, with the disjoint-or-equal property of classes.
[^judson-proofs]: **Judson**, _Abstract Algebra: Theory and Applications_, §1.1 — A Short Note on Proofs: direct proof, proof by contrapositive and contradiction, existence-and-uniqueness arguments, and the role of induction.
</content>
</invoke>