Non-Disjoint Outcomes

In we explored the sum principle as a way of combining two (or more) sets of disjoint outcomes. What happens if the outcomes are not disjoint?

Something different needs to be done. For example, when counting the number of playing cards that are either face cards or red cards, we cannot apply the sum principle to claim there are \(12 + 26 = 38\) cards. The problem is exactly that six cards are both face cards and red cards. There are a few different ways we can handle this that we will explore in this section.

To understand how to deal with combining sets of outcomes that are not disjoint, it will be helpful to use some notation from set theory, which we will briefly review here.

Let \(A\) be the set of outcomes for the first event and \(B\) be the set of outcomes for the second event. When we ask for the number of ways either event can happen, the new set of outcomes consists of all outcomes that are in \(A\), or \(B\), or both. This is nothing more than the union of the set \(A\) and \(B\), written \(A \cup B\).

The sum principle only applies when no outcome belongs to both events. The elements that are common to sets \(A\) and \(B\) are the sets in their intersection, written \(A \cap B\). The intersection of two sets is itself a set. If sets \(A\) and \(B\) are disjoint, then there are no elements in the intersection, so the intersection is the empty set, written \(\emptyset\).

We are counting the number of outcomes, so what we are really interested in is the size (or cardinality) of the sets. We write the size of a set \(X\) as \(\card{X}\).

With this notation in hand, we can restate the sum principle as follows.

Now consider what happens to the sum principle when the sets are NOT disjoint. Suppose we want to find \(\card{A \cup B}\) and know that \(\card{A} = 10\) and \(\card{B} = 8\). If we knew that the sets were disjoint, then \(\card{A \cup B}\) would be 18. But if we don't have that the sets are disjoint, we need more information We must know how many of the 8 elements in \(B\) are also elements of \(A\). Suppose we also know that \(\card{A \cap B} = 6\). Now we can say exactly how many elements are in \(A\), and, of those, how many are in \(B\) and how many are not (6 of the 10 elements are in \(B\), so 4 are in \(A\) but not in \(B\)). We could fill in a Venn diagram as follows:

This says there are 6 elements in \(A \cap B\), 4 elements in \(A\) but not \(B\) (which we can write as \(\card{A \setminus B} = 4\)), and 2 elements in \(B\) but not \(A\) (written \(\card{B \setminus A} = 2\)). Now these three sets are disjoint, so we can use the sum principle to find the number of elements in \(A \cup B\). It is \(6 + 4 + 2 = 12\).

We can do something similar with three sets.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

It would be nice to write an algebraic formula that captures what we have done in the previous examples. Even better would be for this algebraic formula to be a generalization of the case where the sets are disjoint.

Consider again the example where \(\card{A} = 10\), \(\card{B} = 8\) and \(\card{A \cap B} = 6\). We said that \(\card{A \cup B} = 12\), found by adding \(4 + 6 + 2\).

If \(A\) and \(B\) had been disjoint, then \(\card{A \cup B}\) would have been \(\card{A} + \card{B} = 10 + 8 = 18\). We see that is off by exactly 6, which just so happens to be \(\card{A \cap B}\). So perhaps we guess, \[\card{A \cup B} = \card{A} + \card{B} - \card{A \cap B}\]. This makes sense! When we add the number of elements in \(A\) to the number of elements in \(B\), we have counted the six elements that belong to both sets exactly twice. So if we subtract them out, we have counted them exactly once.

In other words, we have:

For three sets, we can also count the elements in the union by carefully removing elements we have counted multiple times. Since there are more ways for the sets to overlap, the formula is more complicated.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Everything we have considered so far in this section has been about how the sum principle applies when the sets of outcomes are not disjoint. Do we need to be similarly worried about overlaps when applying the product principle?

Not really.

One use of the product principle is to compute probabilities, and in that context, we do make a distinction between events being independent or dependent. We will explore this more in . Essentially, to find the probability of two events occuring, we can multiply their respective probabilities if and only if the two events are independent: if the outcome of one event does not affect the outcome of the other.

While finding probability is closely related to counting outcomes, the product principle itself does not require that sets of outcomes be disjoint or make a distinction between dependent or independent events. What does matter is that the number of outcomes for the second event does not change based on which outcome was the result of the first event.

A distinction we do often make when applying the product principle is whether the outcomes of events can be repeated. Consider the following example.

We will explore problems such as the previous example in much more depth next in . Before that though, here is a final example of where the product principle does NOT easily work.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.