2.9: Combining sets

Okay, so we have sets. Now what can we do with them? When you first learn about numbers back before kindergarten, the next thing you learn is how to combine numbers using various operations to produce other numbers. These include \(+, -, \times, \div,\) exponents, roots, etc. Sets, too, have operations that are useful for combining to make other sets. These include:

• Union (\(\cup\)). The union of two sets is a set that includes the elements that either (or both) of them have as members. For instance, if \(A\) = { Dad, Lizzy }, and \(B\) = { Lizzy, T.J., Johnny }, then \(A \cup B\) = { Dad, Lizzy, T.J., Johnny }. Note that an element is in the union if it is in \(A\) or \(B\). For this reason, there is a strong relationship between the union operator of sets and the “or" (\(\vee\)) operator of boolean logic that we’ll see later.

• Intersection (\(\cap\)). The intersection of two sets is a set that includes the elements that both of them have as members. In the above example, \(A \cap B\) = { Lizzy }. There is a strong connection between intersection and the “and" (\(\wedge\)) boolean logic operator.

• (Partial) complement (\(-\)). Looks like subtraction, but significantly different. \(A - B\) contains the elements from A that are not also in B. So you start with \(A\), and then “subtract off" the contents of \(B\), if they occur. In the above example, \(A-B\) = { Dad }. (Note that T.J. and Johnny didn’t really enter in to the calculation.) Unlike \(\cup\) and \(\cap\), \(-\) is not commutative. This means it’s not symmetrical: \(A-B\) doesn’t (normally) give the same answer as \(B-A\). In this example, \(B-A\) is { T.J., Johnny }, whereas if you ever reverse the operands with union or intersection, you’ll always get the same result as before.

• [complement] (Total) complement (\(\overline{X}\)). Same as the partial complement, above, except that the implied first operand is \(\Omega\). In other words, \(A-B\) is “all the things in \(A\) that aren’t in \(B\)," whereas \(\overline{B}\) is “all the things period that aren’t in \(B\)." Of course, “all the things period" means “all the things that we’re currently talking about." The domain of discourse \(\Omega\) is very important here. If we’re talking about the Davies family, we would say that \(\overline{M}\) = { Mom, Lizzy }, because those are all the Davieses who aren’t male. If, on the other hand, \(\Omega\) is “the grand set of absolutely everything," then not only is Mom a member of \(\overline{M}\), but so is the number 12, the French Revolution, and my nightmare last Tuesday about a rabid platypus.

• Cartesian product (\(\times\)). Looks like multiplication, but very different. When you take the Cartesian product of two sets \(A\) and \(B\), you don’t even get the elements from the sets in the result. Instead, you get ordered pairs of elements. These ordered pairs represent each combination of an element from A and an element from B. For instance, suppose \(A\) = { Bob, Dave } and \(B\) = { Jenny, Gabrielle, and Tiffany }. Then:

  \(A \times B\) = { (Bob, Jenny), (Bob, Gabrielle), (Bob, Tiffany),
  (Dave, Jenny), (Dave, Gabrielle), (Dave, Tiffany) }.

  Study that list. The first thing to realize is that it consists of neither guys nor girls, but of ordered pairs. (Clearly, for example, Jenny \(\notin A\times B\).) Every guy appears exactly once with every girl, and the guy is always the first element of the ordered pair. Since we have two guys and three girls, there are six elements in the result, which is an easy way to remember the \(\times\) sign that represents Cartesian product. (Do not, however, make the common mistake of thinking that \(A \times B\) is 6. \(A \times B\) is a set, not a number. The cardinality of the set, of course, is 6, so it’s appropriate to write \(|A \times B| = 6\).)

Laws of combining sets

There are a bunch of handy facts that arise when combining sets using the above operators. The important thing is that these are all easily seen just by thinking about them for a moment. Put another way, these aren’t facts to memorize; they’re facts to look at and see for yourself. They’re just a few natural consequences of the way we’ve defined sets and operations, and there are many others.

• Union and intersection are commutative. As noted above, it’s easy to see that \(A \cup B\) will always give the same result as \(B \cup A\). Same goes for \(\cap\). (Not true for \(-\), though.)

