Sets, Functions, and Relations
The objects every later definition is built from: how to speak precisely about collections, mappings, and the relationships between them.
Leads to: Probability spaces, vector spaces and sigma-algebras are all sets carrying extra structure; random variables and continuous maps are functions carrying extra structure.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Define sets by roster and by set-builder notation and compute unions, intersections, complements, and Cartesian products.
- Distinguish a relation from a function and state precise conditions for injectivity, surjectivity, and bijectivity.
- Prove elementary set identities using the element-chasing (double-inclusion) method.
- Interpret equivalence relations and partitions and explain why they are two views of a single idea.
Key Vocabulary
- Set
- An unordered collection of distinct objects called its elements; specified by roster {1,2,3} or by a rule {x : P(x)}.
- Cartesian product
- The set A×B of all ordered pairs (a,b) with a in A and b in B; ordered means (a,b) ≠ (b,a) in general.
- Relation
- Any subset R of A×B; we write a R b to mean (a,b) is in R.
- Function
- A relation f from A to B in which every a in A is paired with exactly one b in B, written f: A → B.
- Injective / surjective / bijective
- One-to-one / onto / both at once; a bijection is exactly a map with a two-sided inverse.
- Equivalence relation
- A reflexive, symmetric and transitive relation; it carves a set into disjoint equivalence classes.
- Partition
- A family of non-empty, pairwise-disjoint subsets whose union is the whole set.
Intuition & Motivation
Sets and how we build new ones
A set is a collection of distinct objects; order and repetition do not matter, so {1,2,2,3} and {3,1,2} denote the same set. We combine sets with three basic operations, defined purely by membership:
Two sets are equal precisely when they have the same elements. That single fact is the engine behind every set proof: to show \(A=B\) we show \(A\subseteq B\) and \(B\subseteq A\) - the double-inclusion method.
Functions as special relations
A relation from A to B is any subset of \(A\times B\). A function is the disciplined special case: every input is used exactly once. Formally \(f\subseteq A\times B\) is a function when for each \(a\in A\) there is one and only one \(b\) with \((a,b)\in f\); we write \(b=f(a)\).
| Property | Meaning | Symbolic form |
|---|---|---|
| Injective | distinct inputs give distinct outputs | f(x)=f(y) ⇒ x=y |
| Surjective | every target value is hit | ∀b∈B ∃a: f(a)=b |
| Bijective | injective and surjective | has a two-sided inverse f⁻¹ |
Equivalence relations and partitions
A relation \(\sim\) on a set is an equivalence relation if it is reflexive (\(a\sim a\)), symmetric (\(a\sim b\Rightarrow b\sim a\)) and transitive (\(a\sim b,\ b\sim c\Rightarrow a\sim c\)). The key theorem: the equivalence classes of \(\sim\) form a partition, and conversely every partition defines an equivalence relation. The two ideas are the same object seen from two sides - a pattern you will meet again (sigma-algebras and information, cosets and quotients).
Interactive: set algebra as code
- Confusing ⊆ (subset, a relation between sets) with ∈ (membership, between an element and a set). {1} ⊆ {1,2} but {1} ∈ {{1},2}.
- Treating (a,b) as unordered: in a Cartesian product order matters, so (1,2) ≠ (2,1).
- Calling a relation a function when some input maps to two outputs, or when some input is left out.
- Proving only one inclusion A ⊆ B and concluding A = B. Equality needs both directions.
- To prove a set identity, chase a generic element: ‘let x be in the left side, show x is in the right’, then reverse.
- Injectivity is usually proved by ‘assume equal outputs, deduce equal inputs’; surjectivity by solving for a pre-image.
- When you see ‘partition’ think ‘equivalence relation’ and vice versa - switching viewpoints often unlocks a proof.
- In probability, events are sets and independence/conditioning are set operations; this lesson is literally the notation of Phase 7.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#16 Power Digit Sum (1%, tier A) #30 Digit Fifth Powers (2%, tier A) #52 Permuted Multiples (2%, tier A) #33 Digit Cancelling Fractions (3%, tier A)
Applied:
#932 $2025$ (17%, tier B) #315 Digital Root Clocks (18%, tier B) #479 Roots on the Rise (19%, tier B)
Challenge:
#666 Polymorphic Bacteria (41%, tier C) #157 Base-10 Diophantine Reciprocal (42%, tier C)
130 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
Let \(f:A\to B\) and \(g:B\to C\). (a) Prove that if \(f\) and \(g\) are both injective then \(g\circ f\) is injective. (b) Give an explicit example where \(g\circ f\) is injective but \(g\) is not.
(a) Suppose \((g\circ f)(x)=(g\circ f)(y)\), i.e. \(g(f(x))=g(f(y))\). Since \(g\) is injective, \(f(x)=f(y)\). Since \(f\) is injective, \(x=y\). Hence \(g\circ f\) is injective.
(b) Let \(A=\{1\},\ B=\{1,2\},\ C=\{1\}\) with \(f(1)=1\) and \(g(1)=g(2)=1\). Then \(g\circ f\) sends \(1\mapsto 1\) and is injective (its domain has one point), yet \(g\) is not injective because it collapses 1 and 2. The lesson: composition can be better-behaved than its parts.
Lesson Summary
Formula Sheet Additions
- Did I prove both inclusions for a set equality?
- For injectivity, did I start from equal outputs and reach equal inputs?
- For surjectivity, did I exhibit a pre-image for an arbitrary target?
- Am I keeping ∈ and ⊆ straight?
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: Show every element of A lies in B (A ⊆ B) and every element of B lies in A (B ⊆ A); together they force identical membership, hence A = B.
A: Reflexive, symmetric, transitive; the equivalence classes form a partition of the set into non-empty, pairwise-disjoint, exhaustive pieces.
A: Injective: assume f(x)=f(y) and deduce x=y. Surjective: take an arbitrary target b and construct a pre-image a with f(a)=b.
Flashcards
Click to flip. These feed the site-wide spaced-repetition queue.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Vol. I, Intro & Ch. 1 - Introductory set notation, functions, and the real line as a foundation for calculus.
- Linear Algebra Done Right (Sheldon Axler, 4th ed., 2024) current - Ch. 1, 3 background - Functions, injectivity/surjectivity and bijections framed as the language of linear maps.