00.02.06 · precalc / set-and-function

Sets, relations, and functions — the language of mathematics

shipped3 tiersLean: none

Anchor (Master): Halmos 1960 Naive Set Theory (Van Nostrand) §§1–7; Enderton 1977 Elements of Set Theory (Academic Press) Ch. 1–6 (full proofs)

Intuition Beginner

Mathematics has a grammar, just as English does. Three families of words do most of the work, and this unit teaches them together.

A set is a collection. Your pencil case is a set of pens. The days of the week are a set of seven names. A set gathers distinct things and treats them as a single object, so we can reason about the whole collection at once.

A relation is a way things can be connected. "Is taller than" links two people. "Has the same birthday month as" links other pairs. A relation lists which pairs are linked and which are not, nothing more.

A function is a dependable rule. Each input gives exactly one output. Doubling, squaring, and "add three" are functions. You met functions in the previous unit; here we widen the lens to the whole grammar that surrounds them.

Why care? Because nearly every idea in mathematics is built from these three notions. A vector space is a set with structure. A group is a set with a function. An equation asks when two functions agree. Learn these words now and every later unit reads more smoothly.

Visual Beginner

Three overlapping circles show how sets combine. The shaded region is the answer to each operation.

The four set operations in one table, using $A = {1, 2, 3}$ and $B = {2, 3, 4}$ :

Operation	In words	Result
Union $A \cup B$	everything in either	${1, 2, 3, 4}$
Intersection $A \cap B$	only what is in both	${2, 3}$
Difference $A ∖ B$	in $A$ but not in $B$	${1}$
Complement $A^{c}$	everything not in $A$	depends on the universe

Worked example Beginner

This is the deep idea of the unit, made small enough to hold in your hand.

Take the nine numbers $0, 1, 2, 3, 4, 5, 6, 7, 8$ . Link two numbers when they leave the same remainder after division by $3$ . Then sort the nine numbers by their remainder:

Remainder $0$ : the numbers $0, 3, 6$
Remainder $1$ : the numbers $1, 4, 7$
Remainder $2$ : the numbers $2, 5, 8$

The nine numbers fall into three non-overlapping groups. Every number lands in exactly one group. Together the three groups rebuild the whole set, with nothing left over and nothing counted twice.

This is called a partition. The link "same remainder by $3$ " is an equivalence relation, and its three groups are its equivalence classes. A partition and an equivalence relation are two views of the same structure. That single sentence is the heart of the unit.

Check your understanding Beginner

Formal definition Intermediate+

A set $A$ is a collection of distinct objects called its elements, written $a \in A$ when $a$ belongs to $A$ . The set with no elements is the empty set $\emptyset$ . A set $S$ is a subset of $A$ , written $S \subseteq A$ , when every element of $S$ also lies in $A$ . The power set $P (A)$ is the set of all subsets of $A$ .

Fix a universal set $U$ containing both $A$ and $B$ . The four operations combine sets as follows:

A \cup B = {x \in U : x \in A or x \in B}, A \cap B = {x \in U : x \in A and x \in B},

A ∖ B = {x \in U : x \in A and x \in / B}, A^{c} = U ∖ A = {x \in U : x \in / A} .

De Morgan's laws tie these operations together: $(A \cup B)^{c} = A^{c} \cap B^{c}$ and $(A \cap B)^{c} = A^{c} \cup B^{c}$ . They express the symmetry between "or" and "and" under negation ^[Enderton].

The Cartesian product of $A$ and $B$ bundles one element from each into an ordered pair:

A \times B = {(a, b) : a \in A, b \in B} .

Order matters: $(a, b) \neq = (b, a)$ in general, and $A \times B \neq = B \times A$ in general. The product is the substrate on which relations and functions are built.

A relation $R$ from $A$ to $B$ is a subset $R \subseteq A \times B$ . When $(a, b) \in R$ we write $a R b$ . A relation on a single set $A$ is a subset of $A \times A$ . Four properties recur throughout mathematics. A relation $R$ on $A$ is:

reflexive if $(a, a) \in R$ for every $a \in A$ ;
symmetric if $(a, b) \in R$ implies $(b, a) \in R$ ;
antisymmetric if $(a, b) \in R$ and $(b, a) \in R$ together imply $a = b$ ;
transitive if $(a, b) \in R$ and $(b, c) \in R$ together imply $(a, c) \in R$ .

