Invertibility as a two-sided undo, and why bijective is exactly the condition

0:00Everybody has an idea of what undoing a function ought to mean. You put something in, something comes out, and a second machine takes that output and hands you back what you started with. That intuition is right, and it is also exactly half of the definition. The definition asks for two equations, not one. Take a function from a set X to a set Y. It is called invertible when there is some function going the other way, from Y back to X, such that two things hold at once.

0:36Run the original first and then the second one, and you get back every element of X unchanged. Run the second one first and then the original, and you get back every element of Y unchanged. Two composites. Two orders. And two different identity functions — one living on X, the other living on Y. Those two identities are not the same object. When X and Y are different sets, they are visibly different things, and the whole topic turns on keeping them apart.

1:12When that second function exists, it is called the inverse, and it is written with a superscript minus one. So here is the shape of what follows. The first equation and the second equation are independent demands, they buy you different things, and there are perfectly ordinary functions that satisfy one and fail the other. Which is why one-one and onto is not a lucky test that happens to detect invertibility. It is the two halves of the definition, read separately.

1:50Take the first equation on its own and ask what it is really demanding. It says: start anywhere in X, push forward through the function, then pull back through the undo, and land on the element you started at. Every input must be recoverable from its own output. Think about what that rules out. Suppose two different inputs had the same output. Push both forward: they arrive at the same place. Now pull back.

2:20The undo is a function, so it gives one answer for that place. One answer cannot be two different inputs. So the first equation cannot hold if any two inputs collide. It forces the function to be one-one. Notice how little that argument used. It never mentioned the target set. It never asked whether anything was reached. It looked only at the input side. And that is the first half of the definition earning exactly one of the two properties, and no more.

2:57Now the second equation, and it is a genuinely different demand. It says: start anywhere in the declared target Y, pull back through the undo, then push forward through the function, and land on the element of Y you started at. Read that as a construction rather than a check. Given any target y, the undo hands you an element of X. Call it g of y. The equation says the function sends that element to y.

3:29So g of y is an input that reaches y. Every target has one. That is exactly what onto means, and we have just built the witness rather than searched for it. Again, notice what the argument did not use. It never compared two inputs. It never asked about collisions. It looked only at the declared target. So the second half of the definition earns the other property, and no more.

3:58One equation for each demand. That is the whole architecture, and everything else in this video is consequences of it. Here is the claim we are working towards, in both directions. A function is invertible exactly when it is one-one and onto. If it is invertible, then it is one-one and it is onto — and we have just seen both, one from each equation. If it is one-one and onto, then it is invertible — and that direction we have not seen yet, because it asks us to produce an undo out of nothing but those two properties.

4:40That second direction is the one with real content, and it is also the one that pays. It is what lets you prove a function invertible without ever writing its inverse down. So we are going to prove it, rather than assert it. And it is worth saying plainly that this is being supplied. The statement is standard and the argument is short, but a claim of the form 'exactly when' is two proofs, and skipping one of them is how people end up believing that finding a formula is what invertibility means.

5:19Let us put the forward direction on the board properly, because the shape of it matters more than the conclusion. Assume some undo exists that satisfies both equations. First equation. Suppose two inputs, call them a and b, have the same output. Apply the undo to both sides of that equality. The left side collapses to a. The right side collapses to b. So a equals b, and there was never a collision at all.

5:51One-one, from the first equation alone. Second equation. Take any element y of the declared target. The element g of y sits in X, and the function sends it to y. So y is reached. Onto, from the second equation alone. Two paragraphs, two properties, and neither paragraph borrowed anything from the other. That independence is not a stylistic point. It is the reason a function can have one equation and not the other, which is where we are going in a moment.

6:29Now the other direction, which builds the undo instead of assuming it. Assume the function is one-one and onto. We want to define a function from Y back to X. Take a target y. What should the undo send it to? Obviously: to an input that lands on y. So the question is whether there is exactly one such input. Onto says there is at least one, because every target is reached.

6:59One-one says there is at most one, because two different inputs could not both land on y. At least one and at most one is exactly one. So the rule is well-defined, and a rule that gives exactly one answer for each input is a function. Look at where the two properties were spent. Onto bought existence. One-one bought uniqueness. A rule needs both before it is a function at all, and neither could have done the other's job.

7:31And the two equations hold by construction. Push an input forward and pull it back and you return to it, because it was the unique input landing there. Pull a target back and push it forward and you return to it, because that is what the rule was built to do. This is what a computer does when you ask it to build an inverse. It walks the declared target, collects the inputs landing on each element, and reports two separate failure counts: how many targets had none, and how many had more than one.

8:08For the function we will meet in a moment, twelve targets, none with nothing landing on them, none with more than one thing landing on them. Both counts nought, so the inverse exists. Those two counts are onto and one-one, measured rather than asserted. Now the case that makes all this concrete, and it is the sharpest thing in the topic. A function can have an undo that works on one side and not the other, and it is not invertible.

8:41Take doubling on the counting numbers. On a window of forty inputs and forty declared targets, it has no collisions and leaves twenty targets unreached — every odd one. One-one, not onto. So by the claim it should not be invertible. Let us see the definition catch it. Here is a candidate undo. Halve every even number. And send every odd number to one, because it has to go somewhere.

9:11Now check the first equation. Take any input, double it, halve it. You are back where you started, every time. Forty inputs tried, nought failures. The first equation holds completely. So this really is an undo. It is not a broken one. It recovers every input. Now the second equation. Take the target one. The undo sends it to one, because one is odd. Then double: you get two. Two is not one. The second equation fails at the very first target.

