1
Prove a set identity
By double inclusion or by a chain of laws — and know exactly when a Venn diagram is a case check (three circles, all eight regions) and when it is only a picture.
Course · Discrete Mathematics
Sets, Relations, and Functions
Sets, the operations on them and the identities those obey; relations and the two structures they produce — partitions and orderings; functions, injections, surjections and bijections; countable and uncountable; and the counting principle that follows from all of it.
A ⊆ B ⟺ ∀x (x ∈ A → x ∈ B)
|P(A)| = 2^|A| the power set doubles
equivalence relation ⟺ partition
|A| = |B| ⟺ a bijection A → B exists
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 14
- Format
- Interactive
Overview
What you will be able to do
By the end you have the objects every later course manipulates, and the proof habits from Logic and Proof applied to them.
2
Classify a relation
Decide reflexivity, symmetry, antisymmetry and transitivity by checking the definition, and recognise the equivalence relations and partial orders.
3
Work with functions precisely
Distinguish injective from surjective, compose functions in the right order, and say exactly when an inverse exists.
4
Compare sets by pairing
Show ℤ and ℚ are countable and ℝ is not, using the two arguments that settle both — explicit listing and diagonalisation — and turn the finite half of the same idea, no injection from a larger set into a smaller, into a pigeonhole proof by inventing the boxes yourself.
Lessons
14 lessons
First sets, then relations, then functions, and last the counting consequences that Combinatorics and Counting builds on.
Sets and MembershipCollections, membership, and the two ways to describe a set.Not marked
Subsets and Power SetsContainment, proper containment, and the set of all subsets.Not marked
Set OperationsUnion, intersection, difference, complement, symmetric difference.Not marked
Set Identities and ProofsThe laws, and the two ways to prove one.Not marked
Cartesian Products and TuplesOrdered pairs, and the set of all of them.Not marked
Binary RelationsA relation is a set of ordered pairs, and nothing more.Not marked
Properties of RelationsReflexive, symmetric, antisymmetric, transitive — and closures.Not marked
Equivalence Relations and PartitionsReflexive, symmetric, transitive — and the partition that comes free.Not marked
Partial OrdersReflexive, antisymmetric, transitive — ranking rather than grouping.Not marked
FunctionsA relation where every input has exactly one output.Not marked
Injective, Surjective, BijectiveNo collisions, no gaps, or neither.Not marked
Composition and Inverse FunctionsChaining functions, and undoing them.Not marked
Cardinality and CountabilitySame size means a bijection, even for infinite sets.Not marked
The Pigeonhole PrincipleMore objects than boxes means some box has two.Not marked
Recommended background
Quantifiers and proof technique.
Practice suggestions
Do the set proofs by double inclusion at least once each, even when a chain of laws is shorter. The habit of proving A ⊆ B and B ⊆ A separately is what makes the later structural proofs writable.
Use the relation lab as a counterexample machine. Almost every claim about relations is refuted by a three-element example, and building one yourself is faster than recalling which property implies which. Start from the empty preset and use as few elements as the claim needs — but the elements you leave untouched still count, so reflexivity fails until every one of them has its loop.
Pay attention to “Cardinality and Countability”. Countability is where intuition about size stops working, and every argument after it depends on accepting bijection as the definition of "same size".
What it does not cover
Axiomatic set theory. Sets here are naive: collections of objects. The Zermelo–Fraenkel axioms, the axiom of choice and the cardinal arithmetic beyond countable versus uncountable are a separate subject.
Russell's paradox is mentioned where it explains a restriction, but the resolution — separating sets from classes — is not developed.
Ordinals, transfinite induction, and the continuum hypothesis. “Cardinality and Countability” stops at the two cardinalities the rest of the path uses.