01Sets, Logic & the Art of Counting

The roadmap left us with one sentence: put a number on an uncertain future, then size your bet against the risk of being wrong. Every chapter after this one is that sentence made rigorous. But read it again and you'll notice it quietly assumes two things we have not earned yet. Before you can put a number on something, you have to be able to say which things you're talking about. And you have to be able to say how many there are. That's this chapter, and I want to warn you up front that it is not the boring one. It contains the single move that regenerates every counting formula you'll ever need — and a much stranger idea underneath it: "how many?" is never answered by looking. It is answered by pairing. Here's the plan. We'll build a set as a door that only says yes or no. We'll build a function as a vending machine with no formula in it. Then we'll settle "are there more people or more seats?" in a packed theatre — with total certainty, without counting anything. From there, counting becomes a strategy instead of an act of perception, and the strategy is this: count the easy thing, ask how many times each answer got built, and correct for it. By the end, C(n,k) = n!/(k!(n−k)!) — five people, pick two, 120/(2 × 6) = 10 — won't be a formula you memorized. It'll be the first thing you compute with a tool you own.

There's one real prerequisite, and it isn't algebra. This chapter is going to ask you to accept that a definition is a choice we make to keep our reasoning honest. It is not a truth someone discovered. For about ten minutes you'll need to let go of "but everyone knows what counting is." That's the whole entry fee. Everything else you already have: you can multiply, you can divide, you trust that 6/2 = 3, and you have physically pointed at things and said "one, two, three."

Here's the whole course on one page: the four verbs, the foundations underneath them, and the craft on top. We are standing on the very first rung. Nothing sits behind it.

Notice what's underneath everything: sets and counting. That isn't because they're elementary, but because the word probability has no meaning until they exist, so let's build them.

01Which things? A set is a door test

Start with a word you already use: collection, which in everyday English is basically a list. It has an order — there's a first one and a last one. And it can repeat — you can have two of the same thing in it. Hold onto that, because a set has neither of those, and the difference is going to cost you real money later if we let it slide now.

Think about a queue versus a guest list. In a queue, position matters, because being third is different from being seventh, and you could even leave and rejoin in principle, so you'd be in it twice. Now the guest list. There's a bouncer at the door, and he has exactly one question: are you on it — yes or no? He doesn't care what order you arrived in, and he doesn't care that you RSVP'd three times. Yes, or no. That's it.

That bouncer is the set. Not a picture of a set, not a metaphor for a set — a set is precisely a rule that answers yes or no about any thing you hand it. Type whatever you like into the door below and watch what comes back.

So {1, 2, 2, 3} and {1, 2, 3} are the same set. The door gives identical answers to every question you can ask it, and the door is all there is. Writing 2 twice doesn't create a second 2. It just wastes ink. In the same way {1, 2} and {2, 1} are the same set, because "which order did you write them in" is not a question the door can even hear.

Two more things fell out of that door. A door that says no to everyone is still a door, which is the empty set, written ∅. It's a real object — a perfectly good bouncer who happens to have an empty list. And now the one that trips everyone: {∅} is not the same as ∅, because a room containing an empty room is not an empty room. Ask {∅} whether ∅ is inside it and the door says yes, so it has exactly one thing in it. That thing just happens to be nothing-shaped.

Now the confusion I promised would cost you. Deal three cards and read them as a sequence of draws: A-then-K-then-Q is a different object from Q-then-K-then-A — different order, different thing. Read the same three cards as a poker hand and they are one object, full stop. A hand is a set, and a sequence of draws is not. Flip the switch below and watch six different sequences collapse into one hand.

Feel how many things vanished when you flipped that switch. Six went to one. That collapse is not a technicality — it is the source of roughly half of all wrong counts in this entire course, and we'll come back and stare straight at it in Section 4. For now just carry the flag: before you count anything, decide whether the object you're counting is a set or a sequence.

We have doors. Now wire two of them together. If a set is a yes/no test, two sets give you two tests, and there are only three interesting ways to combine two yes/no answers: and, or, not. Nothing new is entering the room. We are wiring switches.

"And" gives you the things that pass both doors, which is the intersection, A ∩ B. "Not" gives you everything that fails the door, the complement. And "or" gives you the union, A ∪ B — but here I have to stop you, because English is about to lie. When someone asks "coffee or tea?" they mean pick one, but in maths "or" is inclusive: A ∪ B means at least one, and both is completely fine. It's the door that opens for anyone holding at least one ticket.

Now the one that actually does damage, and I want you to commit to an answer before you read on. There's a sign on the wall, and it says: NOT (raining AND cold). Right now it is raining, and it is warm, so does the sign still hold? Decide, then press your answer.

