Lesson 18: More Constructions Pt. 2

We’re now going to study one last important way to combine two sets to form a new set.  In lesson 16 we saw two such ways to combine sets, namely the union and the intersection.  These two constructions involved taking two sets and forming a set whose elements are in either of the original sets (the union), and another set whose elements are in both of the original sets (the intersection).  We then saw a new and significantly different way of forming a new set from two old ones in lesson 17, where we studied the Cartesian product.  In the Cartesian product construction, we had to create new elements using the elements from the two original sets that we started with.  We wrote these elements down as (a,b) where a\in A and b\in B, and we viewed these elements as being either simply “pairs of elements”, or as “ways of picking exactly one element from one set and one element from the other”.

We’re now going to study a fourth way of creating a new set from two old ones, and it is going to be most similar to the union that we’ve studied before.  In fact, it will be so similar that we even keep the word “union” in the name of the construction: the disjoint union.  Now, despite the fact that the disjoint union (which I have yet to define) is very similar to the union, it is of course not exactly the same.  The ways in which it is different might seem trivial, but it will actually be very important for us much farther into the future when we study categories (and by “much further”, I mean “much further”).  Let us first recall exactly what it is that the union did for us.

When we took the union of, say, two sets A and B, we formed a set A\cup B by simply “joining these sets together”, meaning we just considered both of their elements “at the same time”.  We didn’t change the elements themselves, we just formed a set by including all of the elements in A and all of the elements in B.  But since we didn’t change the elements, any repeats are simply considered as one element.  For example, the union of \{1, 2, 3\} and \{4, 5, 6\} is simply \{1, 2, 3, 4, 5, 6\}, and the union of \{1, 2, 3\} and \{1, 2, 4\} is \{1, 2, 3, 4\}.  In particular, in the second example the elements “1” and “2” are in both sets, and they only make one appearance in the union because sets do not distinguish identical elements.  One simple corollary to this is that the union of any set with itself is simply itself again.  This is perhaps most easily seen by example, so consider the union of \{1, 2, 3\} and \{1, 2, 3\}.  Well, the set whose elements are in either of these two sets is simply \{1, 2, 3\} again!

This sets us up nicely to make the distinction between a union and a disjoint union.  In short, the disjoint union of two sets is a union that “remembers” which set each element came from.  In some sense, we “label” our elements before union-ing them, so that elements that appear in both sets that we’re “disjoint union-ing” are still distinguished in the finished product.  For example, let A=\{1\} and B=\{1\}.  Clearly A=B, but that’s fine.  Let us now label these elements differently.  Namely, let us label the “1” that comes from A “1_A”, and let us label the “1” that comes from B “1_B”.  Remember, this is just a labeling—it is just a new notation for the abstract idea of “1” that we had originally (i.e., the abstract idea is not changing, just the notation, which is fine).  Then the disjoint union of A and B is the set whose elements are \{1_A, 1_B\}.  We can literally view this as having two different “copies” of the element “1”, in such a way that we can “remember” which set each “1” came from.

At this point in time you might be asking why we’d ever be interested in doing this (you also might not be, which is totally fine too).  There are two answers (that I can think of).  One of the answers is very formal, and the other is a bit more practical.  The formal answer is that this construction actually has some relevance to category theory, which will be studied in future lessons (I call this a formal answer because it is not very satisfying since it only relates one slightly opaque idea to another (currently) opaque idea).  A more practical answer is the following.  The disjoint union actually allows us to deal with sets in a much more flexible way than their original definition allows.  Namely, we have found a logical way around the requirement that sets don’t distinguish identical elements (without, of course, going against any of the logic that we’ve already established).  For example, we would typically have that \{1, 1, 2, 3\}=\{1, 2, 3\} since sets don’t “see” their duplicate elements.  But, from the example from a little while ago, we can construct a set using disjoint unions that might look something like \{1_A, 1_B, 2, 3\}, and this would not equal \{1, 2, 3\} because we are now “remembering” where the duplicate 1’s come from.

Having now seen a little motivation for why this definition is useful, let us finally make the formal definition:

Definition 18.1: Let A and B be sets.  The disjoint union of A and B is the set, often denoted by A\sqcup B, of elements of the form (a, A) or (b, B) where a\in A and b\in B.  We thus have, in symbols, A\sqcup B=\{(a,A)|a\in A\}\cup \{(b,B)|b\in B\}.//

