What one-one asks of distinct inputs, and what many-one allows

0:00Here are four diagrams, and between them they hold the whole of this topic. Each one has the same four inputs down the left — one, two, three and four — and a set of targets down the right. Each draws exactly four arrows, one leaving every input. That is what makes each of them a function: every input gets an arrow, and gets exactly one. The question we are about to ask is not about the left side at all.

0:31It is about the right. In the first diagram, the four arrowheads land on four different targets. In the second, the arrow out of one and the arrow out of two come down on the same target. In the third, the same thing happens again — one and two land together. In the fourth, the arrows cross each other on the way across, but they still finish on four different places.

0:58Count, in each diagram, the targets that take more than one arrowhead. Zero, one, one, zero. So two of the four are clean and two are not. Crossing arrows are not the problem. Two arrowheads on one target is the problem, and everything else here is about that one count. The clean diagrams have a name. A function is called one-one when no two different inputs share an output. Read that sentence literally and it tells you what to do: take every pair of distinct inputs, and check that their outputs differ.

1:38With four inputs that is six pairs, and six pairs is nothing. With fifty inputs it is one thousand two hundred and twenty-five. With a window of two hundred and one whole numbers it is twenty thousand one hundred. Double that window to four hundred and one and it becomes eighty thousand two hundred — very nearly four times the work for twice the domain. And most functions worth naming are not defined on a window at all.

2:09They are defined on all the counting numbers, or on the whole number line, where there is no last pair to reach. So the literal reading of the definition is not a method. It cannot be finished. There is exactly one job it is good for, and we will lean on it hard: a pair that does collide refutes the claim on the spot. Finding is possible. Exhausting is not.

2:39Before we give up on the literal reading, here is the one place it works perfectly. Take a domain of four numbers: minus one, nought, one and two. Two functions are written on it, and they look nothing alike. The first squares its input and then subtracts the input. The second measures the distance from its input to a half, doubles that distance, and subtracts one. Are they the same function?

3:08Two functions count as the same when they agree at every point of a shared domain — so with four points there are four things to check. The first gives two, nought, nought and two. The second gives two, nought, nought and two. Inputs at which they disagree: none. They are one function, written down twice. Now put our question to either of them. Six pairs, and two of those pairs collide: minus one with two, and nought with one.

3:41Four inputs is small enough to check every last pair, and that is exactly why every other example in this video is going to need a different reading of the definition. So here is the second reading, and it is the one that does the work. Instead of starting from two different inputs and hoping their outputs differ, start from the other end. Suppose two outputs are equal. Then show that the two inputs must have been equal all along.

4:14Those two sentences say the same thing. If equal outputs force equal inputs, then different inputs can never produce equal outputs — that is the same claim read backwards. But the second version is a proof you can actually run, because it starts from an equation. Take doubling on the counting numbers: x goes to two x. Suppose two x-one equals two x-two. Cancel the two. x-one equals x-two, and the argument is over.

4:49You never looked at a single pair. That is the whole difference between the two readings. The first asks you to survey infinitely many pairs. The second hands you one equation and asks you to solve it. Every proof of one-one-ness from here on has that shape: assume the outputs agree, and squeeze the inputs together. Let us write the definition down properly, in both its forms, because the two forms get used for different jobs.

5:22A function is one-one — the other word for it is injective — when distinct inputs always have distinct images. Equivalently: whenever two images are equal, the two inputs are equal. The first form is what the words mean. The second form is what you put on paper. And a function that is not one-one is called many-one. That is not a rival property with a theory of its own.

5:52It is simply the negation, and that matters more than it sounds, because it tells you exactly what each one costs to prove. To prove a function one-one you must handle every possible pair at once, which is why you need the second form. To prove a function many-one you need one pair. One pair of different inputs landing on one output, and there is nothing left to say. Watch how short that second job really is.

6:24Take the function that squares its input and adds one, on the whole number line. Feed it one: one squared is one, plus one is two. Feed it minus one: minus one squared is also one, plus one is two. Two different inputs, one output. Many-one. That is the entire proof. Notice what was not required. We did not describe all the collisions, and we did not say how many inputs pile onto each output.

