Sets, Functions, and Equivalence Relations

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 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:

read the set of $a$ in $A$ such that …. The standard number systems recur constantly, so we fix notation for them once:¹

• 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\ne 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

the ambient set inside which relations and functions are defined.

Functions

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)\})$.

Composition

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

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.

Injective, surjective, bijective

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

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.

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$.

A permutation of $A$ is a bijection $A\to A$; permutations of a finite set are the raw material of the symmetric group. 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.

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.

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}$.³ Similarity of matrices ($A\sim B$ when $B=PA{P}^{-1}$ for some invertible $P$) is the equivalence relation whose classes the canonical forms 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$.⁴ Two elements are equivalent precisely when they land on the same point.

Partitions

The complementary notion cuts $A$ into pieces.

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.

The equivalence-partition correspondence

The same disjoint-or-equal argument reappears for cosets and for conjugacy classes.

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:

The quotient set

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

Passing to the quotient treats equivalent elements as identical. Applied to a group by a normal subgroup it produces the quotient group; applied to a ring by an ideal, the quotient ring. 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.

Methods of proof

Algebra is proved, not computed, and a handful of proof shapes cover most of what follows.⁶

• 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 is the model: produce $q$ and $r$, then prove they are forced.
• Contrapositive. $P\Rightarrow Q$ is logically identical to $\neg Q\Rightarrow \neg P$; proving the contrapositive is proving the original. Injectivity, $a_1\ne a_2\Rightarrow f(a_1)\ne f(a_2)$, is usually shown as its contrapositive $f(a_1)=f(a_2)\Rightarrow a_1=a_2$.
• Contradiction. Assume $\neg 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 are almost entirely such two-way statements.