There are a couple of things to note here, especially with that explosion of whacky notation in the last line.  First off, just as in the case of the Cartesian product, we’re changing the elements themselves, and we’re changing them by adding the “label” of A or B (according to which set the element comes from), just so that we can “keep track” of where the various elements come from.  This should not be too scary, because we changed our elements in a very similar way for the Cartesian product, only now our “second slot” is always either “A” or “B”.  Lastly, the regular union appears in the last line, and this is again not surprising.  All we’re doing is going through all of the elements in A and adding the label “A” to them (by putting “A” in the second slot), and then we’re doing the same for all of the elements in B, and then we’re union-ing these two sets of new elements.  By doing this, we ensure that after taking the union of the two new “labeled” sets, we’ll still “remember” where the original elements came from, regardless of whether or not some of the elements in A were the same as some of those in B.

One way to check your understanding of this construction is to note that if A has N elements and B has M elements, then A\sqcup B has N+M elements.  This is simply because we don’t “lose” any elements when taking the union because they’re all labeled differently, and we’re simply taking a union of two sets whose elements have no duplicates.  Remember, we ensured that there’d be no duplicates by labeling the elements from the different sets differently.

There is another subtlety about this construction that should be addressed.  That is, what happens if we want to take the disjoint union of a set with itself?  In particular, we’ve seen that we are able to construct the union, intersection, and Cartesian product of a set A with itself, so now we should ask if and how we can form the disjoint union of A with itself.  As we’ve seen, the disjoint union relies on there being some kind of “labeling system” that allows us to “remember” where all of the elements “come from”.  When the sets were A and B this was easy because we could just label the elements with “A” and “B”, respectively.

But what if you want to construct the disjoint union of A with itself?  Well, technically speaking, we can’t quite do this just yet.  For if we have two “copies” of A and we label all of the elements as (a,A), then we still have no way of distinguishing which “copy” of A the elements come from.  What is missing is a labeling system that distinguishes which copy of A the elements are coming from.  Accordingly, we simply add in a “labeling set” to distinguish the different copies of A.

For example, if A=\{a, b, c\}, then we can simply rename the set and form two copies of it: A_1=\{a, b, c\} and A_2=\{a, b, c\}.  Then we can write the elements in the disjoint union of A with itself as, for example, (a, A_1) \mathrm{\ and\ } (b, A_2).  In other words, we’re simply forcing ourselves to remember which set these elements come from by introducing this new labeling of the sets.

In the above example, our “labeling set” was just \{1, 2\}, but they could have been anything.  If our “labeling set” were \{\mathrm{DONKEY},\mathrm{\ HORSE}\}, then we’d simply write A_{\mathrm{DONKEY}} and A_{\mathrm{HORSE}}.

The moral of this story is that we are indeed able to take the disjoint union of sets with themselves, but we have to get a little creative.  Namely, we have to change what we call the sets themselves so that we have a distinctive way of labeling the elements in the disjoint union.  If this seems unnatural, try to convince yourself that it’s not.  After all, we’ve already had to change what we call our elements when we form Cartesian products and disjoint unions, so why not allow ourselves to change what we call our sets?  Moreover, all of this “changing what we call stuff” is just notation, and we’ve seen time and time again that notation isn’t what matters, but rather the ideas.  Thus, once we have the ideas clear, we just need to find a good notation to reflect those ideas, and it just so happens that the idea of taking the disjoint union of a set with itself requires a little more creativity in its notation.

This ends our investigation of constructing new sets from old ones.  But don’t think that the union, intersection, Cartesian product, and disjoint union are the only possibilities! I’m only moving on because I want to get on to different things, but there are tons of different ways to bring sets together to form new ones.  In fact, in the next interlude I encourage you to try to think up some whacky ways to bring sets together.  All you need is a well-defined way of using the information provided by two sets to produce a new set.  This is a good way of getting a sense of how mathematicians often think!  For now, though, here are some exercises on disjoint unions if you want them.

Exercises

1)  Let A=\{1, 2\},\ B=\{2, 3\}, \mathrm{\ and\ } C=\{1, 3\}.  How many elements are in (A\sqcup B)\sqcup C?  How many elements are in (B\sqcup C)\sqcup A?  Are the sets (A\sqcup B)\sqcup C and (B\sqcup C)\sqcup A equal?  (This is a subtle question, so if you’re a bit stumped have no worries, I’ll try to explain fully in the solutions).

2)  Let A and B be as above in Exercise 1).  How many elements are in the set (A\cup B) \sqcup C?  (Recall that this means “the disjoint union of the set ‘A union B’ with the set C”).

Solutions to the Exercises

On to the Interlude

Next Lesson

Previous Lesson

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s