Lesson 19: Done it once, done it a thousand times

The title of this lesson is a bit non-standard in comparison to the titles of most of the other lessons, so let me explain it a bit.  We’ve seen in lesson 16, lesson 17, and lesson 18 a few of the  various ways that we can take two sets and form a new, third set using the information of the first two.  A natural question to ask, then, is what we can do if we’re handed three sets.  Or four sets.  In other words, if the enemy hands me three sets, am I able to make a fourth set from the information of the first three?  If the enemy hands me four sets, can I make a fifth?  And so on.

Maybe you already see where the title of this lesson is sort of coming from.  If the enemy hands me a thousand sets, can I make a “thouand and one-th” set?  The answer turns out to be, perhaps unsurprisingly, yes.  What’s a bit more remarkable, however, is that oftentimes in order to build this “thousand and one-th” set, we really only need the machinery that we’ve invented for dealing with two sets.  This means that if I want to “combine” the information of an arbitrary number of sets, or “construct” a new set from an arbitrary number of old sets, I really only need to know how to do so for two sets!

Before I actually describe what’s involved when it comes to sets and the constructions we have so far, let me first comment on how general of a phenomenon this is in mathematics.  Mathematicians spend a lot of time “building new things from old things” (and by “things”, of course, I don’t mean teletubbies or baseballs, but rather mathematical structures).  In order to do this, though, they need to define precisely what it is they mean by “building new things”, in a similar way to how we’ve defined unions and intersections.  But our definition of unions (and intersections) only applies when we have two sets to take the union (or intersection) of.

It turns out (as we’ll see below) that in order to take the union of 3 (or more) sets, we only need to know how to take the union of 2 sets.  And it also turns out (as we’ll see throughout many of the coming lessons) that many* mathematical constructions behave this way—i.e., doing something once (taking a union, for example) is all we need to know how to do in order to do something a thousand (or more) times.  Since this ability to “extend” our constructions to more objects is in no way guaranteed by the definitions of the constructions themselves, we do indeed need to check (or prove) that our constructions extend in this way.  Let us therefore get on with doing this checking with what we’ve defined so far.

Suppose we have three sets A, B, and C, and suppose we want to do something to them analogous to “taking the union of all three”.  Notice that I’m forced to use scare quotes because we have yet to discuss what “taking the union of three sets” actually means.  We’ve only defined what it means to take the union of two sets, so one might be tempted to make a new definition for how to take the union of three sets.  But if we did this, we’d quickly run into trouble, because we surely want to be able to take the union of 4 sets, and 5 sets, and 6 sets, and we surely don’t want to have to come up with an infinite number of definitions to account for all of these constructions.  The old and jaded professor might be a little bummed out by these realizations and might consider leaving the academic world and spending his years traveling and hiking instead of figuring out how to get around an infinite number of new definitions.

But the energetic student sees a way out!  Sure, she doesn’t know how to union three sets at once, but she does know how to take the union of two sets to form one set.  Suppose she does this to A and B, thus forming the single set .  She now has two sets left, and C.  Well, she knows how to union two sets!  So she unions these two sets to form (note the parentheses that I’m forced to use to remind ourselves that she union-ed A and B first to form the single set ).  The student looks at the professor and says, “see?! I told you I could do it!”.

But although the professor might be jaded, he’s still sharp, and he points out that the student could have also just as easily constructed  and/or .  I.e., she could have first union-ed A and C, and then union-ed this new set with B, or she could have first union-ed B and C, and then union-ed this new set with A.  All of these are equally good candidates for “the union of three sets A, B, and C”, and so which one is she to use?  Alas, we’ve reached another impasse.  The student goes home bummed out that her fields medal might be farther away than she thought…

But while at home, drowning her disappointment in hot chocolate and Reddit memes, she has an idea.  What if all of those ways of “union-ing” three sets together were somehow the same?  What if it didn’t matter which way of union-ing we chose, because they’d all give us the same final set?  After a couple more links in /r/funny, the student sits back and thinks of the following.

What are the elements in ?  By the definition of a union, these are the elements either in C, or in “A union B”.  But what are the elements in “A union B”?  These are precisely the elements that are either in A or in B.  Thus, the elements in are precisely those elements that are either in C or “either in A or B”.  Similarly, the elements in  are precisely those elements that are either in B or “either in A or C”.  But clearly these are all the same elements, because they’re all “either in A or B or C”!  Checking the last case, , convinces the student that indeed, these three sets are all exactly equal.  It doesn’t matter in which order she unions these three sets, because the final set will always be the same!

