1.5: A.5- An Example

Proof. We want to show that for any sets \(A\), \(B\), and \(C\), \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)

First we unpack the definition of “\(=\)” in the statement of the proposition. Recall that proving sets identical means showing that the sets have the same elements. That is, all elements of \(A \cup (B \cap C)\) are also elements of \((A \cup B) \cap (A \cup C)\), and vice versa. The “vice versa” means that also every element of \((A \cup B) \cap (A \cup C)\) must be an element of \(A \cup (B \cap C)\). So in unpacking the definition, we see that we have to prove a conjunction. Let’s record this:

By definition, \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) iff every element of \(A \cup (B \cap C)\) is also an element of \((A \cup B) \cap (A \cup C)\), and every element of \((A \cup B) \cap (A \cup C)\) is an element of \(A \cup (B \cap C)\).

Since this is a conjunction, we must prove each conjunct separately. Lets start with the first: let’s prove that every element of \(A \cup (B \cap C)\) is also an element of \((A \cup B) \cap (A \cup C)\).

This is a universal claim, and so we consider an arbitrary element of \(A \cup (B \cap C)\) and show that it must also be an element of \((A \cup B) \cap (A \cup C)\). We’ll pick a variable to call this arbitrary element by, say, \(z\). Our proof continues:

First, we prove that every element of \(A \cup (B \cap C)\) is also an element of \((A \cup B) \cap (A \cup C)\). Let \(z \in A \cup (B \cap C)\). We have to show that \(z \in (A \cup B) \cap (A \cup C)\).

Now it is time to unpack the definition of \(\cup\) and \(\cap\). For instance, the definition of \(\cup\) is: \(A \cup B = \Setabs{z}{z \in A \text{ or } z \in B}\). When we apply the definition to “\(A \cup (B \cap C)\),” the role of the “\(B\)” in the definition is now played by “\(B \cap C\),” so \(A \cup (B \cap C) = \Setabs{z}{z \in A \text{ or } z \in B \cap C}\). So our assumption that \(z \in A \cup (B \cap C)\) amounts to: \(z \in \Setabs{z}{z \in A \text{ or } z \in B \cap C}\). And \(z \in \Setabs{z}{\dots z\dots}\) iff …\(z\) …, i.e., in this case, \(z \in A\) or \(z \in B \cap C\).

By the definition of \(\cup\), either \(z \in A\) or \(z \in B \cap C\).

Since this is a disjunction, it will be useful to apply proof by cases. We take the two cases, and show that in each one, the conclusion we’re aiming for (namely, “\(z \in (A \cup B) \cap (A \cup C)\)”) obtains.

Case 1: Suppose that \(z \in A\).

There’s not much more to work from based on our assumptions. So let’s look at what we have to work with in the conclusion. We want to show that \(z \in (A \cup B) \cap (A \cup C)\). Based on the definition of \(\cap\), if we want to show that \(z \in (A \cup B) \cap (A \cup C)\), we have to show that it’s in both \((A \cup B)\) and \((A \cup C)\). But \(z \in A \cup B\) iff \(z \in A\) or \(z \in B\), and we already have (as the assumption of case 1) that \(z \in A\). By the same reasoning—switching \(C\) for \(B\)—\(z \in A \cup C\). This argument went in the reverse direction, so let’s record our reasoning in the direction needed in our proof.

Since \(z \in A\), \(z \in A\) or \(z \in B\), and hence, by definition of \(\cup\), \(z \in A \cup B\). Similarly, \(z \in A \cup C\). But this means that \(z \in (A \cup B) \cap (A \cup C)\), by definition of \(\cap\).

This completes the first case of the proof by cases. Now we want to derive the conclusion in the second case, where \(z \in B \cap C\).

Case 2: Suppose that \(z \in B \cap C\).

Again, we are working with the intersection of two sets. Let’s apply the definition of \(\cap\):

Since \(z \in B \cap C\), \(z\) must be an element of both \(B\) and \(C\), by definition of \(\cap\).

It’s time to look at our conclusion again. We have to show that \(z\) is in both \((A \cup B)\) and \((A \cup C)\). And again, the solution is immediate.

Since \(z \in B\), \(z \in (A \cup B)\). Since \(z \in C\), also \(z \in (A \cup C)\). So, \(z \in (A \cup B) \cap (A \cup C)\).

Here we applied the definitions of \(\cup\) and \(\cap\) again, but since we’ve already recalled those definitions, and already showed that if \(z\) is in one of two sets it is in their union, we don’t have to be as explicit in what we’ve done.

We’ve completed the second case of the proof by cases, so now we can assert our first conclusion.

So, if \(z \in A \cup (B \cap C)\) then \(z \in (A \cup B) \cap (A \cup C)\).

Now we just want to show the other direction, that every element of \((A \cup B) \cap (A \cup C)\) is an element of \(A \cup (B \cap C)\). As before, we prove this universal claim by assuming we have an arbitrary element of the first set and show it must be in the second set. Let’s state what we’re about to do.

Now, assume that \(z \in (A \cup B) \cap (A \cup C)\). We want to show that \(z \in A \cup (B \cap C)\).

We are now working from the hypothesis that \(z \in (A \cup B) \cap (A \cup C)\). It hopefully isn’t too confusing that we’re using the same \(z\) here as in the first part of the proof. When we finished that part, all the assumptions we’ve made there are no longer in effect, so now we can make new assumptions about what \(z\) is. If that is confusing to you, just replace \(z\) with a different variable in what follows.

We know that \(z\) is in both \(A \cup B\) and \(A \cup C\), by definition of \(\cap\). And by the definition of \(\cup\), we can further unpack this to: either \(z \in A\) or \(z \in B\), and also either \(z \in A\) or \(z \in C\). This looks like a proof by cases again—except the “and” makes it confusing. You might think that this amounts to there being three possibilities: \(z\) is either in \(A\), \(B\) or \(C\). But that would be a mistake. We have to be careful, so let’s consider each disjunction in turn.

By definition of \(\cap\), \(z \in A \cup B\) and \(z \in A \cup C\). By definition of \(\cup\), \(z \in A\) or \(z \in B\). We distinguish cases.

Since we’re focusing on the first disjunction, we haven’t gotten our second disjunction (from unpacking \(A \cup C\)) yet. In fact, we don’t need it yet. The first case is \(z \in A\), and an element of a set is also an element of the union of that set with any other. So case 1 is easy:

Case 1: Suppose that \(z \in A\). It follows that \(z \in A \cup (B \cap C)\).

Now for the second case, \(z \in B\). Here we’ll unpack the second \(\cup\) and do another proof-by-cases:

Case 2: Suppose that \(z \in B\). Since \(z \in A \cup C\), either \(z \in A\) or \(z \in C\). We distinguish cases further:

Case 2a: \(z \in A\). Then, again, \(z \in A \cup (B \cap C)\).

Ok, this was a bit weird. We didn’t actually need the assumption that \(z \in B\) for this case, but that’s ok.

Case 2b: \(z \in C\). Then \(z \in B\) and \(z \in C\), so \(z \in B \cap C\), and consequently, \(z \in A \cup (B \cap C)\).

This concludes both proofs-by-cases and so we’re done with the second half.

So, if \(z \in (A \cup B) \cap (A \cup C)\) then \(z \in A \cup (B \cap C)\). ◻