A relation that is reflexive, symmetric, and transitive is an equivalence relation, conventionally written $\sim$ . An equivalence relation generalises equality: two related elements are "the same" for whatever purpose $\sim$ encodes. A partition of $A$ is a family ${P_{i}}_{i \in I}$ of non-empty, pairwise disjoint subsets of $A$ whose union is all of $A$ .

A function $f : A \to B$ , recalled from 00.02.05, is a relation $f \subseteq A \times B$ in which each $a \in A$ occurs in exactly one pair $(a, b)$ . The set $A$ is the domain, $B$ the codomain. A function is injective if distinct inputs give distinct outputs, surjective if every element of $B$ is hit, and bijective if it is both. The composition of $g : B \to C$ after $f : A \to B$ is $(g \circ f) (a) = g (f (a))$ .

Key theorem with proof Intermediate+

Theorem (equivalence relations and partitions). Let $A$ be a non-empty set. Every equivalence relation on $A$ determines a unique partition of $A$ , and every partition of $A$ determines a unique equivalence relation. These two constructions are mutually inverse.

Proof. Given an equivalence relation $\sim$ on $A$ , define the equivalence class of $a \in A$ by

[a] = {x \in A : x \sim a} .

Each class is non-empty, because reflexivity gives $a \sim a$ , so $a \in [a]$ . Since every element lies in its own class, the union of all classes is $A$ . It remains to show that two classes are either identical or disjoint.

Suppose two classes meet: $[a] \cap [b] \neq = \emptyset$ . Choose $c \in [a] \cap [b]$ , so $c \sim a$ and $c \sim b$ . By symmetry $a \sim c$ , and by transitivity $a \sim c$ together with $c \sim b$ gives $a \sim b$ . Now if $x \in [a]$ , then $x \sim a$ and $a \sim b$ give $x \sim b$ , so $x \in [b]$ ; this shows $[a] \subseteq [b]$ . The reverse inclusion follows by the same argument with $a$ and $b$ swapped. Hence $[a] = [b]$ whenever the classes meet, so distinct classes are disjoint. The classes therefore form a partition.

Conversely, given a partition ${P_{i}}_{i \in I}$ of $A$ , define $a \sim b$ when $a$ and $b$ lie in the same part $P_{i}$ . Reflexivity holds because $a$ lies in exactly one part. Symmetry holds because equality of parts is symmetric. Transitivity holds because if $a$ and $b$ share a part and $b$ and $c$ share a part, that part is the same (the parts are disjoint), so $a$ and $c$ share it. The two constructions undo each other: the classes of the relation induced by a partition are exactly the original parts. $□$

This bijection is the load-bearing result of the unit: to specify an equivalence relation is precisely to specify a partition, and conversely.

Bridge. This theorem builds toward the quotient constructions of linear algebra 01.01.03 and group theory 01.02.01, where a subspace or a normal subgroup defines an equivalence relation and the classes themselves become the elements of a new algebraic object. The same partition idea appears again in the construction of the integers from pairs of natural numbers, the rationals from pairs of integers, and the real numbers from Cauchy sequences of rationals. The central insight is that "declaring equivalent elements equal" is a single operation that generalises across algebra, topology, and analysis: putting these together, the bridge is that every quotient space, every modular arithmetic, and every isomorphism theorem is an equivalence relation wearing the costume of its field.

Exercises Intermediate+

Exercise 5 (medium, short-answer).

Determine whether $f (x) = x^{2}$ is injective and surjective as a function $R \to R$ . Then answer the same two questions for $f : [0, \infty) \to [0, \infty)$ with $f (x) = x^{2}$ . Which version is a bijection?

Hint

For injectivity, look for two different inputs giving the same square. For surjectivity, ask whether every target value is reached.

Answer

On $R \to R$ : $f$ is not injective because $f (2) = f (- 2) = 4$ ; $f$ is not surjective because no real square is negative. On $[0, \infty) \to [0, \infty)$ : $f$ is injective (squaring is strictly increasing on non-negative reals) and surjective (every $y \geq 0$ is $(y)^{2}$ ), so it is a bijection. Restricting the domain and codomain turned a non-invertible map into an invertible one.