The sign holds. And if your gut said no, good — that's the exact wrong turn we needed to catch. "Not both" is not the same sentence as "neither", because "not both" only needs one of them to fail. It's raining but it isn't cold, so it isn't both, so the sign is fine. Now say that back slowly: "not both" means "at least one of them is false." That sentence, written in symbols, is ¬(A ∧ B) = ¬A ∨ ¬B. That's De Morgan's law, and it's not an identity to memorize. It's a transcript of a sentence you just said out loud, and the Venn shading in that figure is the same sentence drawn.

One more piece of grammar and we can leave. Suppose I chop a set into pieces: when am I allowed to just add up the piece-counts? This looks like bookkeeping, but it is actually the licence for the plus sign, and it fails silently, which is the worst way for anything to fail. So let's break it on purpose. Count a deck of cards by suit, then count it by red cards and face cards, and check both against the real deck.

By suit: 13 + 13 + 13 + 13 = 52. Correct. By red-and-face: 26 + 12 = 38, but the real answer is 32. Six cards — the red face cards — got counted twice, once for being red and once for having a face. Notice that addition didn't go slightly wrong here: it was never legal in the first place, and nothing warned you.

So here's the repair, and the two conditions have earned their keep. A partition of a set is a collection of pieces that (1) don't overlap — every pair of pieces intersects in ∅ — and (2) cover everything — their union is the whole set. Suits are a partition of the deck. Red/face is not. When you have a partition, and only then, you get the addition rule: |A| + |B| = |A ∪ B| for disjoint pieces. Hearts and spades never overlap, so 13 + 13 = 26 cards, nothing to correct. Neither condition is new: an empty intersection, and a union that reaches everything, demanded at the same time.

02The pairing — and what "how many" really means

We can now say which things: sets, and the and/or/not grammar on top of them. The next step is small: two sets are sitting there, so connect them — reach into one and land on exactly one thing in the other. That's it. That's the whole idea, and it's called a function.

Now, I know what your mental image is, because it's everyone's: y = 2x + 1. A formula. Some algebra you feed a number and get a number out. Please put that down for a minute, because it's the single most expensive misconception in this chapter. It's why "probability is a function on sets" is going to sound like mysticism in Chapter 9 when it should sound like Tuesday.

Look at a vending machine instead. Press B4 and you get exactly one thing. A machine that gives you a Snickers on Tuesday and a Twix on Wednesday from the same button is broken — and you didn't need a definition to know that, you just know it. That feeling is "exactly one." Now notice what the machine does not have anywhere inside it: a formula. Its rule is a lookup table screwed to the inside of the door. Press the buttons.

So: a function is a rule pairing each element of a domain with exactly one element of a codomain. The domain is the buttons. The codomain is the shelf — everything the machine could conceivably dispense — and the range is what actually drops for some button. So why name a shelf that's bigger than what comes out? Because we want to describe the machine's type before we know its stock, and that is the entire reason a codomain exists.

And while we're here — y = ±√x is not a function. That isn't because a rule forbids it, but because it's a machine that drops two cans: 9 gives back both 3 and −3.

Now stare at a map's arrows for a second, because there are only two ways a bunch of arrows can be imperfect. Either two arrows crash into the same target, or some target is sitting there untouched, and that's the whole taxonomy, forced rather than invented. Drag the arrows and watch both alarms.

Now the names land on something you're already holding. No collisions means the map is injective, and nothing missed means it's surjective. Both at once and it's a bijection — a perfect pairing. Here's the way I've come to think about it: injective means nothing is lost (given the output, you can always recover the input), and surjective means nothing is wasted (every target earns its place).

And now the rung that almost every course on earth skips.

You're in a packed theatre: ten thousand seats, no seat numbers, people everywhere. Question: are there more seats or more people? You cannot count either one, because you'd lose your place by row forty and there's no way to check yourself. So do this instead: ask everyone to sit down, one person per seat, and look at what happens.

Nobody is left standing — so no two people crashed into one seat, and nobody missed out. That's injective. No seat is empty, because every seat got reached, and that's surjective. So the answer is: exactly the same number. And I want you to sit with how strange that is, because you now know it, with total certainty, and you never counted a thing.

So here's the move, and it's a promotion rather than a discovery. A bijection between two sets is precisely what "they have the same number of things" has always meant, and we just never said it out loud. "Same size" was never about numbers at all. It was about pairing, and numbers were the middleman all along, so we've just fired them.