Unfortunately (or fortunately) this accomplishment is not warranting of a fields medal, but the student does have a good time explaining it to her professor (who clearly needs to brush up on his set theory).  The student isn’t done, however.  She continues to plow forward, and asks the same questions about intersections:  is it the case that ?  Again, the answer is yes.  Let us see why.   is the set of elements that are in C and in “A intersect B”, and “A intersect B” is the set of elements that are in A and B.  Thus,  is the set of elements that are in A and B and C!  The exact same logic (of breaking these sets down “one intersection at a time”) applied to the other two sets shows that all of these sets are indeed the set of elements in A and B and C, and so they’re all equal!

This means that we can now talk about the union (or intersection) of an arbitrary number of sets without having to introduce new definitions for all of them.  All we do is “union them up one at a time”, and we know that this is a sufficient prescription because the order in which we “union them up” is irrelevant—all different possibilites are equivalent!

Thus, in order to take the union of a thousand sets, call them , we simply start union-ing them up one at a time, in any order, and we know that whatever order we pick the result will be the same (because at each step we know that the order is irrelevant because at each step we’re simply union-ing a third set onto two sets that were union-ed, which we know is order-independent).  Therefore we can unambiguously write the expression (which stands for the single set formed as the union of all thousand of these sets), without having to worry about where we put the parentheses because we know that the order that we “union them up” doesn’t matter.

Let me end this lesson with two quick comments.  First, everything that we established in the above paragraph applies for a “thousand-fold” intersection as well, simply because we’ve already established the “three-fold” intersection property and because we’ve shown that all we need to show is the three-fold property (the rest follows from the three-fold case).  Secondly, this is a good time for me to introduce some more notation.  This is a great bit of notation because it is a perfect example of something that might have been scary had we not known what’s really going on, but now that we do know what’s going on it shouldn’t be scary at all.

Suppose we’re given a thousand sets, labeled as those above: .  It’d be nice to have a notation for the “thousand-fold union” of these sets without always having to write the tedious expression  .  This is not ideal notation for a couple of reasons.  First, it’s not ideal because it’s ambiguous: where do I put the “…”?  After the third set? After the fifth set?  It clearly doesn’t matter as long as we know what we’re talking about, but it’s still annoying (ambiguity is the mathematician’s kryptonite).  It’s also not ideal simply because it’s long.  So here’s a better way.  Let’s let this set be denoted by

.

The union sign is still in there, and the notation is simply telling us to union all of the sets labeled by , for some “i”, where “i” runs from 1 to 1,000.  That’s not so bad at all.  We’ve gotten rid of any ambiguities, and now all we need to write is  instead of  for the same abstract idea!

Similarly, we could write

for the “thousand-fold” intersection of these sets.

It should also be mentioned that in this new notation, the “i” is what’s called a “dummy variable” because it doesn’t matter at all which letter or symbol we use in its place.  The “i” plays absolutely no role here.  I could just as easily (and truthfully) have written  or  or  for the exact same set.  Note also that we could let the numbers “1” and “1,000” be anything they want, but that it just so happens that in our case our sets were labeled from 1 to 1,000, and so these were the numbers we had to go with (if the sets were labeled differently, we’d have different numbers in our expressions).

That’ll do it for this lesson, and I’ll pass on putting in any exercises because a) I can’t think of any good ones for these ideas and b) this lesson is already pretty long.  In the next lesson we’ll be able to use a lot of what we’ve learned to look at ideas from basic high school or middle school math in a whole new light.  This new light will be a much more abstract one, and I think it is precisely this abstraction that helps to clear up what we’ve “really” been doing all along in middle and high school math!  I’ll try to make these parallels to more familiar math as much as possible, so as to point out that the kind of math that we’re learning now has always been and will always be “behind the scenes” of what is more “conventional”.  The next lesson is just the start!

Next Lesson

Previous Lesson

Back to Interlude

*But not all.  We don’t discuss Cartesian products or disjoint unions here, and that’s because these constructions are a bit more subtle (primarily because we’ve had to change the elements themselves to discuss them).  We will, however, address these issues in due time.