🔢 Discrete Mathematics

What you’ll learn

1. The World of Separate ThingsExplain what makes discrete mathematics a distinct discipline — the absence of arbitrarily small steps — and why counting and proof become the only available tools.Continuous mathematics rests on the assumption that between any two values lies another, which is what makes limits, derivatives, and integrals possible. Discrete mathematics studies objects for which that assumption fails: integers, sets, graphs, strings, and the states of a computer. Once smallness is unavailable, only two instruments remain — counting (measuring how many without enumerating) and proof (achieving certainty when checking every case is impossible) — and these are the through-line of everything that follows.
2. Sets: The Language of CollectionsUse sets, their operations, and the subset relation as the precise language of collections, and derive the power-set size 2^n by counting decisions rather than objects.A set is a collection of distinct, unordered objects treated as a single object, and membership — a strict yes or no — is its only primitive relation. Union, intersection, and difference build new sets from old, and disjointness (empty intersection) is the condition under which sizes simply add. Counting the subsets of an n-element set by making one independent in/out choice per element yields 2^n, introducing both the central technique of combinatorics and the exponential growth that dominates the rest of the course.
3. Statements With a ShapeRead and negate quantified statements mechanically, and distinguish the conditional from its converse and its contrapositive.Quantifiers make explicit the structure that ordinary language leaves ambiguous, and their order changes meaning entirely: ∀x∃y and ∃y∀x are different claims. Negation is mechanical — push the ¬ inward and every quantifier it crosses flips — which is why one counterexample refutes a universal claim while refuting an existential claim requires ruling out everything. The conditional p → q fails only when p holds and q does not; its converse is a separate claim, but its contrapositive ¬q → ¬p is logically equivalent and can always be substituted, a licence the next chapter turns into a proof technique.
4. Why Mathematicians Don't TestApply direct proof, proof by contrapositive, and proof by contradiction, and choose between them by examining which hypothesis offers a usable handle.Because discrete objects are separate and often infinite in number, testing cases can never establish a general claim — Pólya's conjecture survives hundreds of thousands of checks and fails at 906,150,257. Direct proof unfolds definitions and walks forward; proof by contrapositive exploits the logical equivalence of ¬q → ¬p with p → q to swap an unusable hypothesis for a concrete one; proof by contradiction assumes the negation and derives an impossibility, which is why it is the natural technique for claims that something does not exist. The proof that √2 is irrational rules out infinitely many fractions in six lines — a thing no amount of computation could do.
5. Induction: Proving Infinitely Many Things at OnceProve statements about all natural numbers by induction, and recognise induction as the structure underlying loop invariants and recursion.Mathematical induction proves infinitely many statements with a finite argument by establishing two things: a base case (the first domino falls) and an inductive step (each case implies the next). The step is not circular — it proves a conditional about the link between consecutive cases, while the base case supplies the only actual push, and neither alone proves anything. The same structure appears in computing as the loop invariant and as recursion, which is why induction is how a program can be proved correct on inputs it was never tested against.
6. Counting Without CountingCount outcomes with the product rule, and distinguish permutations from combinations by asking whether order matters and whether repeats are allowed.Combinatorics measures how many things exist without producing any of them, and the product rule — multiply the number of independent choices — carries most of the subject, because each earlier choice branches into every later one. Permutations count ordered selections, P(n,k) = n!/(n−k)!; combinations count unordered ones by counting the ordered version and dividing by the k! ways each group could have been ordered. Almost every counting error comes from failing to ask, before any algebra, whether order matters and whether repeats are allowed.
7. The Pigeonhole PrincipleUse the pigeonhole principle to prove existence and impossibility results, and distinguish non-constructive proof from a method of finding an object.The pigeonhole principle — n items in m containers with n > m forces some container to hold two — is trivially obvious and yet proves claims that appear unknowable, such as that two Londoners have exactly the same hair count. Such proofs are non-constructive: they establish existence with certainty while offering no way to locate the objects, a gap between 'exists' and 'findable' that modern cryptography depends on. Pigeonhole's serious use is proving impossibility: no lossless compressor can shrink every file, and hash collisions are mathematically guaranteed rather than an engineering defect.
8. Graphs: Relationships as MathematicsModel relationships as graphs, apply Euler's degree argument, and trace breadth-first search as a shortest-path algorithm.Euler settled the Königsberg bridges problem in 1736 by discarding geography entirely and keeping only what connects to what — inventing the graph, a set of vertices and edges representing pure relationship. His solution was a counting argument: intermediate vertices must have even degree because entries pair with exits, so at most two odd vertices are permitted, and Königsberg had four, making the walk impossible rather than merely hard. Because friend networks, roads, the internet, compilers, and project plans are all graphs once irrelevant detail is deleted, one theorem serves them all — and breadth-first search, which expands in rings and is proved correct by induction, finds shortest paths in every one of them.
9. Modular Arithmetic and the PayoffCompute in modular arithmetic, explain why it yields one-way functions, and connect exponential counting to cryptographic security.Modular arithmetic wraps the number line into a finite circle, and the wrap discards information — which makes operations easy to perform and hard to reverse, the asymmetry every modern cryptosystem is built on. Security does not come from any mathematical prohibition on brute force: keys can always be enumerated in principle, and pigeonhole guarantees collisions. It comes from counting — a 256-bit key space of roughly 1.16 × 10^77 outruns a trillion machines testing a trillion keys per second since the Big Bang by roughly 35 orders of magnitude, and each added bit doubles the gap, closing the course's loop back to the 2^n first met while counting subsets.

Questions this course answers

Grounded in trusted sources

• Kenneth Rosen, Discrete Mathematics and Its Applications (8th ed., McGraw-Hill)
• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (4th ed., MIT Press)
• Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis' (Comm. Acad. Sci. Petropolitanae, 1736)
• Paul Halmos, Naive Set Theory (Springer)
• Richard Stanley, Enumerative Combinatorics, Vol. 1 (Cambridge University Press)
• Rivest, Shamir & Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems' (CACM 21:2, 1978)
• NIST SP 800-57 Part 1 Rev. 5 — Recommendation for Key Management
• Stanford Encyclopedia of Philosophy — Classical Logic

Every Wunder lesson is built from real, reputable sources — never invented.

Related Math courses