9:48Across the window: forty targets tried, twenty failures, the smallest being one. So the reading for this pair is nought failures on the input side and twenty on the output side. And the builder agrees from its own direction: forty targets, twenty with nothing landing on them, none with more than one. This function has a genuine one-sided undo and is not invertible. The two equations are not two ways of saying the same thing.

10:22Now the mirror image, because a matched pair is much more convincing than one example. Take the folding function. It sends one to one, it sends two to one as well, and it sends everything above two to one less than itself. Read over forty-one inputs against a declared target of forty, it has one collision — the pair one and two — and nothing unreached. Onto, not one-one. The other half.

10:52Here is a candidate undo for it: send one to one, and send every target from two upwards to one more than itself. Check the second equation first this time. Take any target y. If y is at least two, the undo hands you y plus one, which is above two, and the fold sends it back down to y. And the target one comes back to one. Forty targets tried, nought failures.

11:21So the second equation holds completely, which is the equation doubling failed. Now the first equation. Take the input two. The fold sends it to one. The undo sends one back to one. One is not two. Forty-one inputs tried, one failure, and it is at the input two. Put the two side by side. Doubling: nought failures on the input side, twenty on the output side. The fold: one failure on the input side, nought on the output side.

11:56One function with each half of the definition, and neither of them invertible. The builder catches the fold from its own side too: forty targets, none unreached, but one target with more than one input landing on it. And it refuses to hand back a function on the strength of that alone. So if the output-side equation is what fails so often, there is an obvious question. Can you arrange for it not to?

12:29Yes, and it is done constantly, usually without comment. Take the function sending x to four x plus three, on the counting numbers. Declare the target to be all the counting numbers, and over the first twelve inputs against fifty-one declared targets you get no collisions and thirty-nine targets unreached. The builder refuses. Fifty-one targets, thirty-nine with nothing landing on them. Now change nothing about the rule and declare the target to be exactly the numbers of the form four x plus three: seven, eleven, fifteen, and so on up to fifty-one for our twelve inputs.

13:14Same rule. Every one of the twelve inputs goes to exactly the same place as before. But now: no collisions, nothing unreached. Twelve targets, none empty, none doubled. The builder hands back a function. And the stated formula for that inverse — take three away and divide by four — passes both equations. Twelve inputs returned, twelve targets returned, nought failures either side. Notice that the declared target is doing real work here, and not decoration. Take three away from an arbitrary counting number and divide by four and you will usually not get a counting number at all.

14:01The formula for the inverse is not a function on the whole of the counting numbers. It is a function on the set that was declared, and that is why the declaration had to be trimmed. This is the general move: a co-domain declared to be exactly the range makes the output-side equation attainable, by construction. It is not cheating, but it is worth seeing done, because a function handed to you as invertible has usually had this done to it already.

14:37Now the payoff, which is the practical reason any of this matters. To prove a function invertible you do not have to produce its inverse. You prove it is one-one and you prove it is onto, and you are finished. That is not a shortcut past anything. The construction we did earlier turns those two properties into the inverse, so nothing has been skipped. You simply never write the formula.

15:06Here is one worth doing. Take the quotient of x minus two by x minus three, with three removed from the source and one removed from the target. Read over a stand-in of forty points: no collisions, nothing unreached. So it is invertible, and we are done. No formula was written. The builder confirms it from the other side: forty targets, none empty, none doubled, and it hands back a function.

15:37And if you do want the formula, it is the quotient of three y minus two by y minus one, and it passes both equations — forty inputs returned, forty targets returned, nought failures either way. But that was optional. Notice also why one had to be removed from the target. Set the quotient equal to one and you need x minus two to equal x minus three, which nothing satisfies. Across the forty points, the number of inputs landing on one is nought.

16:15So one is a target that could never be reached, and leaving it declared would have broken the output-side equation for no good reason. Here is a second one, for the same treatment. Send x to x divided by one plus the size of x. On a stand-in of forty-one points: no collisions, nothing unreached, and the largest size any output reaches is ten elevenths — comfortably inside one, which is why the declared target is the numbers strictly between minus one and one.

16:52Its inverse sends y to y divided by one minus the size of y, and it passes both equations. But again, one-one and onto had already settled it. Two last things, and the first is the easiest inverse there is. Some functions are their own inverse. Take the function that sends every odd number to one more than itself and every even number to one less. One to two, two to one, three to four, four to three, five to six, six to five.

17:28It has no collisions and leaves nothing unreached, so it is invertible. And run it twice: an odd number rises to the even one above it and comes straight back down. Both equations hold with the function itself as the undo. Forty inputs returned, forty targets returned, nought failures either side. So the inverse is the function itself. The reciprocal does the same thing. On a set closed under inversion — forty-two points here — it has no collisions and nothing unreached, and the reciprocal of the reciprocal is what you started with. Nought failures on both equations.

18:13Which brings us to the last thing, and it is a notation trap that the reciprocal is directly responsible for. The superscript minus one does not mean one divided by the function. For the reciprocal those two happen to be the same thing, and that coincidence is exactly what entrenches the mistake. So take a function where they are not. Send x to three minus four x. On a grid of forty-one points it has no collisions and nothing unreached, and its inverse sends y to three minus y, over four — which passes both equations.

18:55Now evaluate both things at the input nought. The inverse gives three quarters. One divided by the function gives one third. Three quarters against one third. Different numbers, and in fact across the whole grid the two never agree anywhere at all. The superscript is a name for the undo. It is not an exponent, and it is not a division. And that is the topic. Two equations, not one. Each buys exactly one property. Together they build the inverse, which is why proving one-one and onto is the whole job, and why a function with an undo on one side only is a real thing and not a paradox.