Mathematical Foundations·Intermediate·5 lessons·62 practice activities·~280 min
Set Theory and Relations: The Structure Underneath Logic
The mathematical scaffolding that makes formal reasoning possible
What you'll learn
By the end of this unit, you can…
- Distinguish membership and inclusion.
- Compute set operations.
- Classify relations by properties.
- Classify functions as injective surjective bijective.
- Translate and verify arguments set theoretically.
Lessons
Lesson sequence
- 1Open →
What Is a Set?
Introduces sets as collections defined by their members, explains the axiom of extensionality, distinguishes membership from subset, discusses the empty set, and shows why naive unrestricted comprehension collapses into Russell's paradox.
- 2Student Pro
Operations on Sets
Introduces the standard set operations — union, intersection, complement, difference, symmetric difference, power set, and Cartesian product — and teaches students to verify results by element-chasing and visualize simple cases using Venn diagrams.
- 3Student Pro
Relations and Their Properties
Defines a relation as a subset of a Cartesian product, introduces reflexivity, symmetry, transitivity, and antisymmetry, explains equivalence relations and the partitions they induce, and discusses order relations.
- 4Student Pro
Functions and Cardinality
Defines a function as a well-defined relation, introduces injective, surjective, and bijective functions, develops cardinality for finite and infinite sets, states the pigeonhole principle, and presents Cantor's diagonal argument in intuitive form.
- 5Student Pro
Capstone: Using Set Theory in Logic and Argument
Integrates the unit by showing how set theory provides the semantic foundation for categorical and predicate logic. Students translate categorical and quantified arguments into set-theoretic form and verify them structurally using union, intersection, subset, and function reasoning.
How to study
Three moves that work for this unit
Read the explanation
Each lesson opens with a guided walkthrough — read it before the activity.
Study the worked example
Look at why each step follows, not just what the answer is.
Practice with the target in mind
Know which rule applies and what would make the response weak before you start.
Reference materials
Optional context for the unit. Each lesson surfaces the concepts and rules it uses — these are here when you want the bigger picture.
Concept map (9 terms)
Set
A well-defined collection of distinct objects, considered as a single mathematical object; the objects are called elements or members of the set.
Element (Member)
An object belonging to a set; if x is an element of the set A, we write x ∈ A, and if it is not, we write x ∉ A.
Subset
A set A is a subset of a set B, written A ⊆ B, if every element of A is also an element of B; A is a proper subset if in addition A ≠ B.
Power Set
The power set of a set A, written P(A) or 2^A, is the set whose elements are all the subsets of A, including the empty set and A itself.
Cartesian Product
The Cartesian product A × B of two sets is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
Relation
A binary relation from A to B is a subset R ⊆ A × B; elements (a, b) ∈ R are usually written a R b.
Function
A function f: A → B is a relation from A to B such that for every a ∈ A there is exactly one b ∈ B with (a, b) ∈ f; we write f(a) = b for this unique value.
Equivalence Relation
A relation R on A that is reflexive, symmetric, and transitive; each equivalence relation partitions A into disjoint equivalence classes.
Cardinality
A measure of the size of a set; two sets have the same cardinality when there exists a bijection between them, and a set is countable when it has the same cardinality as the natural numbers.
Rules and standards (6)
- Axiom of Extensionality. Two sets are equal if and only if they have exactly the same elements; order and repetition of listed elements are irrelevant. Common failures: Treating {1, 2, 3} and {3, 2, 1} as different sets because the elements are listed in a different order.; Treating {1, 1, 2} as a three-element set rather than recognizing it as the two-element set {1, 2}..
- Russell's Paradox Restriction. There is no set whose members are exactly those sets that are not members of themselves; naive unrestricted comprehension must be replaced by axiomatic separation or a similar restriction. Common failures: Assuming that every describable property carves out a set, which leads to Russell's paradox.; Treating 'the set of all sets' as a legitimate set without noticing the contradictions it generates..
- Subset and Membership Are Different Relations. Membership (∈) and inclusion (⊆) are distinct: x ∈ A means x is one of the elements of A, while A ⊆ B means every element of A is also an element of B. Common failures: Writing 1 ⊆ {1, 2} when the correct claim is 1 ∈ {1, 2}.; Writing {1} ∈ {1, 2} when the correct claim is {1} ⊆ {1, 2}..
- Reflexivity, Symmetry, and Transitivity. A relation R on A is reflexive if every element is related to itself, symmetric if a R b implies b R a, and transitive if a R b and b R c imply a R c; an equivalence relation must satisfy all three. Common failures: Checking a finite sample of pairs and declaring a relation transitive without verifying that every three-step chain is respected.; Confusing symmetry with reflexivity, or antisymmetry with asymmetry..
- Functions Must Be Well-Defined. A relation f ⊆ A × B is a function only when every element of A is paired with exactly one element of B; no element of A may be missing, and no element of A may be paired with two different outputs. Common failures: Defining a 'function' that leaves some elements of the domain without any output.; Defining a 'function' by a rule that produces two different outputs for the same input under different representations..
- Pigeonhole Principle. If a function maps a finite set of size n into a finite set of size m < n, then at least two elements of the domain must share the same image; equivalently, no injection exists from a larger finite set into a smaller one. Common failures: Claiming an injection between two finite sets without checking the sizes.; Using the pigeonhole principle to conclude anything stronger than the existence of a collision, such as identifying which specific elements collide..
Formalization patterns (2)
- Set-Builder Notation. From natural_language_description to set_builder_expression — Identify the domain from which candidate elements are drawn.; Write the candidate variable followed by a vertical bar or colon.; State the defining property the candidate must satisfy, using predicate-logic style notation when possible.; Wrap the whole expression in set braces.; Verify that the property actually picks out the intended collection by checking a few test elements..
- Relation as a Set of Ordered Pairs. From natural_language_relation to subset_of_cartesian_product — Identify the source set A and the target set B the relation connects.; Form the Cartesian product A × B as the space of all possible ordered pairs.; Write the relation as the subset R ⊆ A × B containing exactly the pairs (a, b) for which a is related to b.; Check each of reflexivity, symmetry, transitivity, and antisymmetry by inspecting the pairs.; If the relation is functional, verify that each element of A appears as the first coordinate of exactly one pair..
Full mastery and assessment guidance
Mastery requirements
- Distinguish membership and inclusion. Correct Classifications · 8_correct_classifications
- Compute set operations. Correct Computations · 8_correct_computations
- Classify relations by properties. Correct Classifications · 6_correct_classifications
- Classify functions as injective surjective bijective. Correct Classifications · 6_correct_classifications
- Translate and verify arguments set theoretically. Correct Translations And Verifications · 4_correct_translations_and_verifications
Assessment advice
- Can I state extensionality without looking at my notes?
- For any given claim, can I decide whether ∈ or ⊆ is the right symbol?
- Can I explain in one paragraph why Russell's paradox forces a restriction on set formation?
- Do not read set notation by visual similarity — always ask whether the left object is a member of or a subset of the right object.
- Do not treat 'the set of all X' as automatically well-defined; it is only a set when X is a property restricted to an existing set.
- For each operation, can I state its defining condition in terms of 'and,' 'or,' or 'not'?
- Can I compute unions, intersections, differences, and symmetric differences on small numeric sets without using a diagram?
- Can I list all 2^n subsets of an n-element set systematically?
- Do not skip element-chasing steps when checking an identity; cases need to be handled explicitly.
- Do not forget to include ∅ as an element of every power set.
- Can I state each of reflexivity, symmetry, transitivity, and antisymmetry in precise set-theoretic terms?
- Given a concrete relation, can I produce its equivalence classes if it is an equivalence relation?
- Can I give an example of a partial order that is not total?
- Do not verify transitivity by checking only a handful of pairs; the property must hold for every three-element chain.
- Do not confuse a relation failing to be reflexive with the relation being 'almost an equivalence relation.' Reflexivity is essential.
- Can I state the well-definedness condition for a function in one sentence?
- Given a small finite function, can I decide whether it is injective, surjective, both, or neither?
- Can I reproduce the pigeonhole principle and explain why it is true by counting?
- Do not call a relation a function without checking that every domain element is mapped.
- Do not assume every infinite set is countable — Cantor's argument exhibits one that is not.
- Can I translate every categorical proposition into precise set-theoretic form?
- Can I use subset transitivity and element-chasing to verify a valid argument structurally?
- Can I construct a small-set counterexample whenever I suspect an argument is invalid?
- Do not mix up subset claims with intersection claims — 'All S are P' and 'Some S are P' are structurally different.
- Do not treat an invalid argument as 'probably valid' without constructing a concrete counterexample.
Historical context (4)
- Georg Cantor. Founded set theory as a rigorous mathematical discipline, introduced the concept of cardinality for infinite sets, and proved that the real numbers form a strictly larger infinity than the natural numbers via the diagonal argument. The definition of set equality, the hierarchy of infinite cardinalities, and the diagonal method taught in this unit all descend directly from Cantor's work.
- Bertrand Russell. Discovered in 1901 that naive set theory is inconsistent: the collection of all sets that are not members of themselves cannot itself be a set without contradiction. Russell's paradox is the reason modern set theory restricts comprehension and distinguishes sets from proper classes; every axiomatic framework in use today is a response to it.
- Ernst Zermelo and Abraham Fraenkel. Developed the Zermelo-Fraenkel axiomatization (ZF), which replaces naive comprehension with a limited separation schema and provides the standard foundation for modern mathematics. ZF (with the axiom of choice, giving ZFC) is the framework within which every definition in this unit can be made rigorous and consistent.
- Kurt Gödel. Constructed the inner model L of constructible sets and proved that the axiom of choice and the continuum hypothesis are consistent with ZF, laying the groundwork for the independence results of later decades. Gödel's constructible universe shows that the very notion of 'set' is more subtle than it first appears, and it marks the beginning of modern metamathematics.