Bijections, and why on a finite set either half implies the other

0:00Two demands have been made of functions so far, and they have been kept apart on purpose. One: no two different inputs share an output. Two: every element of the declared target is reached by something. A function that meets both at once has a name. It is called bijective, or in longer words, one-one and onto. And that is all the word means. It is not a third property with a theory of its own; it is a label for holding both, and every proof that something is bijective is two proofs written one after the other.

0:40Here are four arrow diagrams, and it is worth reading each of them twice — once for each demand. Read as a pair of numbers, collisions first and unreached targets second, they come out: nought and two; one and three; one and nought; and nought and nought. The first has no collision and misses two targets. The second collides once and misses three. The third collides once and misses nothing.

1:09And the fourth collides nowhere and misses nothing. Diagrams meeting both demands: one out of the four, and it is the last one. The other three between them fail in three different ways, which is already a hint that the two demands are pulling in different directions. This video is about when they stop being independent. First, the case for their being genuinely separate. You could imagine that meeting one demand tends to drag the other along with it, and on small pictures it can look that way.

1:46So here are two functions, both defined on the counting numbers, both going to the counting numbers, and each holding exactly one of the two halves. The first is doubling: x goes to two x. On a window of forty, its collisions number nought. It never sends two different inputs to one place. Is it onto? Build the input that would reach a target: half of it. Forty targets tried, twenty of them refused by the domain, and none went astray.

2:20Every odd target needs a half that is not a counting number, so the smallest thing it misses is one. One-one, and not onto. The second function is a fold. Send one to one, send two to one as well, and send everything above two to one less than itself. Forty-one inputs into a target of forty: collisions, one — the pair one and two. Unreached, nought. Onto, and not one-one.

2:50Two functions on the same infinite set, one half each. So in general the two demands are independent, and no amount of one buys you any of the other. Now hold that thought and change the setting completely. Take a finite set — say four things — and a function from that set back into the same set. Think of the target as four slots, and think of the function as spending outputs into them.

3:21Every input produces exactly one output. That is what makes it a function. Now suppose it is one-one. Then no two inputs land in the same slot, so each of the four inputs spends a slot nobody else has used. Four inputs, four distinct slots used, four slots available. There is nothing left over. Every slot is full, which is to say every target is reached. The function is onto, and we never checked for coverage — we counted.

3:55Now run the same argument backwards. Suppose instead that it is onto. Then every one of the four slots has something in it, so at least four distinct outputs were produced. But there are only four inputs to produce them with. If any two inputs had shared an output, there would be at most three distinct outputs to go round, and a slot would be empty. So no two inputs share, and the function is one-one.

4:24One counting fact, used twice, in opposite directions. Let us do that on three elements, slowly, because the shape of each argument is worth having. The set is one, two, three, and the function goes from that set back to itself. First claim: if it is onto, it is one-one. Argue by contradiction. Suppose two of the three inputs collided — say they share an output. That accounts for one output between the two of them.

4:57The remaining input has exactly one output of its own. So the whole function produces at most two distinct outputs. And two distinct outputs cannot cover a target that has three elements in it. That contradicts being onto, so no two inputs collided. Notice what the contradiction says and what it does not. It says the range would have at most two elements. The target still has three — those are different sets, and mixing them up is what makes this proof feel like a trick.

5:32Second claim, and this one runs forwards with no contradiction at all. Suppose the function is one-one. Then its three inputs go to three distinct outputs. Three distinct elements chosen from a set that has only three are all of it. So every element is reached, and the function is onto. Two short arguments, and between them an equivalence. Now say it once, for any finite set. Let the set have some number of elements — call it n — and let the function go from that set back into itself.

6:10If it is one-one, its outputs are n distinct elements sitting inside a set that holds only n. They are therefore all of it, and it is onto. If it is onto, then all n elements are outputs, so at least n distinct outputs were used. Only n inputs are available to make them. So no two inputs can share, and it is one-one. Both halves lean on a single fact: a set of n elements cannot also hold n distinct things that leave part of it out.

6:45That is the pigeonhole principle wearing two hats. And now a warning, because the statement is more conditional than it looks, and flattening it is the commonest mistake made with it. It is a statement about a function from a set to itself. The two sizes have to match. Here is a function from a three-element set into a four-element one, sending one, two and three to four, five and six.

