Part II: Structures

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." — Linus Torvalds

Part I gave you the grammar of mathematics: how to state a claim precisely and how to prove it. But a grammar needs something to talk about. Part II supplies the nouns. Sets, functions, relations, sequences, orders — these are the fundamental objects of discrete mathematics, and they are not abstract decorations. They are the data types of mathematics, and they map, almost one for one, onto the data structures you already use every day. A Python set is a set. A hash map is a function from keys to values. A foreign key in a database is a relation. A build dependency graph is a partial order. When you learn the mathematics here, you are not leaving programming behind; you are seeing the structure that was inside your programs the whole time.

There is a reason this part comes second rather than last. Nearly everything in the rest of the book is built out of these few objects. A relation, in Chapter 12, is just a set of ordered pairs — so it depends on sets. A graph, the workhorse of Part V, is a set of vertices together with a set of edges. A probability event, in Part III, is a subset of a sample space. The recurrences of Part III and the algorithms of Part V are described with the sequence and summation notation introduced here. Even the cryptography of Part IV leans on functions and their inverses. Get these structures clean and fluent now, and the later chapters stop feeling like new material and start feeling like familiar objects wearing new clothes.

Part II also marks a quiet shift in what you are doing with proofs. In Part I you proved statements about numbers and logic. Here you will prove statements about structures — that two sets are equal, that a function is a bijection, that a relation is an equivalence. The proof techniques are exactly the ones you just learned; only the subject matter has changed. By the end of this part you will read a definition like "a function is injective if..." and immediately know how to prove a given function fits it. That fluency — moving smoothly between a structure's definition and a proof about it — is the real skill of Part II, and it is what separates someone who has memorized the vocabulary from someone who can actually use it.

What You Will Learn

Chapter 8 — Sets. The foundation everything else is built on. You will use set notation and the core operations (union, intersection, difference, complement), prove set identities by chasing a single element through the definitions, and build power sets and Cartesian products. The Toolkit increment, sets.py, implements these operations from scratch, and the CS payoff is immediate: deduplication, near-constant-time membership testing, and why a set beats a list when uniqueness and lookup matter.

Chapter 9 — Functions. A function is a relation with a rule, and that simple idea carries enormous weight in computing. You will define functions formally, classify them as injective, surjective, or bijective, and compose and invert them. The payoff is a precise way to think about hash functions, pure functions, and type signatures — and the bijection, defined here, becomes the tool Chapter 10 uses to measure the size of infinity.

Chapter 10 — Cardinality and Infinity. This is a threshold chapter, the one that changes how you see computation. You will learn to compare set sizes by matching elements, see why the integers and rationals are "countable" while the reals are not, and run Cantor's diagonal argument yourself. The consequence is startling and concrete: there are strictly more problems than there are programs to solve them, which means some problems cannot be solved by any program at all. It is the first hint of the limits that Chapter 36 makes rigorous.

Chapter 11 — Sequences and Summations. The notation you will use to analyze every algorithm in the book. You will work with sequences in closed and recursive form, master summation notation, and evaluate arithmetic and geometric series with confidence. This is also where Fibonacci returns, now treated as a sequence, and where you learn to turn the cost of a nested loop into a sum you can actually evaluate — the technique Chapter 14 leans on directly.

Chapter 12 — Relations. Relations generalize functions and underpin both databases and graphs. You will represent relations as sets of pairs, as matrices, and as digraphs; classify them by the properties (reflexive, symmetric, transitive) that matter; build equivalence relations and the partitions they induce; and compute transitive closures. The CS anchor is the relational model — the mathematics behind every SQL query you have ever written.

Chapter 13 — Partial Orders, Lattices, and Boolean Algebra. Some things are only partly comparable, and that idea has teeth. You will work with partial orders and Hasse diagrams, perform a topological sort (the algorithm behind make and every build system), and meet lattices. The chapter closes the loop with logic by deriving Boolean algebra and showing how its laws become physical logic gates — connecting all the way back to Chapter 1.

Chapter 14 — Algorithms and Complexity. The analytical spine of the rest of the book. You will define an algorithm precisely, count its work in a machine-independent way, and master the three asymptotic notations — Big-O, Big-Omega, and Big-Theta — proving growth claims straight from the definition. You will rank the growth-rate hierarchy you will live with for the rest of your career and argue your first lower bound. This is the vocabulary every code review and system-design conversation is conducted in.

How This Part Fits

Part II rests squarely on Part I. The set-identity proofs of Chapter 8 and the function classifications of Chapter 9 are written in the proof styles you learned in Chapters 4 and 5, and several arguments here — including Cantor's diagonalization in Chapter 10 — are proofs by contradiction at heart. The translation skills of Chapters 1 and 2, turning English into precise logical statements, are exactly what you will use to read and write the formal definitions that fill this part. Induction from Chapter 6 reappears whenever we reason about a sequence or a recursively built structure.

Looking forward, this part is the launchpad for almost everything that follows. Sets and counting set up the combinatorics of Part III. Sequences and summations set up recurrences and the cost analysis used throughout. Functions, inverses, and modular ideas feed the number theory and cryptography of Part IV. Relations and the graph-shaped thinking they introduce open directly onto Part V, the graph-theory core of the book. And Chapter 10's glimpse of the uncountable is the seed of Part VI, where the limits of computation become a formal theory. Almost every cross-reference in the later chapters points back to something defined here.

Time Investment

The hours below are guided estimates from the outline; treat them as planning figures, not a schedule. The advanced chapters (10 and 13) reward extra time, and Chapter 14 is the one most worth slowing down for, since its notation recurs in every later analysis.

We begin where everything else begins. Chapter 8 takes the most ordinary object in your programs — a collection of distinct things, with no duplicates and no order — names it a set, and shows that the moment you name it, an entire algebra and an entire vocabulary come along for free. Let's start there.

Chapters in This Part

• Chapter 8: Sets
• Chapter 9: Functions
• Chapter 10: Cardinality and Infinity
• Chapter 11: Sequences and Summations
• Chapter 12: Relations
• Chapter 13: Partial Orders, Lattices, and Boolean Algebra
• Chapter 14: Algorithms and Complexity