## Back to Tutorial

*similar to problem 5 from section 1.1 of your text

1.

Assume the set A = {1, 4, 7, 8} and B = {7} (note that B ⊂ A). Find a subset C of A such that B ∪ C = A and B ∩ C = Ø. Let D = {7, 8}. Note that D ⊂ A. Find a subset E of A such that D ∪ E = A and D ∩ E = Ø. How many distinct pairs of disjoint non-empty subsets of A are there, the union of which is all of A?

Hide Response

Show Response

To someone new to finite math, this problem likely sounds pretty confusing. But if we can get a good grasp on all this new vocabulary, we'll see it actually isn't too complicated.

A subset C of A such that B ∪ C = A and B ∩ C = Ø simply means that the elements in B and C, when combined, must result in all the elements of A. That the intersection of B and C is Ø means they have no shared elements in common. These two things tell us that C must then be {1, 4, 8} because it has no elements in common with B but once added to B, equals A.

Repeating that process for a subset E of A, such that D ∪ E = A and D ∩ E = Ø, we know E must be {1, 4}.

Finally, the last question asks us how many distinct pairs of disjoint (meaning having no intersection -- or no elements in common with each other) non-empty subsets there are of A. First, let me point out that it's no accident this question is here. The first two exercises, as is common in this class, have trained you to think about how to answer this one. In other words, the pair of subsets B and C, as well as the pair D and E, represent two of these disjoint, non-empty pairs. How many others are there?

Unfortunately, the only way forward is to simply name them. Start with the pairs of subsets in which the first set contains only a single element from A, such as B = {7}, and the second set contains the remaining three, such as C = {1, 4, 8}. This could be true for when B equals each of the other three elements in A, as well, giving us 4 pairs thus far. Keep in mind, though, C could also equal {7}, while B = {1, 4, 8}, which means each of those 4 pairs we just discovered has a duplicate in which the names of the two subsets are reversed. So, actually, we're up to 8 pairs.

Next, we need to know the pairs in which each subset contains two of the elements from A, such as D = {7, 8} and E = {1, 4}. Here are the possible two-digit subsets from set A: {1, 4}, {1, 7}, {1, 8}, {4, 7}, {4, 8}, and {7, 8}. Note that the subset {4, 1} is no different from {1, 4} because the order of the elements doesn't matter -- it's the same set. Therefore, each of those six subsets would be paired with another subset containing the remaining two elements from A. The subset F = {1, 4}, for example, would be paired with the subset G = {7, 8}. Now we can see that each of those six subsets is just three pairs: {1, 4} and {7, 8}; {1, 7} and {4, 8}; {1, 8} and {4, 7}. If you named each subset, you could duplicate it and swap the names, so those 3 pairs then result in 6 pairs.

And when you add those to the 8 pairs we found earlier, we get 14 distinct, disjoint, non-empty sets.