7:14Its collisions: nought. Its unreached targets: one — the fourth element gets nothing. One-one and not onto, on finite sets, because the sizes are different. The same counting argument does give the version for two different finite sets of equal size, and we will measure that in a moment — but that version is an extension, not the statement itself. An argument is one thing. Let us go and count.

7:46Take a finite set and enumerate every single function from it back to itself. Not a sample — every one. Then put each function into one of four boxes. Box one: meets both demands. Box two: no collision, but something unreached. Box three: something collided, but nothing unreached. Box four: fails both. Nothing about this sorting knows the theorem. Two separate routines are asked two separate questions, and neither is ever told what the other found.

8:23So all four boxes are perfectly able to come back full. On a one-element set there is one function, and the boxes come out one, nought, nought, nought. On two elements there are four functions: two, nought, nought, two. On three elements there are twenty-seven functions: six, nought, nought, twenty-one. On four elements there are two hundred and fifty-six functions: twenty-four, nought, nought, two hundred and thirty-two. Look at the middle two columns. Nought, every time.

8:59Not one function in any of those families held one demand without the other. And the counts add up to every function there is — one, four, twenty-seven, two hundred and fifty-six — so nothing was quietly skipped. That is what the theorem looks like when it is counted rather than argued. Two empty boxes are only interesting if those boxes can fill, so let us make them fill. Run exactly the same census, with the same two routines, on functions from a three-element set into a four-element one.

9:38There are sixty-four such functions, and the boxes come out: nought, twenty-four, nought, forty. The second box, which was empty every time before, now holds twenty-four functions — every one of them one-one and none of them onto. Now go the other way, from a four-element set into a three-element one. Eighty-one functions, and the boxes come out: nought, nought, thirty-six, forty-five. The third box now holds thirty-six. So the two boxes are not empty by construction, and they were not empty because the routines could not fill them. They were empty because the sizes matched.

10:23And to check it really is the sizes and not some accident of the set being the same set, run the census between two different three-element sets. Six, nought, nought, twenty-one — identical to the earlier reading on one set with itself. So the extension to two finite sets of equal size is real, and it is measured rather than hoped for. Now the question the whole video has been walking towards.

10:54The finite proof needed one step: n distinct outputs, sitting inside a set of size n, exhaust it. Which of those words fails when the set is infinite? Not distinctness. Take doubling on the counting numbers and look at the first ten inputs. They produce ten distinct outputs. On the first twenty inputs, twenty distinct outputs. On forty, forty. It never repeats. The distinctness holds perfectly well. The step that fails is the words sitting inside.

11:30Of those ten distinct outputs, how many actually lie inside the window of ten? Five. The other five have fallen out past the end. Of the twenty, ten inside and ten outside. Of the forty, twenty inside and twenty outside. Half the outputs leave the set they were supposed to be filling. So the window has unreached elements — five, then ten, then twenty — even though nothing collided. Compare that with a function that does stay inside. The identity on forty produces forty distinct outputs, and all forty of them are inside the forty. Nothing is left over.

12:14That is the entire difference. On a finite set, distinct and inside forces exhausted. On an infinite one, as many as carries no information, because the count is not a number, and the outputs are free to be as numerous as the set and still miss half of it. Put the two witnesses side by side now, because with the counting argument in hand they read differently. Doubling: no collisions, and half its declared target unreached.

12:49The fold: one collision, and nothing unreached. Each is missing exactly one half of bijectivity, and each is on the same infinite set. Here is a third one, and this is the shape that catches people in exercises, because you have to find the collision yourself. Send an odd number to half of one more than itself, and an even number to half of itself. So one goes to one, and two also goes to one.

13:20On a window of forty its collisions number twenty. It is not one-one. But it is onto: every target m is reached from two m, which is always a counting number. Forty targets tried, none refused, none astray. And notice something about that last check, because it matters for how you answer questions like this. If you had searched a window of forty for unreached targets, you would have found twenty of them and concluded it was not onto.

