What laws describe how union and intersection combine sets?

"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 ∪ B will always give the same result as B ∪ A . Same goes for ∩ . (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 ∪ B ) ∪ C will give the same result as A ∪ ( B ∪ C ) . This means we can freely write expressions like “ X ∪ Y ∪ 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 ∪ B ∩ 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 × 2 gives either 10 or 14 depending on the order of operations. In algebra, we learned that × 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. You’ll recall from basic algebra that a · ( b + c ) = ab + ac . Similarly with sets, X ∩ ( Y ∪ Z ) = ( X ∩ Y ) ∪ ( X ∩ 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 · c 6 = ( a + b ) · ( a + c ) ), but remarkably it does here: X ∪ ( Y ∩ Z ) = ( X ∪ Y ) ∩ ( X ∪ 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 ∪ ∅ = X and X ∩ Ω = 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 ∪ Ω = Ω and X ∩ ∅ = ∅ . 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 ∪ X = Ω . 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 ∩ X = ∅ , 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."