MU-101 · Foundations & Mathematical Proof
How mathematics is built: sets, logic, and the forms of rigorous argument that everything after this relies on.
None — this unit is the entry point to the canon.
Lectures
| L01 | What a Proof Is: Statements, Truth, and Argument — |
| L02 | Propositional Logic: Connectives and Truth Tables — |
| L03 | Quantifiers, Scope, and Negation |
| L04 | Sets: Membership, Subsets, and Operations |
| L05 | Relations, Functions, and Composition — |
| L06 | Injections, Surjections, and Bijections — |
| L07 | Direct Proof and Proof by Cases — |
| L08 | Proof by Contraposition — |
| L09 | Proof by Contradiction |
| L10 | The Irrationality of √2 |
| L11 | The Natural Numbers and the Peano Axioms — |
| L12 | Mathematical Induction |
| L13 | Strong Induction and Definition by Recursion |
| L14 | The Well-Ordering Principle |
| L15 | Equivalence of Induction and Well-Ordering |
| L16 | Divisibility and the Division Algorithm |
| L17 | Primes and Euclid's Argument |
| L18 | Counting: Bijections and Finite Sets — |
| L19 | The Pigeonhole Principle |
| L20 | Applications of Pigeonhole |
| L21 | Equivalence Relations and Partitions — |
| L22 | Order Relations, Bounds, and Suprema — |
| L23 | Countable Sets and Enumeration — |
| L24 | Cantor's Diagonal Argument |
| L25 | Power Sets and Cantor's Theorem |
| L26 | Synthesis: The Architecture of Rigorous Mathematics |
Theorems in this unit
The principle of mathematical induction
If a statement holds for 1 and its truth at n forces its truth at n+1, it holds for every natural number.
The well-ordering principle
Every non-empty set of natural numbers has a least element, and this is equivalent to induction.
The pigeonhole principle
If n+1 objects are placed in n boxes, some box holds at least two.
The irrationality of √2
No ratio of integers squares to 2; the proof is the classic argument by contradiction.
The infinitude of the primes
There is no largest prime; assuming a finite list yields a contradiction.
The uncountability of the reals
No list can enumerate all real numbers — Cantor's diagonal argument.
Cantor's theorem
A set never has the same cardinality as its power set: |P(A)| > |A|.
The division algorithm
Every integer divides another with a unique quotient and a unique remainder below the divisor.
Equivalence relations and partitions
Equivalence relations and partitions of a set are the same data: the classes of a relation partition it, and every partition comes from exactly one relation.