6:55People often try to argue exactly that, and it is proving something far stronger than was asked. On a stand-in for the line — the numbers from minus five to five in quarter steps, forty-one of them — that function offers eight hundred and twenty pairs, and twenty of them collide. Twenty is a great many more than one, and one was already enough. The asymmetry is the thing to carry away.

7:23Refuting takes one example. Establishing takes an argument. Now the sharpest thing in this topic, and it is easy to miss because nothing about the formula changes. Squaring. x goes to x squared. Character for character the same rule, twice over. First on the counting numbers — take the first two hundred of them, one up to two hundred. Nineteen thousand nine hundred pairs, and collisions: none. The reason is visible in the steps.

7:58Walk up the counting numbers and every single step of the squaring function goes up. It never comes back down, so it never revisits a value it has already used. Now the same rule on the whole numbers with the negatives included — two hundred and one of them, from minus one hundred up to one hundred. Twenty thousand one hundred pairs, and collisions: one hundred. Minus one and one both square to one. Minus two and two both square to four. Every negative has a positive twin.

8:35Same formula. Different verdict. So being one-one is not a property of a formula. It is a property of a formula together with the domain it was declared on, and dropping the domain from the sentence makes the sentence meaningless. Cubing shows you the other side of that. On the counting numbers, nineteen thousand nine hundred pairs and no collisions; on the whole numbers with the negatives, twenty thousand one hundred pairs and still no collisions.

9:08A cube keeps the sign of its input, so a negative cube can never meet a positive one. Here is a function written in two cases, and it is the one that catches people out. On the counting numbers: if the input is odd, add one; if it is even, subtract one. So one goes to two, two goes to one, three goes to four, four goes to three, five goes to six, six goes to five.

9:38It swaps them in pairs. Apply it twice to any of the first two hundred counting numbers and you land back exactly where you started — all two hundred of them. Is it one-one? The tempting move is to check the odd rule, check the even rule, and declare victory. That is not enough, and the reason is that a collision does not have to stay inside one case. So there are three things to rule out, and the interesting one comes first.

10:10Suppose an odd input and an even input shared an output. Then the odd one plus one equals the even one minus one, which makes the even one exactly two more than the odd one. But two more than an odd number is odd, and we assumed it was even. Impossible, so that case is closed. Within the odd inputs: add one to each side and cancel — the inputs were equal.

10:38Within the even inputs: subtract one from each side and cancel — same again. Collisions across the cases, collisions among the odds, collisions among the evens: none, none and none, across all nineteen thousand nine hundred pairs. And look at what this function is not. Its steps run down, up, down, up, down, up. It is one-one and it rises nowhere for long. Being one-one has nothing whatever to do with going steadily upward.

11:14One-one functions do not have to be clever. Here is a thoroughly dull one, and it is dull on purpose. A class of fifty students, and the function that sends each student to their student number. Is it one-one? Suppose two students had the same student number. In a register where numbers are handed out one per student, that means they are the same student. Done. One thousand two hundred and twenty-five pairs of students, and no collisions.

11:48Now notice where the reason came from. It is not a fact about algebra. It is a fact about how a register is kept. The shape of the proof does not care in the slightest. Assume the outputs agree, derive that the inputs agree — whether the derivation runs on cancellation or on office procedure. And break the register — hand two students one number — and the very same walk turns up the collision at once.

12:19So that zero is a reading, not an assumption. Graphs make collisions visible, and the device is worth having in your hands. Draw the parabola: the graph of x squared over the number line. Now draw a horizontal line straight across it at height one. It meets the curve twice, at minus one and at one. Two points on one level line means two inputs with one output, and that is a collision you can see rather than compute.

12:52Slide the line down to height nought and it meets the curve exactly once, at the bottom of the bowl. So the test is genuinely testing something. Not every level line cuts twice. Slide it lower still and it misses the curve altogether. Which gives the rule: a function is one-one exactly when no horizontal line meets its graph more than once. And here is a warning the picture makes obvious.