• Union and intersection are associative. “Associative" means that if you have an operator repeated several times, left to right, it doesn’t matter which order you evaluate them in. \((A \cup B) \cup C\) will give the same result as \(A \cup (B \cup C)\). This means we can freely write expressions like “\(X \cup Y \cup Z\)" and no one can accuse us of being ambiguous. This is also true if you have three (or more) intersections in a row. Be careful, though: associativity does not hold if you have unions and intersections mixed together. If I write \(A \cup B \cap C\) it matters very much whether I do the union first or the intersection first. This is just how it works with numbers: \(4 + 3 \times 2\) gives either 10 or 14 depending on the order of operations. In algebra, we learned that \(\times\) has precedence over +, and you’ll always do that one first in the absence of parentheses. We could establish a similar order for set operations, but we won’t: we’ll always make it explicit with parens.

• Union and intersection are distributive. [distributivelaw] You’ll recall from basic algebra that \(a \cdot (b+c) = ab + ac\). Similarly with sets, \[X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z).\] It’s important to work this out for yourself rather than just memorize it as a rule. Why does it work? Well, take a concrete example. Suppose \(X\) is the set of all female students, \(Y\) is the set of all computer science majors, and \(Z\) is the set of all math majors. (Some students, of course, double-major in both.) The left-hand side of the equals sign says “first take all the math and computer science majors and put them in a group. Then, intersect that group with the women to extract only the female students." The result is “women who are either computer science majors or math majors (or both)." Now look at the right-hand side. The first pair of parentheses encloses only female computer science majors. The right pair encloses female math majors. Then we take the union of the two, to get a group which contains only females, and specifically only the females who are computer science majors or math majors (or both). Clearly, the two sides of the equals sign have the same extension.

  The distributive property in basic algebra doesn’t work if you flip the times and plus signs (normally \(a+b\cdot c \neq (a+b)\cdot (a+c)\)), but remarkably it does here: \[X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z).\] Using the same definitions of \(X\), \(Y\), and \(Z\), work out the meaning of this one and convince yourself it’s always true.

• Identity laws. Simplest thing you’ve learned all day: \(X \cup \varnothing = X\) and \(X \cap \Omega = X\). You don’t change \(X\) by adding nothing to it, or taking nothing away from it.

• Domination laws. The flip side of the above is that \(X \cup \Omega = \Omega\) and \(X \cap \varnothing = \varnothing\). If you take \(X\), and then add everything and the kitchen sink to it, you get everything and the kitchen sink. And if you restrict \(X\) to having nothing, it of course has nothing.

• Complement laws. \(X \cup \overline{X} = \Omega\). This is another way of saying “everything (in the domain of discourse) is either in, or not in, a set." So if I take \(X\), and then I take everything not in \(X\), and smoosh the two together, I get everything. In a similar vein, \(X \cap \overline{X} = \varnothing\), because there can’t be any element that’s both in \(X\) and not in \(X\): that would be a contradiction. Interestingly, the first of these two laws has become controversial in modern philosophy. It’s called “the law of the excluded middle," and is explicitly repudiated in many modern logic systems.

• De Morgan’s laws. [demorganslaws] Now these are worth memorizing, if only because (1) they’re incredibly important, and (2) they may not slip right off the tongue the way the previous properties do. The first one can be stated this way:

  \[\overline{X \cup Y} = \overline{X} \cap \overline{Y}.\]

  Again, it’s best understood with a specific example. Let’s say you’re renting a house, and want to make sure you don’t have any surly characters under the roof. Let \(X\) be the set of all known thieves. Let \(Y\) be the set of all known murderers. Now as a landlord, you don’t want any thieves or murderers renting your property. So who are you willing to rent to? Answer: if \(\Omega\) is the set of all people, you are willing to rent to \(\overline{X \cup Y}\).

  Why that? Because if you take \(X \cup Y\), that gives you all the undesirables: people who are either murderers or thieves (or both). You don’t want to rent to any of them. In fact, you want to rent to the complement of that set; namely, “anybody else." Putting an overbar on that expression gives you all the non-thieves and non-murderers.

  Very well. But now look at the right hand side of the equation. \(\overline{X}\) gives you the non-thieves. \(\overline{Y}\) gives you the non-murderers. Now in order to get acceptable people, you want to rent only to someone who’s in both groups. Put another way, they have to be both a non-thief and a non-murderer in order for you to rent to them. Therefore, they must be in the intersection of the non-thief group and the non-murderer group. Therefore, the two sides of this equation are the same.

  The other form of De Morgan’s law is stated by flipping the intersections and unions:

  \[\overline{X \cap Y} = \overline{X} \cup \overline{Y}.\]

  Work this one out for yourself using a similar example, and convince yourself it’s always true.

  Augustus De Morgan, by the way, was a brilliant 19\(^\text{th}\) century mathematician with a wide range of interests. His name will come up again when we study logic and mathematical induction.