Which sounds like philosophy until you notice what it does to counting. Go count three coffee cups on your desk — actually do it, out loud, finger moving. Now: what was your finger doing? It touched a cup and said "one," then touched another and said "two," and nothing was missed and nothing was touched twice. You were building a bijection between the cups and the ruler {1, 2, 3}, and you've been doing this since you were three years old without anybody ever naming it. Step through it, then break it.

So here is the definition, and every word of it was set by hand: |A| = n means a bijection exists between A and {1, 2, …, n}. The ruler has n things by definition — it's the yardstick, not a claim about the world. Counting a set is building a bijection to the ruler.

And now watch it turn from philosophy into a weapon, because "How many?" now has a strategy. If I can't point at the things, I don't give up. I pair them with something I can already count. Every single formula in the rest of this chapter is that one sentence wearing a different hat.

03Building things you can count

Let's cash that in immediately. Three shirts, two pairs of trousers: how many outfits? Don't compute it. Draw it, with shirts down the side and trousers across the top, so that every outfit is a cell.

Count the cells: three rows of two. That's it — that's where multiplication came from, and it isn't a rule about counting that someone handed down. It's the shape of a grid, and the phrase "rows of" is the multiplication. Here's what's actually doing the work: each outfit pairs with exactly one choice-tuple (which shirt, which trousers), and every tuple builds exactly one outfit. That pairing is a bijection, so counting outfits is counting tuples, and tuples are the cells of a grid.

That's the multiplication principle: make k choices in a row, with n₁, n₂, …, nₖ options at each step, and you build n₁ · n₂ ··· nₖ objects — three shirts, two trousers, 3 × 2 = 6 outfits. But it comes with a condition, and this is the exact inch where good students break. So let's break it deliberately.

Here are two situations that feel identical and aren't. First: a menu where ordering the fish deletes a wine option. Second: seating five people, where after you seat one, the set of remaining people has changed. Both feel like "the choices depend on each other." Both feel illegal. Only one is — so put the two grids side by side.

There it is, and the eye gets it before the words do. The menu's grid is ragged — different rows have different lengths, it isn't a rectangle, and the product lies. The seating grid is a rectangle — after you seat anyone at all, there are always exactly 4 people left, and it doesn't matter who you seated.

So say the condition exactly, because everyone states it vaguely: the number of options at each step must be fixed. Not the options themselves. The menu changed its length. The guest list only changed its membership. One is a rectangle, one isn't, and that is the entire difference between fluency and paralysis.

Good, so now run the multiplication principle to exhaustion. Line up 3 people out of 5: first slot 5 choices, second 4, third 3. That's 5 × 4 × 3 = 60, and notice you just solved it with no formula at all. Step through what happens when we try to write that in factorial notation.

So n! — read "n factorial" — is just n · (n−1) ··· 2 · 1: the multiplication principle run all the way down. And 5! is 5×4×3×2×1, which is too much — it has an extra 2×1 tail we never used. So kill the tail: 5!/2! = 5!/(5−3)!, which is 120/2 = 60 — the same sixty you just counted by hand. That's P(n,k) = n!/(n−k)!, the number of ways to arrange k things out of n. It is not magic and it is not new. It's 5×4×3 wearing a coat, and (n−k)! is precisely the part you never used, cancelled.

And 0! = 1. Not "by convention," because that's a teacher admitting defeat: two independent roads force it. Road one: how many ways to arrange zero things in a row? Exactly one, the empty arrangement — and remember from Section 1 that the empty thing is a real thing. Road two: arranging all n of them must give n!, and the formula we just built says it's n!/(n−n)! = n!/0!, which only works if 0! = 1. For n = 5 it reads 120/0!, and only 120/1 = 120 hands back 5! itself. Two roads, one answer, and it was never a convention.

One housekeeping note so notation never ambushes you. You'll see P(n,k), ⁿPᵣ, and (n)ₖ in different books. Three costumes, one idea — each of them says P(5,3) = 60, so you haven't missed anything.

04★ The overcount — the keystone of the chapter

Everything so far has been setup. This section is the chapter, and honestly it's most of combinatorics. So we're going to do it the hard way: you're going to answer a question, and you're going to get it wrong, and being wrong is the point.

Five people are in a room, and everyone shakes everyone else's hand exactly once. How many handshakes? Commit to a number before you touch anything, and really commit.

If you said 20, I want to be very clear about something: that is a good answer, and it isn't sloppy. You used the multiplication principle you just earned, and you used it correctly — pick a shaker (5 ways), then pick a shakee (4 ways), 5 × 4 = 20. Your recipe is airtight, and it really does produce 20 things.

