Feeding one function into another, and why swapping them changes the answer

0:00Here are two machines. You put something into the first, it hands out a result, and that result goes straight into the second. Nobody looks at what comes out of the middle. You put something in at one end and take something out at the other, and the pair of them behaves like a single machine. That single machine is what this video is about. But there is one thing that has to be true before you can wire them up at all, and it is not about the rules. It is about the sets.

0:32The first machine has a set it takes its inputs from, and a set its outputs are declared to lie in. The second machine has the same two declarations of its own. For the plug to fit, the first one's declared output set has to be the second one's declared input set. Not overlap with it. Be it. When that holds, you get a new function, and it runs from the first machine's input set to the second machine's output set.

1:04Notice which two sets those are. The first and the last. The middle set does the connecting and then disappears from the description. The whole of this topic is two consequences of that picture. The first is that swapping the two machines usually gives you something that cannot be wired up at all, because the plug no longer fits. The second is that even when both orders can be wired up, they are in general different machines, because whichever one you put first is the one that touches the input.

1:40So order matters twice over, and neither of the two reasons is about arithmetic. Before anything else, the notation, because it is written in the opposite order to the way it acts, and almost every slip in this topic comes from that. Call the first machine f and the second machine g. The composite is written g circle f. The letter of the machine that acts SECOND is written FIRST.

2:11The reason is the value rule. To find where the composite sends an input x, you write g of f of x. Read that from the inside out. The x is innermost. The letter nearest to it is f, so f is what touches the input. Then g is applied to whatever f produced. So the letter closest to the input in the value rule is the one that goes first, and when you compress that into a name, that letter ends up on the right.

2:43There is no deep reason for it. It is the same convention that makes you read a nest of brackets from the inside. Say it once to yourself in the form you will need: in g circle f, f acts first. Everything else in this video assumes you have that the right way round. Let us follow one element the whole way through, because the picture is worth having before any numbers.

3:12Three sets, side by side. Call them A, B and C. The first function carries A to B. The second carries B to C. Pick one element of A. The first function sends it somewhere in B. That element of B is not the answer. It is a waypoint. The second function now sends it somewhere in C. And that is the answer. One input in A, one output in C.

3:40Now draw the arc that skips the middle: it starts in A and ends in C, and it is the composite. The arc is the whole point of the diagram. It starts at the first oval and it ends at the third. Which means the composite's declared input set is A and its declared output set is C. It is worth being blunt about this, because it is a standing mistake: the composite's output set is not B. B was the connector.

4:13Now some actual numbers, and we will push four inputs through, one at a time. The first function takes its inputs from the set two, three, four, five, and its outputs are declared to lie in the set three, four, five, nine. It sends two to three. It sends three to four. And it sends both four and five to five. The second function takes its inputs from that same set — three, four, five, nine — and its outputs are declared to lie in the set seven, eleven, fifteen.

4:50It sends both three and four to seven, and both five and nine to eleven. Check the plug before anything else. The first function's declared output set has four members, the second's declared input set has four members, and nothing in the first is missing from the second. They are the same set, so the composite exists. Now push. Two goes to three, and three goes to seven. So the composite sends two to seven.

5:22Three goes to four, and four goes to seven. So the composite sends three to seven as well. Four goes to five, and five goes to eleven. So four goes to eleven. Five goes to five, and five goes to eleven. So five goes to eleven too. There is the whole composite: two and three to seven, four and five to eleven. And its declared sets are the first set and the last set: from two, three, four, five, to seven, eleven, fifteen.

5:57Now read those four values, because they say more than the arithmetic did. Count the collisions — the pairs of different inputs that end up in the same place — and count the declared targets that nothing reaches. The first function on its own: one collision, four and five, and one unreached target, nine. The second function on its own: two collisions, and one unreached target, fifteen. The composite: two collisions, and one unreached target, fifteen.

6:31So the composite has two collisions, and they came from two different places. Four and five were already stuck together by the first function. That collision was inherited — nothing the second function did could have separated them. But two and three were NOT stuck together by the first function. It sent them to three and to four, which are different. They collide because the second function folds three and four together. That collision was invented on the second stage.

7:05So of the composite's two collisions, one was inherited and one was made. Composition can only ever add collisions; it can never undo one. Missed targets work the same way. Fifteen is unreached by the composite, and the reason is upstream: the second function never produces fifteen from anything. That is the general shape. A composite is at most as well behaved as its factors, and often worse. And the converse of that is worth stating, because it is the one direction that does hold: if both factors are one-one, the composite cannot collide.

7:49That is not an opinion. Take three elements through four to four, and count every pair of one-one functions there is: five hundred and seventy-six pairs, and not one composite among them collides. Let the SECOND function be any function at all and the same census gives six thousand one hundred and forty-four pairs, of which three thousand eight hundred and forty fold something together. Let the FIRST be free instead and you get one thousand five hundred and thirty-six pairs, nine hundred and sixty of them folding.

8:27So a colliding composite is something that census is perfectly able to find. It found thousands of them. It just never finds one when both factors are clean. Now the first of the two reasons order matters, and it is the stronger one. Take those same two functions and try to wire them the other way round. Second machine first. The second function's outputs are declared to lie in the set seven, eleven, fifteen.