Rubric: full credit for both injectivity verdicts, both surjectivity verdicts, and the bijection identification.

Exercise 7 (hard, short-answer).

Define $a \sim b$ on the integers by $5 ∣ (a - b)$ (5 divides $a - b$ ). Prove that $\sim$ is an equivalence relation, describe its equivalence classes, and state how many there are.

Hint

Divisibility of differences is reflexive ( $a - a = 0$ ), and it is preserved under sign changes and sums.

Answer

Reflexive: $a - a = 0$ and $5 ∣ 0$ . Symmetric: if $5 ∣ (a - b)$ then $5 ∣ - (a - b) = b - a$ . Transitive: if $5 ∣ (a - b)$ and $5 ∣ (b - c)$ , then $5$ divides their sum $(a - b) + (b - c) = a - c$ . So $\sim$ is an equivalence relation. The classes are the congruence classes modulo $5$ :

[0] = {\dots, - 5, 0, 5, 10, \dots}, [1] = {\dots, - 4, 1, 6, \dots}, [2], [3], [4],

five classes in total, one per remainder $0, 1, 2, 3, 4$ .

Rubric: full credit for the three-property proof, the description of the classes, and the count five.

Lean formalization Intermediate+

This unit ships with lean_status: none. The precalculus layer is prose-elementary: the quality gate is the worked-example exposition and the partition–equivalence-relation proof, not a Lean formalization. The underlying objects are nevertheless fully formalisable in Mathlib, and a companion module would make the bridge concrete.

In Mathlib, set operations live in the Set namespace (Set.union, Set.inter, Set.diff, Set.compl, Set.powerset), Cartesian products in Set.prod, and bijections in Equiv with composition and inverses built in. Equivalence relations are captured by Setoid together with Quotient, and the correspondence between equivalence relations and partitions is available through Setoid.quotient and supporting lemmas about classes. A future companion module under Codex.Precalc.SetAndFunction could port the mod-3 worked example and the congruence-mod-5 exercise into Lean, mirroring the formal treatment already shipped in 00.02.05.

Advanced results Master

The power set $P (A)$ collects every subset of $A$ . For a finite set with $n$ elements, $∣ P (A) ∣ = 2^{n}$ , so the power set is always larger than $A$ itself. Cantor's cornerstone result says this growth never stops, even for infinite sets: no set is in bijection with its own power set.

Theorem (Cantor). For every set $A$ , there is no surjection $A \to P (A)$ . Consequently $∣ A ∣ < ∣ P (A) ∣$ .

The argument is short and diagonal. Given any function $f : A \to P (A)$ , form the set $D = {a \in A : a \in / f (a)}$ , which is itself an element of $P (A)$ . If $D = f (b)$ for some $b \in A$ , then asking whether $b$ belongs to $D$ produces the contradiction $b \in f (b) ⟺ b \in / f (b)$ . So $D$ escapes the image of $f$ , and $f$ was never surjective. The full proof appears in the proof set below. Cantor's theorem is the engine of the hierarchy of infinite cardinals and the seed of the undecidability results studied much later in the curriculum.

A second master-level theme is the lattice of partitions. The set of all equivalence relations on $A$ is partially ordered by refinement: write $\sim_{1} ⪯ \sim_{2}$ when every $\sim_{1}$ -class is contained in a $\sim_{2}$ -class, that is, when $a \sim_{1} b$ implies $a \sim_{2} b$ . Under this order the equivalence relations form a lattice. The meet of two relations is their intersection; the join is the transitive closure of their union (equivalently, the smallest equivalence relation containing both). The least element is equality, the finest partition into singletons; the greatest element is the universal relation $A \times A$ , the coarsest partition with one class. This lattice is the backbone of every quotient construction across algebra, and the same shape reappears for subgroups, subspaces, and topologies.

The Cantor–Bernstein–Schröder theorem supplies the cardinality comparison test: if there is an injection $A \to B$ and an injection $B \to A$ , then there is a bijection $A \to B$ . Stated without proof here, it lets us compare infinite sizes without ever constructing an explicit bijection, and together with Cantor's theorem it organises the infinite cardinals into a linear hierarchy.

