Discrete! #27: Discrete Mathematics and Its Applications 2.2

2.2: Set Operations

Things are getting more interesting! Now we introduce some operations called union and intersection, denoted as ∪ and ∩ respectively. These are very clever symbols, since they look a lot like our OR and AND symbols, ∨ and ∧. As it turns out, these concepts are very similar, though applied to different things.

A∪B = {x | x∈A∨x∈B}

That is, “The set, A-union-B is the set containing x, such that x must be a member of A or a member of B or a member of both.”

In other words, this new set we’re making contains both the elements of A and the elements of B. Or, in human-speak: A union is when you combine two sets into one new set.

You hopefully can see the sense in which it’s analogous to OR. In OR, you say “One of these two propositions, or both of them, is true.” In a union, you say “Each element is a member of one of these sets or both of them.”

A∩B = {x | x∈A∧x∈B}

That is, “The set, A-intersection-B is the set containing x, such that x must be a member of both A and B.”

In other words, this new set we’re making contains only those elements which were contained in both A and B. Or, in human-speak: An intersection is when you make a new set out of the shared elements of A and B.

The book provides some nice Venn Diagram versions of these concepts that I won’t reproduce here.

We also get a new type of notation, which is bar notation. I don’t love bar notation, because it’s used in lots of different areas to mean lots of different things. BUT SCREW IT. LET’S DO IT.

Putting a bar, aka a little line, above a set means you’re talking about the set’s compliment. What does that mean? Well, imagine you’re talking about the universal set of elements for something. For example, say you’re talking about the universal set of Star Wars films. We refer to that set as U, for universal.

Now, say you made a set, A, which contained Episodes 4, 5, and 6. The complement of

So, A={Episode 4, Episode 5, Episode 6}

Now, you can talk about the compliment of A, written as Ā. Ā contains the elements of the universal set, which A alone does not contain.

Ā = {Episode 1, Episode 2, Episode 3, those Ewok movies}

Again, there’s an analogy. The bar is similar to NOT, given by ¬. A is a set of elements in U. Ā is a set of elements in U, which are not in A.

Here are some other ways to think about it:

A-bar-bar = A

U – A = Ā

U – Ā = A

Make sense?

This leads us to this sections biiiiig bunch of laws. Let’s go through:

Set Identities:

 

Identity Laws

A∪∅ = A

A∩U = A

Pretty straightforward. The combination of A and nothing is still A. The set that is the intersection of A and everything that could be in A is the same is just plain old A.

Domination Laws

A∪U = U

A∩∅ = ∅

Again, pretty sensible. The combination of A and everything else is the same as just everything else. And, the crossover between elements of A and no elements is… (drum roll…) no elements.

Idempotent Laws

A∪A=A

A∩A=A

Again, pretty clear. The combination of A and A is still just A. The intersection of A and itself is… itself.

Complementation Law

A-bar-bar = A

(I don’t know how to write two bars above A)

But, anyway, pretty clear. The two bars are just a double negative.

Commutative Laws

A∪B=A∪B

A∩B=B∩A

Since order doesn’t matter in sets, they’re nice and commutative.

Associative Laws

A∪(B∪C)=(A∪B)∪C

A∩(B∩C)=(A∩B)∩C

That is, if you have all the same operators you can flip around the parentheses however you want. One way to think of this is as follows: If you draw the Venn Diagram of the sets and how they relate, whether it’s their intersections or unions, it doesn’t matter which circles you draw first. The union or intersection will be the same.

Distributive Laws

A∩(B∪C)=(A∩B)∪(A∩C)

A∪(B∩C)=(A∪B)∩(A∪C)

Okay, this one might seem a little trickier, but you should remember the basic notion from our earlier stuff. It’s probably easiest of you draw the Venn Diagram on these.

For the first one, you can think of it like this: You make a new set called B-Union-C then see where it intersects with A. That’s no different then just seeing where A intersects with B and where A intersects with C, then combining them.

For the second, it’s just flipped. On the left side, you’re finding where B and C intersect and combining it with A. Equivalently, on the right, you’re combining A with B, then A with C, then seeing where these two new groups touch.

De Morgan’s Laws

I don’t know how to write these out properly, so I’ll use language:

The complement of the union of A and B is equal to the intersection of A-bar and B-bar.

The complement of the intersection of A and B is equal to the union of A-bar and B-bar.

These should remind you of the old de Morgan’s laws for our basic operations. To illustrate, let’s take the first case and do an example.

U is the set of all major star wars movies, so U = {1,2,3,4,5,6}

A is the set of good star wars movies, so A = {4,5,6}

B is the set of odd-numbered star wars movies, so B = {1,3,5}

A∪B = {1,3,4,5,6}

The complement of A∪B is {2}

The complement of A is {1,2,3}

The complement of B is {2,4,6}

The intersection of those complements is {2}.

So, the complement of the union is the same as the intersection of the complements. Not so bad, right?

Absorption Laws

A∪(A∩B)=A

A∩(A∪B)=A

The first one says “If you take all the places A and B intersect and combine them with A, you’ve just got A.” That is, the intersection of A and B is necessarily a subset of A. A + a subset of A = A.

The second says “If you take the union of A and B and then find where that intersects with A, you’ve just got A.” That is, A-Union-B probably makes a new larger set, but finding its intersection with A just reduces it back to A.

Complement Laws

A∪Ā=U

A∩Ā=∅

Simple enough – the part of U that is A plus the part of U that is not A equals A. And, the intersection of something and its complement is, obviously, nothing.

 

BAM! I think most of these are pretty straightforward. But, the real test of fluency will be when we start working problems.

 

Generalized Unions and Intersections

You can use notation to create complicated sets.

This should look familiar if you’ve ever done summations or sequences. Basically, it means that you make the union of all the A sets with the subheading “1” to the some other subheading, which we placehold right now with n. The same can be done for intersections.

It’s not terribly tricky to understand, but the bigger challenge will be when we start working problems.

Computer Representations of Sets

This section basically shows a way to use bits to represent sets, assuming U={1,2,3,4,5,6,7,8,9,10}

The way you represent is by making a string of 0s and 1s, in which the position in the string corresponds to a certain number, and 1 means the corresponding number is a member of the set.

So, for example, multiples of 3 would be

0010 0100 10

Multiples of 4 would be

0001 0001 00

Multiples of 5 would be

0000 1000 01

Odds would be

1010 1010 10

The gaps are just to make mental evaluation easier for your puny human brain.

OKAY, that wasn’t so painful. Next time, we’ll see how we do on problems.

Next stop: Interesting Problems in 2.2