So look at what it produced. "A shakes B" and "B shakes A" are two different recipes — and one handshake. Every single handshake in that room got built exactly twice. Not sometimes twice, not roughly twice, but exactly twice, every time. Your recipe didn't fail, because your recipe was 2-to-1, so: 20 / 2 = 10.

And there's the whole chapter, in one sentence you can carry for the rest of your life:

Count the easy thing. Ask how many times each answer got built. Divide by that.

You were never wrong. You were 2× right. And now you hold the general tool instead of a corrected number, so let's name it: the quotient principle, or the overcount principle. If a recipe builds each target exactly d times, then #targets = #recipes / d — the handshakes were 20 recipes at d = 2, so 20/2 = 10.

Now let's make the machinery visible on the smallest case that leaves nowhere to hide. Three people, choose two: write out all six orderings by hand — AB, BA, AC, CA, BC, CB. No formula, just a list you can look at. Now group them.

Three groups, and every group has exactly two in it — not roughly two, exactly, and you can see it. So 6/2 = 3. Now notice why you divided by 2, because nobody handed you a rule saying "order doesn't matter." You divided by 2 because you looked at the map and counted the fibres. Each group is a fibre: all the recipes that build one particular target.

Now weaponize it. Take n people and pick a committee of k, then line up all n of them: that's n! orderings. Call the first k the committee and the rest outsiders, and ask how many times each committee got built. Shuffle the k inside — k! ways, same committee. Shuffle the n−k outside — (n−k)! ways, same committee. So the map from orderings to committees is exactly k!(n−k)!-to-one — five people picking two gives 2 × 6 = 12 orderings per committee, and 120/12 = 10. Therefore:

C(n,k) = n! / (k!(n−k)!)

Read that again and notice what just happened: the formula arrived already understood. It's the first thing you computed with the tool — it isn't the tool, and that's the difference between owning combinatorics and renting it. One degree off the template — identical items, a circular table, a committee with a designated chair, two people who must sit together — and someone who memorized C(n,k) is stuck. You just find the map and count the fibres.

Two loose ends before we move. First, the test you'll actually use, and it's a question rather than a rule: relabel the order of your picks — did you get a different object? Different object means order is real, so it's a permutation, and same object means your recipe built it more than once, so divide it out. That works forever, because it's just the keystone asked as a question. And enjoy this one: a "combination lock" is a permutation lock. Everybody knows the word is wrong, nobody's fixing it, so reach for the test, never the noun.

Second: C(n,k) = C(n,n−k) — both C(5,2) and C(5,3) come to 10. You could verify that by cancelling factorials, which teaches you nothing and you'd forget by Thursday. Don't. Draw one line through the n people instead — k on the left, n−k on the right — and read it from both sides.

Choosing who goes is the same act as choosing who stays — one line, read two ways. That's a bijection, it's zero computation, and your eye finished the proof before this sentence did.

05When the overcount goes ragged

That division had a hypothesis, and nobody says it out loud. Go back to the three groups in Figure 14: all the same size, which is exactly why 6/2 was legal. Change one group's size and the division stops meaning anything. Division is legal only when every target gets built exactly the same number of times.

And when it isn't, nothing warns you: there's no error, you get a plausible wrong number, and you walk away happy. Let's watch it happen.

Ragged fibres, no division. That trapdoor sits under a large share of all combinatorics errors, and now you can see it before you fall in. Which leaves one question standing: if the overcount isn't uniform, what do you do?

Take three overlapping sets and try to count their union. Adding is illegal — we proved that with the deck back in Section 1, and these pieces obviously overlap. So instead of arguing about formulas, let's audit one dot: put a single point inside all three circles and give it a running tally.

Follow the ledger. It's in A: +1. In B: +1. In C: +1. Tally is 3 — that dot got counted three times, and it's one element, so subtract the three pairwise overlaps: −1, −1, −1. Tally is now 0, which means the dot has been erased. But it's a real element of the union, so it must count exactly once, and we add it back: +1. Done.

That's inclusion–exclusion: |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. The + on the triple term is not a sign rule you memorize. It's a repair, forced by watching one dot's tally go wrong. Drag the dot into exactly two circles and re-run it: +1+1−1 = 1 ✓, and the triple term never touches it. Every term in that formula is something you watched become necessary. Which is exactly why the four-set case is reachable instead of terrifying — you don't recall a pattern, you audit a dot.

Inclusion–exclusion is the keystone again. Almost nobody says that out loud, and it's the difference between one idea and a pile of formulas. You built a count, and it overcounted, but here the overcount is not uniform: the middle dot got built three times, the edge dots twice, the outer dots once. Ragged fibres. So you can't divide. You subtract, dot by dot, until every element's ledger reads exactly one.