Synthesis. Sets, relations, and functions are the grammar of mathematics, and this unit assembles them into a single working language. Sets collect the objects under study; relations describe how those objects stand to one another; functions are the special single-valued relations that transform one structure into another. Equivalence relations generalise the notion of equality, and the foundational reason quotients exist is that every equivalence relation partitions its set; the central insight of modern algebra is that these partitions inherit structure from the parent. This is exactly the mechanism behind quotient groups, quotient vector spaces, and the classification of objects up to isomorphism. The function concept builds toward category theory, where functions are the morphisms and bijections measure cardinality, and Cantor's theorem generalises into the hierarchy of infinite sizes that underpins all of set-based mathematics. Putting these together, the bridge is that the entire categorical and algebraic framework of the curriculum rests on these three primitives — collections, connections, and structure-preserving maps — and every later unit, from topology to measure theory to algebraic geometry, is written in this language.

Full proof set Master

Proposition (Cantor, full proof). For every set $A$ , there is no surjection $A \to P (A)$ , and therefore $∣ A ∣ < ∣ P (A) ∣$ .

Proof. Let $f : A \to P (A)$ be any function. Define the diagonal set

D = {a \in A : a \in / f (a)} .

Because $D \subseteq A$ , we have $D \in P (A)$ . Suppose, towards a contradiction, that $f$ is surjective. Then $D = f (b)$ for some $b \in A$ . Ask whether $b$ lies in $D$ :

If $b \in D$ , then by the definition of $D$ we have $b \in / f (b) = D$ , a contradiction.
If $b \in / D$ , then $b \in / f (b)$ , so by the definition of $D$ we have $b \in D$ , again a contradiction.

Both cases fail, so no such $b$ exists. The set $D$ lies outside the image of $f$ , so $f$ is not surjective. Because $f$ was arbitrary, no surjection $A \to P (A)$ exists, and the inclusion $A ↪ P (A)$ sending $a \mapsto {a}$ shows $∣ A ∣ \leq ∣ P (A) ∣$ strictly. $□$

Proposition (partitions form a lattice). The equivalence relations on a set $A$ , ordered by refinement, form a lattice with greatest element the universal relation and least element equality.

Proof. Let $E (A)$ denote the set of all equivalence relations on $A$ . For $\sim_{1}, \sim_{2} \in E (A)$ , declare $\sim_{1} ⪯ \sim_{2}$ when every $\sim_{1}$ -class is contained in a $\sim_{2}$ -class, equivalently when $a \sim_{1} b$ implies $a \sim_{2} b$ . This relation is reflexive, antisymmetric, and transitive on $E (A)$ , so it is a partial order.

The universal relation $U = A \times A$ relates every pair of elements, so $\sim⪯ U$ for every $\sim\in E (A)$ ; it is the greatest element, the single-class partition. The equality relation $Δ = {(a, a) : a \in A}$ is the finest partition, with $Δ ⪯\sim$ for every $\sim$ ; it is the least element.

For the meet, take $\sim_{1} \cap \sim_{2}$ as a subset of $A \times A$ . It is reflexive, symmetric, and transitive (each property is checked pointwise), so it is an equivalence relation, and it is the greatest lower bound of $\sim_{1}$ and $\sim_{2}$ . For the join, take the transitive closure of $\sim_{1} \cup \sim_{2}$ : declare $a \sim b$ when there is a finite chain $a = x_{0}, x_{1}, \dots, x_{n} = b$ with each consecutive pair in $\sim_{1}$ or $\sim_{2}$ . This is the smallest equivalence relation containing both $\sim_{1}$ and $\sim_{2}$ , hence the least upper bound. Meets and joins of arbitrary families are constructed the same way, so $E (A)$ is a complete lattice. $□$

Connections Master

Equivalence relations and partitions are the engine of quotient vector spaces 01.01.03. A subspace $W \subseteq V$ defines $u \sim v$ when $u - v \in W$ , and the resulting classes $v + W$ form a new vector space $V / W$ whose dimension drops by $dim W$ . The construction is the partition theorem of this unit with linear structure layered on top.
In group theory 01.02.01, a normal subgroup $N ⊴ G$ defines $g \sim h$ when $g^{- 1} h \in N$ , and the classes $g N$ form the quotient group $G / N$ . This is the same partition machinery, now carrying an inherited group operation, and the first isomorphism theorem identifies $G / N$ with the image of any homomorphism killing $N$ .
Bijections define cardinality and reappear wherever counting matters, from the characteristic functions of probability 37.03.01 to the cardinal arithmetic that sizes function spaces. Cantor's theorem proved here launches the hierarchy those later units measure with.
Continuous maps 02.01.02 are functions that preserve topological closeness, refining the bare set-theoretic function of this unit into a morphism of a category; the function concept is the seed, and continuity is the extra condition that makes it a geometric object.