9:00The first function takes its inputs from the set two, three, four, five. Those are not the same set. Look at the report: three members on one side, four on the other, and all three of the first are missing from the second. Not one of seven, eleven and fifteen is an input the first function will accept. So the reversed composite is not a different function from the one we built. It is not a function at all. There is nothing to compute.

9:33This is worth pausing on because it is a stronger statement than the one people expect. The expectation is that the two orders give different answers. Here one of the two orders does not have any answers to give. And notice that the refusal has nothing to do with the rules. Neither function was consulted. The two declared sets were compared and that settled it. One more guard against a lazy version of this. It is not enough for the two sets to be the same SIZE.

10:08Take a function whose inputs are one, two, three and whose outputs are declared in seven, eleven, fifteen. Three members each side, so the sizes match. Try to run it after our second function. Three members in one declared set, three in the other, and all three missing from the one that matters. Refused. Same size, different sets, no composite. So now the honest case. Two functions where both orders are legal, and we find out whether they are the same.

10:44Both of these take any real number and give back a real number, so every set in sight is the same set and the plug fits either way round. The first sends x to the cosine of x. The second sends x to three times x squared. Wire cosine first. The cosine comes out, and the second machine squares it and triples it. So that composite is three times the square of the cosine of x.

11:15Now wire them the other way. Three x squared comes out first, and the cosine machine takes the cosine of that. So this composite is the cosine of three x squared. Look at those two written side by side. Three times the square of the cosine, against the cosine of three times the square. In the first, the cosine is taken first and then squared. In the second, the squaring happens first and the cosine is taken of the result.

11:49They are built from the same two ingredients and they are visibly not the same expression. But being visibly different is not a proof. To settle it, we need one input at which the two disagree. One. Try zero, because both are easy there. The first composite: the cosine of zero is one, one squared is one, three times one is three. The second composite: three times zero squared is zero, and the cosine of zero is one.

12:24Three against one. They differ. That is the entire proof that the two composites are different functions. One input, two values, done. It is worth being clear about why one input is enough. Two functions are equal when they agree at every input of their common domain. So they FAIL to be equal the moment there is one input where they do not. The negation of a for-all is a there-exists, and a there-exists needs exactly one example.

12:57Which is why inequality of functions is the easy claim and equality is the hard one. To show equality you owe every input. For what it is worth, these two disagree almost everywhere. Take eighty-one inputs an eighth of a unit apart, from minus five to five, and they disagree at all eighty-one. The closest they come to each other anywhere on that grid is about nought point nought eight — nowhere near close enough for any rounding question to arise.

13:32But none of that was needed. Zero alone did it. Now the mistake that runs the other way, which is subtler and much more common. Suppose you had tried an input and the two composites had agreed there. What would you have proved? Nothing at all. Here is the cleanest possible demonstration, back on the four-input example. Our composite sends two to seven, three to seven, four to eleven and five to eleven.

14:04Now here is a rival function with the same declared input set and the same declared output set. It sends two to seven, three to seven, four to SEVEN, and five to eleven. Compare them input by input. Four inputs tried. They agree at two, at three, and at five. Three agreements out of four. And they are different functions, because at the input four one gives eleven and the other gives seven.

14:34Three quarters of the evidence said they were the same, and three quarters of the evidence is worth nothing. So the two claims are not symmetric at all. One disagreement settles inequality forever. Any number of agreements short of all of them settles nothing. If a question asks you to show two functions are unequal, hunt for one input. If it asks you to show they are equal, you are being asked for an argument that covers every input at once.

15:08Let us collect the bookkeeping, because it is the thing that makes the rest safe. Composition involves three sets, not two. The first function's input set. The middle set. And the second function's output set. Two of those three have to coincide: the first function's declared OUTPUT set and the second function's declared INPUT set. That is the whole requirement. When they do, the composite's declared input set is the first set and its declared output set is the third.

15:44Three questions, and you can answer all three before computing a single value. Does the composite exist? Compare two sets. What are its declared sets? Take the outer two. Is the reverse composite even a question? Compare two different sets, and quite often the answer is no. None of those needs the rules at all, which is exactly why they are the first things to check. One last thing, as a signpost.

16:16We have spent the whole video on composites that lose something — a collision picked up, a target left unreached, an order that will not even wire up. But some composites give you back exactly what you put in. Take the function on the counting numbers that sends every odd number to one more than itself and every even number to one less. One goes to two, two goes to one, three to four, four to three.

16:47Compose it with itself. An odd number goes up to the even number above it, and that even number comes straight back down to where it started. Over the first forty inputs, the composite disagrees with leaving them alone at nothing at all. Forty inputs tried, zero disagreements. Here is a second one, built out of two different functions. Send x to four x plus three, and send the results back by taking three away and dividing by four.

17:20Twelve inputs tried going up and then down: no disagreement with leaving them alone. Twelve tried going down and then up: the same. Both orders return everything untouched, which is a very different situation from anything else in this video. A function that has a partner like that is called invertible, and the partner undoes it. That is where this goes next. But notice that even there, composition did the work. The question was never whether two rules look like opposites. It was what happens when you run one into the other and check every input.