13:21The right-hand half of that parabola is perfectly one-one — over there it only ever climbs. But one-one is a claim about the whole declared domain, not about a stretch of it you happen to like. On the full line the parabola is many-one, and its good behaviour on the right does not rescue it. Three standard functions now. All three are many-one, and each one dies of a different kind of collision.

13:52First the modulus function, which sends each input to its distance from nought. On a stand-in of seventeen points, one hundred and thirty-six pairs, and eight of them collide. Minus one and one both give one; every number is twinned with its negative, so the collisions come in matched couples. Second, the signum function, which reports only the sign of its input: one for a positive number, nought for nought, minus one for a negative.

14:26Same seventeen points, same one hundred and thirty-six pairs — and fifty-six collisions. That is a completely different sort of failure. Its whole output set holds three values, so on an infinite domain collisions are not bad luck, they are forced. One and two will do it: both positive, both sent to one. Walk it from point to point and you can see why. Of those steps, fourteen are flat, two rise, and none at all falls.

14:58It never once goes down, and it still is not one-one, because flat is quite enough. Third, the greatest-integer function, which rounds each input down to the nearest whole number. On the tenths from nought to three, four hundred and sixty-five pairs, and one hundred and thirty-five of them collide. One point two and one point five both give one. It climbs in steps and lies level in between, and every level stretch is a collision waiting to be named.

15:33Now a trap that almost everybody walks into. If two functions are each one-one, is their sum one-one? Take sine and cosine on a quarter turn, from nought up to a right angle, and sample five points across it. Sine: ten pairs, no collisions. It climbs the whole way. Cosine: ten pairs, no collisions. It falls the whole way. Each of them is perfectly one-one there. Now add them. Ten pairs, and two collisions.

16:05Look at the two ends. At nought, sine is nought and cosine is one, so the sum is one. At the right angle, sine is one and cosine is nought, so the sum is one again. Two different inputs, one output. Across those five points sine takes five distinct values and cosine takes five distinct values — and their sum takes three. The sum rises and then comes back down, and everything on the way back runs into something on the way up.

16:39Here is the same lesson with nothing to hide behind. The function that returns its input is one-one. The function that returns minus its input is one-one. Add them and you get nought, everywhere. On the three inputs minus one, nought and one, that sum has three pairs and all three of them collide. Being one-one simply is not preserved by adding. Finally, counting. How many one-one functions are there from a three-element set to itself?

17:14There is a cheap way to answer and an honest way, and they agree. The honest way: write down every function from the set to itself. Each of the three inputs may be sent to any of the three outputs, which gives twenty-seven functions in all. Test each one for a collision. Six of them survive. And those six are exactly the rearrangements: one two three, one three two, two one three, two three one, three one two, three two one.

17:48Every one-one function from a finite set to itself is a shuffle of that set, because with nowhere spare to go, distinct inputs have to fill every place exactly once. Give the outputs more room and that stops being true. From three elements into a four-element target there are sixty-four functions, and twenty-four of them are one-one — more than six, because now there is somewhere to leave empty. Here is one of those twenty-four.

18:20Three inputs go to four, five and six, inside a target holding four, five, six and seven. Three pairs, no collisions, so it is one-one — and seven receives nothing at all. Being one-one and covering the target are two entirely separate questions, and this function answers them differently. So, what it all comes to. One-one means no two different inputs share an output, and many-one is just the failure of that. Nothing more.

18:55Reading the definition forwards tells you what it means. Reading it backwards — equal outputs force equal inputs — is what you write down, because it starts from an equation instead of from infinitely many pairs. Proving many-one costs one pair. Proving one-one costs an argument. The verdict belongs to the formula and the domain together, and never to the formula on its own. Squaring is the proof of that: on the counting numbers it collides with nothing, and once the negatives are let in there are one hundred collisions.

19:35Watch case splits, because the collision you missed is usually the one that crosses between the cases. Watch flat stretches on a graph, and watch for level lines that cut twice. And do not assume the property survives anything you do to it — two functions that are each one-one can add to one that is not.