Discrete Math 2: More on Sets

Last time I talked about what a set is and some stuff that can be done with sets. First we can look at the union of sets which is the set containing as elements, all of the elements from the sets being unioned. Then we can also look at the intersection of sets, which is the set of all overlapping elements of whatever sets we are looking at.

These are operations between sets, like multiplication and addition being operations between numbers. Now I look at one more type of operation called complement.

The complement of a set A, is all of the elements that are not in A. Of course this only makes sense if A is inside of something larger so that you can talk about things that aren’t in A.

It is denoted either $A^{C}$ or $A^{\prime}$ but I will be using $A^{C}$.
For example, consider the sets
$A = \{1,2,3,4\}$ and $B = \{1,3,5,7,9\}$
within the set $U = \{1,2,3,4,5,6,7,8,9,10\}$
Then
$A^{C} = \{5,6,7,8,9,10\}$ and
$B^{C} = \{2,4,6,8,10\}$

We usually U to denote the universal set in the context of whatever problem is being discussed. Given two sets A and B within the universal set U, we can show $A^{C}$

And we can show $B^{C}$ with

What about if we want to write stuff in A, but not in B? We would say this is the set A not B, or write
$A \setminus B$. To get this set we are actually taking everything in A, and intersecting it with the stuff that is not in B, otherwise known as $B^{C}$.

So $A \cap B^{C}$ is:

Looking at these parts together and also throwing in the intersection can lead us to a nice equality.
$A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A\cap B)$ or
$A \cup B = (A \cap B^{C}) \cup (B \cap A^{C}) \cup (A\cap B)$
with pictures;

This is important because it allows us to break up sets into pieces.

Now that we have the three main operations used for sets we can see how they fit together and make some useful rules.

First we have the easiest one, associativity. This just means that when using the same operation a bunch of times, the order doesn’t matter. Just like when you multiply a bunch of numbers, you can do it in any order. More formally we would say for sets A, B, and C, that:

$(A \cap B )\cap C = A \cap (B \cap C)$
$(A \cup B )\cup C = A \cup B \cup C)$

This makes great sense if you draw a picture with three sets and look at both sides of each equation. A more formal way to prove that two sets are equal is to show that they contain each other, but I am not going to do that here.

Next we have commutativity. For real numbers with multiplication this means that $a \times b = b \times a$ which is a seemingly obvious thing. For sets we have the same thing

$A \cup B = B \cup A$
$A \cap B = B \cap A$

Next is the distributive property, just like with numbers. This is a way of combining two operations together. Remember the distributive property with numbers looks something like this:
$3(5+2) = 3\times 5 + 3\times 2$
Multiplication distributes over the addition, we combined the two operations in a way that makes sense.

There is a similar idea for sets. The general rule for sets A, B, and C is
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

It looks just like the multiplication and addition distribution with different symbols.

Lastly, we want to throw in the complement operation and see what happens. First as usual, the obvious one:

$(A^{C})^{C} = A$ If you complement a set twice, you just get back to the original set. This is sort of like taking a double negative. Next we want to combine operations again.

This is usually the most difficult to grasp property, but pictures make it easy to see. I can’t seem to draw them very well still so I leave it to you to draw for yourself. Again the formal way would be to show that both sets contain each other, which I may write about next time.

$(A \cup B)^{C} = A^{C} \cap B^{C}$
$(A \cap B)^{C} = A^{C} \cup B^{C}$