Why complementing turns each of the two operations into the other

0:00Two sentences about one object and two sets. It is not in either of them. It is outside the first, and outside the second. The first asks one question, about the set you get by putting the two together. The second asks two, one about each set on its own. And yet the verdict is always the same. In a universe of five objects there are thirty-two sets you can make, and one thousand and twenty-four ordered pairs of them.

0:32Ask both sentences of every object of every pair. That is five thousand one hundred and twenty verdicts. They disagree on none of them. That equality has a twin, and the pair is what this video is about. Start small. The universe is one to six. The first set holds two and three. The second holds three, four and five. Four of the six numbers are in at least one of them.

1:02Left-hand side. Put the two sets together: two, three, four, five. Outside that union sit one and six. Right-hand side, and it never mentions the union. Outside the first set: one, four, five, six. Four numbers. Outside the second: one, two, six. Three numbers. What do those two outsides share? One and six. The same answer by a completely different route. One law, checked on one pair of sets. First, kill the wrong answer.

1:38Almost everyone's guess is that complementing a union gives the union of the complements. Leave the operation alone, and complement the two pieces. Outside the first: one, four, five, six. Outside the second: one, two, six. Together that is one, two, four, five and six. Five numbers, where the right answer had two. It wrongly admits three of them: two, four and five. Watch why two gets in. Two is inside the first set, so it is not outside the union.

2:14But it is outside the second, and or only needs one yes. Across all one thousand and twenty-four pairs, the wrong version lands on the right answer thirty-two times. Those thirty-two are precisely the pairs where the two sets are the same set. Not one pair of different sets survives it. So it is wrong on nine hundred and ninety-two. What did that six-object check actually establish? Six objects give sixty-four subsets, so four thousand and ninety-six ordered pairs.

2:51The check settled one. It left four thousand and ninety-five untouched. Run the machine over all of them and both laws do hold, every time. So the check was not wrong. It was narrow. And widening it does not help, because the claim is about every universe, not this one. Six objects, nine, a hundred, endlessly many. You cannot finish an endless job by working faster. You have to stop counting and start arguing.

3:24Here is the argument. Take any one object of the universe. Suppose it is outside the union. The union holds everything in either set, so if the object were in either, it would be in the union. It is not, so it is in neither. In neither means outside the first and outside the second, which is what being in both complements means. That is one direction. Now run the sentence backwards.

3:54Suppose it is in both complements. Then it is outside the first and outside the second, so nothing put it in the union. Both directions, so the two sides hold exactly the same objects. Notice what the argument never asked. Never how many members anything has. Never which universe we were in. It took one object and followed its verdict, and one object is all any set is made of.

4:23That is why this is a proof and the counting was not. The twin law swaps the operations the other way. Outside the overlap becomes outside one or outside the other. Not in both does not mean in neither. It means at least one of the two failed. Possibly only one. Back to the small universe. The two sets share only three. So outside their overlap sit one, two, four, five and six.

4:54Five numbers, but only one and six are in neither set. Two, four and five are each in one of them. They just are not in both. Across every pair in the five-object universe there are two thousand five hundred and sixty cases of an object failing to be in both while sitting comfortably in one. Not-both is genuinely weaker than neither, and this law is what keeps them straight.

5:22The walk is the mirror image. An object outside the overlap failed at least one test, so it is in at least one complement. Reverse the sentence for the other direction. One more thing the walk never asked. It never assumed the two sets share anything. These laws get read as facts about overlapping circles. In the five-object universe, two hundred and forty-three of the ordered pairs share nothing at all.

5:54That is three to the fifth, and here is why. Each object has three choices: the first set, the second, or neither. It cannot be in both, or they would share it. Both laws hold on every one of those two hundred and forty-three. With nothing shared, the overlap is empty, so outside it is the whole universe. And the two outsides together are also the whole universe. The law does not merely survive the empty case. It is boring there, which is what a law should be.

6:30The proofs are done. But they do not answer why the operations had to swap. Why not complement a union and get another union? Look at what complementing does to containment. Suppose the first set sits inside the second. Anything outside the second is outside the first, because it was never in the first to begin with. So the outsides sit the other way round. Complementing turns a containment around.