Divide when the overcount is even. Subtract when it's ragged. One wisdom, two arithmetics.

One last tool, and it costs us nothing because we built it six rungs ago. Thirteen people are in a room, and assigning each person their birth month is a function: people → months. Now ask the only question that matters: could that function be injective?

If it were injective, we'd have a perfect copy of 13 distinct things sitting inside 12, and an injection can never grow a set. Impossible. So the function is not injective, and "not injective" means exactly what the arrow diagram showed: two arrows crash into one dot. Two people, same month. Done — one line, zero new machinery. That's the pigeonhole principle: there is no injection from a bigger finite set into a smaller one, so a collision is forced.

Now let me be honest about the part that's genuinely uncomfortable, because pretending it isn't is how you lose someone's trust. We just proved that two people in that room share a birth month — and we learned no name and no month. Mathematics flatly refuses to tell us which. That should feel strange. Sit in it for a second. And then flip it, because that strangeness is the power: pigeonhole is what you reach for when you can prove something must exist and could never find it by searching. It's why hash tables must eventually collide, and why no compression program can shrink every possible file — there are more files than there are shorter files, so some file must get bigger. Same one line, different room.

06Favourable over total — the first probability

We can count, so let's spend it. Flip two coins: what's the chance you get one head and one tail? Commit to a number, then run it.

A huge number of people say 1/3, and I want to defend that answer for a moment, because it's disciplined. The outcomes look like two heads, one head, two tails — three outcomes, one of them favourable, so 1/3. That's exactly the tool we taught you, applied carefully.

Now make one coin a penny and one a dime, and just look. Penny-heads/dime-tails and penny-tails/dime-heads are two different things sitting on the table, and they always were. The real outcomes are HH, HT, TH, TT — and two of those four are favourable, so the answer is 1/2. The simulation in that figure votes with reality, not with your gut: ten thousand flips park on 0.5 and never go near 0.33.

Here's the lesson, and it's the most expensive inch in this chapter. You weren't careless. Your Ω — your sample space, the set of all outcomes — was wrong. And a wrong Ω is invisible from inside the arithmetic, so you could check your division all day and never find it, because the bug isn't in the division. That's why nobody can debug this error on their own: they were never told that Ω is a choice they were making.

So state the rule with its hypothesis visible, the way it should always have been taught: P(A) = |A| / |Ω|, and this is legal only when Ω is partitioned into genuinely equally-likely atoms. And notice — that's exactly the multiplication-principle grid you already trust. Two coins, 2 × 2 = 4 cells, each cell one atom, each atom symmetric with the others, so one head and one tail reads 2/4 = 1/2. The grid was the honest Ω all along.

Every rung under that formula was set by hand in this chapter. Partition Ω into atoms — we built partitions. An event A is a union of atoms — we built unions. Count A, count Ω by pairing each against the ruler — we built counting. Nothing was borrowed, and nothing was assumed.

And now the last beat, which costs nothing because we pre-paid the debt thirteen steps ago at the vending machine. Look at what P actually is: it takes a SET and hands back a number. That's a function — and a function never needed a formula, and it never needed a numeric input, so it's the vending machine. The buttons are events. That sentence — probability is a function on sets — is the first line of Chapter 9, and you already own it.

So let's put the whole chapter in one picture. Every ×, every ÷, every − you'll ever write in a counting formula is bookkeeping for how many-to-one your map is.

That's Chapter 1. Look at what you're actually walking out with — and it's one sentence, not nine formulas: count the easy thing, ask how many times each answer got built, and correct for it — divide if the overcount is even, subtract if it's ragged. With that you can re-derive C(n,k), inclusion–exclusion and pigeonhole from nothing, with zero memory. And you can diagnose a wrong count as one of exactly three named diseases: a wrong sample space, an illegal addition across overlapping cases, or an uncorrected overcount. That turns "I got it wrong" into a debuggable event instead of a verdict on your intelligence.

And there's a bridge already under your feet. We counted finite collections all day — pair them with the ruler {1, …, n} and stop. But here's the question this chapter can't answer: what happens when the count doesn't stop? When the pairing runs on forever and you're adding up infinitely many shrinking pieces? That's a series, and it needs a limit. Hiding inside it is a single fact, a/(1−r): with a = 1 and r = ½ it reads 1/(1−½) = 2, exactly where 1 + ½ + ¼ + … lands. That one fact powers half the "hard" tricks in this entire course, along with its strange continuous cousin, e. That's next.