Discrete Mathematics
The mathematics of things you can count, list and check: statements that are true or false, sets and the relations between them, proof by induction, counting without enumerating, probability over finite outcomes, the arithmetic of remainders, graphs, and the analysis of the algorithms that run on all of it. Eight courses and 106 lessons are available.
- Courses
- 8
- Lessons
- 106
- Level
- Beginner → Advanced
- Assumes
- no calculus required
Overview
Logic comes first because everything after it is a claim that has to be stated precisely enough to be true or false. A reader who has not settled what ∀x ∃y P(x, y) means cannot read a single theorem in the later courses, and will silently misread several.
Sets, relations and functions come second because they are the vocabulary. An equivalence relation, a bijection and a partial order each appear in four of the six courses that follow; they are introduced once.
Induction is third rather than last because it is the proof technique the rest of the path depends on. Counting arguments, recurrence solutions, graph theorems and algorithm correctness are all induction wearing different clothes.
Counting, probability and number theory then apply that machinery to three specific worlds, and graphs give it an object to act on. Algorithms and complexity comes last because it needs all of them: recurrences from Induction and Recursion, counting from Combinatorics and Counting, and graphs from Graphs and Trees.
Courses
Each course assumes the ones before it and nothing else. Induction and Recursion proves things about the sets built in Sets, Relations, and Functions; Discrete Probability counts the outcomes Combinatorics and Counting taught you to count; Algorithms and Complexity analyses the structures Graphs and Trees built.
Make a statement precise enough to be true or false, then establish it. Connectives and truth tables, logical equivalence, quantifiers and the order they come in, valid inference, and direct, contrapositive, contradiction and case proofs written out in full.
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.
Logic and Proof ended by showing that checking cases is not proving. This is the answer: prove P(k) → P(k+1) once and the claim holds for every n you could ever check and every one you could not. Then the same idea applied to definitions, to data, to algorithms and to recurrences.
How many? The two basic rules, the four ways to choose r from n, what changes when repetition is allowed, how to correct an over-count, and the double-counting arguments that prove identities without algebra.
Counting with a denominator. Every probability here is a ratio of counts, so Combinatorics and Counting does most of the work — and the parts that go wrong, conditioning and independence, go wrong for reasons that have nothing to do with arithmetic.
Everything follows from one theorem about division with remainder. Primes, gcds, congruences and modular inverses build up to RSA — which is generated, used and then broken here on primes small enough to check by hand.
The discrete structure that models everything with a relation on it: networks, dependencies, maps, molecules, schedules. Every theorem in this course is a claim about all graphs, and the lab lets you try to break each one.
The course the rest of the path was building toward. Recurrences from Induction and Recursion, counting from Combinatorics and Counting and graphs from Graphs and Trees all reappear as the running time of something — and the last two lessons say what no algorithm can do.
Recommended background
School algebra, and nothing beyond it. You need to be comfortable rearranging an equation, working with exponents, and reading summation notation — the first course that uses Σ explains it where it first appears.
No calculus. Nothing on this path takes a limit, a derivative or an integral. Where a growth rate is compared to another, it is compared by an explicit constant and threshold rather than by a limit.
No programming. Algorithms and Complexity reads pseudocode and Number Theory and Cryptography walks through algorithms step by step, but nothing asks you to write or run code. The labs execute in your browser so that you can watch an algorithm rather than implement it.
Patience with definitions. The single largest difficulty in this subject is that its words are used precisely: or is inclusive, some means at least one, and a graph is not a plot. Every one of those is stated where it first matters.