Historical & philosophical context Master

Georg Cantor founded set theory in a sequence of papers beginning in 1874 with "Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen," in which he proved that the real numbers cannot be put in bijection with the natural numbers ^{[Cantor 1874]}. The result shattered the earlier assumption that all infinite collections have the same size, and it forced mathematicians to treat collections of objects as legitimate objects of study in their own right. The controversy Cantor provoked among his contemporaries shaped the foundations debate of the early twentieth century.

Augustus De Morgan codified the symmetry between "or" and "and" under negation in his work on formal logic from 1858. The two identities $(A \cup B)^{c} = A^{c} \cap B^{c}$ and $(A \cap B)^{c} = A^{c} \cup B^{c}$ now bear his name and appear wherever boolean reasoning does, from circuit design to probability to the algebra of subsets studied here ^[Enderton].

Paul Halmos's Naive Set Theory (1960) distilled the working mathematician's set theory into a slender volume that remains the standard gentle introduction, treating sets, relations, functions, and equivalence classes with the informal precision this curriculum adopts at the Beginner and Intermediate tiers ^[Halmos]. Herbert Enderton's Elements of Set Theory (1977) gives the rigorous undergraduate treatment, including the partition–equivalence-relation correspondence and the construction of the number systems upward from the empty set.

Bibliography Master

@book{Halmos1960NaiveSetTheory,
  author = {Halmos, Paul R.},
  title = {Naive Set Theory},
  publisher = {D. Van Nostrand},
  year = {1960}
}

@book{Enderton1977ElementsOfSetTheory,
  author = {Enderton, Herbert B.},
  title = {Elements of Set Theory},
  publisher = {Academic Press},
  year = {1977}
}

@book{StewartRedlinWatson2016Precalculus,
  author = {Stewart, James and Redlin, Lothar and Watson, Saleem},
  title = {Precalculus: Mathematics for Calculus},
  edition = {7},
  publisher = {Cengage Learning},
  year = {2016}
}

@article{Cantor1874,
  author = {Cantor, Georg},
  title = {Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen},
  journal = {Journal für die reine und angewandte Mathematik (Crelle's Journal)},
  volume = {77},
  pages = {258--262},
  year = {1874}
}

@book{DeMorgan1858FormalLogic,
  author = {De Morgan, Augustus},
  title = {The Syllabus of a Proposed System of Logic},
  publisher = {Walton and Maberly},
  year = {1858}
}

Prerequisites

00.02.05

Tier anchors

beginner: intuition: sets collect, relations connect, functions map — the grammar of mathematics (Strogatz-style plain English)
intermediate: Stewart, Redlin & Watson 2016 Precalculus: Mathematics for Calculus (Cengage) Ch. P, §§P.1–P.3 (sets, real line, functions)
master: Halmos 1960 Naive Set Theory (Van Nostrand) §§1–7; Enderton 1977 Elements of Set Theory (Academic Press) Ch. 1–6 (full proofs)

References

Halmos — Naive Set Theory · §§1–7, sets, subsets, union, intersection, complement, Cartesian product, relations, equivalence relations, and functions as single-valued relations; the standard gentle reference for naive set-theoretic foundations used at the Intermediate and Master tiers.
Enderton — Elements of Set Theory · Ch. 1–6, the partition–equivalence-relation bijection in full, ordered pairs and Cartesian products, functions as graphs, Cantor's diagonal argument; the undergraduate formal treatment.
Stewart, Redlin & Watson — Precalculus: Mathematics for Calculus · Ch. P (prerequisites), the real line, intervals, set-builder notation, and an elementary treatment of functions, domain, and graphs; the Intermediate anchor text.
Cantor — Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen (Crelle 1874) · Cantor's 1874 paper; the founding document of set theory, containing the first proof that the reals are uncountable and seeding the study of infinite cardinalities.

Estimated time

beginner: 20 min
intermediate: 50 min
master: 100 min