13:52That conclusion would be wrong. Those targets are reached — from inputs above forty. A window search can only refute coverage when the input that would be needed is forced to lie inside the window, which is exactly the case for doubling and exactly not the case here. So the two-step proof settles the infinite cases, and looking at a picture does not. The collapse failing on an infinite set does not mean bijections of infinite sets are impossible. That is a different claim and it is false.

14:31Here is one you can draw completely. Send every odd number to one more than itself, and every even number to one less. So the first six inputs go to two, one, four, three, six, five. It swaps one with two, three with four, five with six, and never stops. On a window of forty: collisions, nought. Unreached, nought. Both demands met. The coverage argument names its input for each kind of target, and it is worth seeing done rather than asserted.

15:05For an odd target, take the even number one above it. Feed in two, four, six and out come one, three, five. For an even target, take the odd number one below it. Feed in one, three, five and out come two, four, six. Every target has its input named, so nothing is missed. One more thing about this function, which we will come back to properly later. Apply it twice and every one of the forty inputs comes back to itself.

15:38It is its own undoing, which is the strongest possible way of being a bijection. Everything so far has been a set mapping to itself. Here is a bijection between two genuinely different sets. Take a set of three things and a set of four things, and form all the ordered pairs with the first entry from the first set and the second from the second. There are twelve such pairs.

16:07Now form all the ordered pairs the other way round. Twelve of those as well. And the function between them is the simplest one imaginable: swap the two slots. Is it one-one? If two swapped pairs are equal then they agree slot by slot, so the originals agreed slot by slot too. Collisions: nought. Is it onto? Any pair on the other side is the swap of the corresponding pair on this side. Unreached: nought.

16:40Both demands, so it is a bijection. And notice what that buys you. The two collections have the same size — and the bijection is the reason, not a consequence of separately counting them. Two more, quickly, for practice. A rule that removes one point from each side: the quotient of x minus two by x minus three, with three taken out of the source and one taken out of the target.

17:10Forty targets tried, none refused, none astray, and no collisions among the inputs it produced. A bijection, manufactured by removing exactly one point from each side. And a pair often set as a multiple choice. The fourth power on a stand-in for the line: twenty collisions and thirty-nine targets unreached, so it fails both demands. Tripling on the same stand-in: no collisions, and forty-one targets tried with none refused and none astray. It meets both. That one is a bijection.

17:51Here is where all this pays for itself. How many onto functions are there from a set of n things to itself? That question looks like hard combinatorics. Counting surjections directly means inclusion and exclusion, and it is a genuinely awkward calculation. But by the result we just measured, an onto function from a finite set to itself is automatically one-one. So the onto functions are exactly the one-one functions. Same set of functions, described two ways.

18:28And a one-one function from a finite set to itself is a rearrangement of it — nothing is left over and nothing is doubled up. The rearrangements of n symbols number n factorial. So the answer is n factorial, and no surjection was ever counted. Check it against the census. Functions with no collision, for sets of one to four elements: one, two, six, twenty-four. Functions with nothing unreached, for the same four sets: one, two, six, twenty-four.

19:04And the factorials: one, two, six, twenty-four. Three columns, arrived at three different ways, and they agree all the way down. For three elements the six are just the six orderings: one two three, one three two, two one three, two three one, three one two, three two one. Anyone who starts an inclusion-and-exclusion calculation on that question has missed a theorem they already had in hand. So, what it comes to.

19:38Bijective means both demands at once, and it is proved as two proofs, never one. In general the two demands are independent: doubling has one half, the fold has the other, and both live on the same infinite set. But for a function from a finite set to itself they collapse into a single demand, and the reason is counting rather than anything analytical. Measured over every function there is, on sets of one, two, three and four elements, the two mixed boxes came back empty every time — and they fill the moment the two sizes differ.

20:20The step that fails on an infinite set is not distinctness. It is the requirement that the outputs stay inside. And here is a thought to leave with. We have been treating finite as the obvious idea and the collapse as the surprising consequence. You could turn that round. You could take the collapse as the definition — a set is finite exactly when every one-one function from it to itself is onto.

20:51An infinite set is then precisely one that has a one-one function to itself that misses something, and doubling on the counting numbers is a witness that the counting numbers are infinite. That is not the definition you were taught, and it is not being examined. But it is a real one, and it tells you that this equivalence is not a convenience. It is the thing that tells finite and infinite apart.