7:00In the five-object universe, two hundred and forty-three ordered pairs have one set inside the other. Three to the fifth again. Every one comes back reversed, and no pair that was not nested comes back looking nested. There is a second fact, and it is the quieter one. Complementing twice returns the set you started with, for all thirty-two. So complementing is a reversal that can be undone. How much of the law does reversal alone give you?

7:34The first set sits inside the union. So does the second. Complement all three, and both containments turn around. Outside the union sits inside the first outside, and inside the second outside too. Anything inside both of two sets is inside what they share. So outside the union sits inside what the two outsides share. Checked on all one thousand and twenty-four pairs, and it never fails. But look at what we have: one side sitting inside the other.

8:09We wanted them equal, and sitting inside is half of that. Reversal handed us that half for free, and it has nothing more to give. Is that half really all reversal buys? Take a universe of three objects. Eight subsets. Now consider every way of assigning a subset to each of those eight, with one rule: whenever one set sits inside another, the assigned sets sit the other way round.

8:40A search finds eight thousand of them. All eight thousand give you the easy half, so that half really is free. Now, how many give the whole equality? Seven hundred and twenty-nine. Seven thousand two hundred and seventy-one reverse containment perfectly well and still get the law wrong. Reversal is not enough. That is a measurement, not a feeling. Now the second fact: undoing itself. Of the eight thousand, exactly four undo themselves.

9:14All four give the whole law. Reversal plus undoing itself forces the equality. Reversal alone does not. Those four are worth naming. Shuffle the three objects however you like, then complement. Six shuffles, six one-to-one reversals, and four of those shuffles undo themselves. Complement, with nothing shuffled, is one of the four. And a reversal that gets the law wrong gets at least two of the sixty-four pairs wrong. Never just one.

9:49The reversal is not really about the universe. Any set will do as the thing you take away from. Suppose the first set sits inside the second. Take a third set and remove the second from it. Then remove the first instead. Removing the bigger one leaves less. An object that survived losing the second was never in the second, so never in the first, so it survives losing the first too.

10:19The same walk, with a third set standing where the universe stood. There are seven thousand seven hundred and seventy-six ways to choose a nested pair and a third set, and it holds for all of them. The nesting is doing real work, not decorating the sentence. Take any of the seven hundred and eighty-one pairs that are not nested, and some third set breaks it. So complement is just this, with the universe in the third place.

10:51Now the picture, and it comes last on purpose. Two sets cut a universe into four cases. In the first only. In both. In the second only. In neither. Every object is in exactly one of the four. Shade the outside of the union. One case: in neither. Shade what the two outsides share. Also just in neither. Same picture. That is the first law, drawn. Now shade the outside of the overlap. Three cases: first only, second only, neither.

11:27Shade outside one or outside the other. The same three. Same picture again, and that is the second law. The two pictures are not each other. One shaded region against three. Drawings are a good check and a bad proof. They convince you about two circles on a page. The walk convinced you about every universe there is. One more check, on both laws at once. The universe is one to nine.

11:58The first set is even: two, four, six, eight. The second is two, three, five, seven. Their union holds seven numbers, everything from two to eight. So outside the union sit one and nine. Outside the first: one, three, five, seven, nine. Outside the second: one, four, six, eight, nine. What they share: one and nine. First law confirmed. Now the other law on the same pair. The two sets share only the number two.

12:30So outside their overlap is everything but two. Eight numbers. And the two outsides together are also everything but two. And the second law left out exactly one object, the only one both sets held. So where do these two belong? Complement comes with four groups of facts. First: a set and its outside make up the whole universe between them, and share nothing. Second: complementing twice returns the set.

13:02Third: the empty set and the universe are each other's outsides. Fourth: this pair. Outside a union is the shared outside. Outside an overlap is the combined outside. Every one of those was checked on all thirty-two sets of a five-object universe. But the second group is not just sitting on that list. It is the ingredient that made the fourth come out the way it did. Reversal on its own gave one half. Being undoable gave the other.

13:36So the swap was never a convention anyone chose. Not is a reversal, and a reversal you can undo has to carry the smallest set holding both to the largest set inside both. Or becomes and, and and becomes or. It could not have come out any other way.