Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 8.4 Some set-flavoured results

There are quite a few standard results that describe how the set operations defined above interact with each other. We’ll state some of the more important ones as a theorem (or two (or three)). But first, let us summarise what we have learned above.

Remark 8.4.1. A set of results about sets seen earlier.

Let \(A,B\) be sets. Then
  • \((A \subseteq B) \equiv (\forall x\in A, x\in B) \equiv( x\in A \implies x\in B)\text{.}\)
  • \(\displaystyle (A = B) \equiv \left( (A \subseteq B) \land (B \subseteq A) \right) \equiv \left((x \in A) \iff (x \in B) \right)\)
  • \(\displaystyle (x \in A \cap B) \equiv \left( (x\in A) \land (x\in B) \right)\)
  • \(\displaystyle (x \in A \cup B) \equiv \left( (x\in A) \lor (x\in B) \right)\)
  • \(\displaystyle (x \in \bar{A}) \equiv (x \not\in A) \equiv \neg(x \in A)\)
  • \(\displaystyle (x \in A - B) \equiv \left( (x \in A) \land (x \not\in B)\right) \equiv \left( (x \in A) \land \neg(x \in B) \right)\)
Using these we can prove the following theorems
The above are not so hard to understand. You can see that the distributive laws for sets look very much like the distributive laws for additional and multiplication. Laws for set differences are less obvious and we certainly wouldn’t expect you to remember them. However they do make very good exercises! And, as you’ll see in the examples below, a quick sketch of Venn diagrams can help a lot. But a Venn diagram is not a proof  101 .
When we prove the above theorems we’ll make use of some simple little results that follow quite directly from the definitions of our set operations. Rather than explaining those results again and again in each proof (where the reader has to check the reasoning each time), we’ll put them in a separate little result of their own. Since it is a helpful result we’ll call it a lemma.
These are straight forward to prove using the logic we know and the definitions of union and intersection.
We prove each in order.
  • Assume \(x \in A\text{.}\) Then \(x\in A\) or \(x\in B\text{.}\) Hence \(x \in A\cup B\text{.}\)
  • Assume \(x \in A \cap B\text{.}\) Hence \(x \in A\) and \(x\in B\text{.}\) Thus we have that \(x\in A\) as required.
  • The contrapositive of the statement is the definition of intersection, so the statement is true.
  • The contrapositive of the statement is the definition of union, so the statement is true.

Remark 8.4.6. Careful choice of \(B\).

Take a careful look at the first of the statements in the lemma above. Observe that the hypothesis does not mention the set \(B\) that is in the conclusion. This is a useful observation. It means that we can apply the result by choosing \(B\) to be some set we are interested in. That is:
If \(x \in A\) then \(x\) is in the union of \(A\) and any set we choose.
and similarly the second (its contrapositive) says
If \(x\not\in A\) then \(x\) is not in the intersection of \(A\) and any set we choose.
Okay, primed with these results let’s prove one of DeMorgan’s laws

Example 8.4.7.

Let \(A,B\) be sets included in a universal set \(U\text{,}\) then \(\overline{A \cap B} = \bar{A} \cup \bar{B}\text{.}\)
Scratchwork.
First we should draw a Venn diagram describing the sets \(\overline{A\cap B}, \bar{A}\) and \(\bar{B}\text{:}\)
Again, note that though Venn diagrams are useful tools for to understand and explore problems like these, they are not proofs. You should think of them as tools to help your scratch work.
Its an equality so we have to prove that the LHS is a subset of the RHS and vice-versa. Let’s do those in order.
  • Assume \(x\in \overline{A\cap B}\text{.}\)
  • By definition of set complement this means that \(x \not\in (A\cap B)\text{.}\)
  • Now our helpful lemma comes to our aid. It tells that this implies that \(x \notin A\) or \(x\not\in B\text{.}\)
    • If \(x\not\in A\) then \(x \in \bar{A}\text{.}\) As per our helpful lemma, if \(x\) is an element of a particular set, then it is an element of the union of that set and any other set we choose. Hence, if \(x\in \bar{A}\) then \(x\in \bar{A}\cup\bar{B}\text{.}\)
    • Similarly, if \(x\not\in B\) then \(x\in\bar{B}\text{,}\) and so \(x \in \bar{B}\cup\bar{A}\text{.}\)
  • In either case \(x\in\bar{A}\cup\bar{B}\) as required.
And the other inclusion:
  • Assume \(x\in\bar{A} \cup \bar{B}\text{.}\) Hence \(x\in\bar{A}\) or \(x\in\bar{B}\text{.}\)
    • If \(x\in\bar{A}\) then \(x\not\in A\text{.}\) As above, our helpful lemma comes to our aid. If we know that \(x\) is not an element of a particular set, then it is not in the intersection of that set and any other set we choose. Hence, if \(x \not\in A\) then \(x\not\in A\cap B\text{.}\)
    • If \(x\in\bar{B}\) then \(x\not\in B\text{,}\) and by a similar argument, \(x\not\in A\cap B\text{.}\)
  • In either case \(x\not\in A\cap B\text{,}\) so \(x\in\overline{A\cap B}\) as required.
Now we can write this as a proper proof.
Solution.
We first prove that \(\overline{A\cap B} \subset \bar{A}\cup\bar{B}\) and then the reverse inclusion.
  • Let \(x \in \overline{A\cap B}\text{,}\) and hence \(x\not\in (A \cap B)\text{.}\) This implies that \(x\not\in A\) or \(x\not\in B\text{.}\) If \(x \not\in A\) then \(x \in \bar{A}\text{,}\) and so \(x \in\bar{A} \cup \bar{B}\text{.}\) Similarly, if \(x \not\in B\) then \(x \in \bar{B}\text{,}\) and so \(x \in\bar{B} \cup \bar{A}\text{.}\) In either case, \(x\in \bar{A} \cup \bar{B}\) as required.
  • Now assume that \(x\in \bar{A} \cup \bar{B}\text{,}\) so \(x\in \bar{A}\) or \(x \in \bar{B}\text{.}\) If \(x \in \bar{A}\) then \(x\not\in A\text{,}\) and so \(x\not\in A \cap B\text{.}\) Similarly if \(x \in \bar{B}\) then \(x\not\in B\text{,}\) and so \(x\not\in B \cap A\text{.}\) In either case \(x\not\in A\cap B\text{,}\) and so \(x\in \overline{A\cap B}\text{.}\)
Since we have shown both inclusions, \(\overline{A\cap B} = \bar{A}\cup\bar{B}\)
What about a distributive law or two?

Example 8.4.8.

Let \(A,B,C\) be non-empty sets, then \(A \times (B\cup C) = (A\times B) \cup (A\times C)\text{.}\)
Notice that this result still holds when the sets are allowed to be empty, but the proof of the result is a little messier and involves more cases.
Scratchwork.
Unfortunately it isn’t so easy to draw a useful picture here 102 , but thankfully this isn’t too hard to prove. It is a set-equality, so we need to prove the LHS is a subset of the RHS and vice-versa.
  • Let \(p \in A \times (B\cup C)\text{.}\) Notice that since \(A,B,C\) are non-empty, we know that \(p\) exists. Since the LHS is the cartesian product of two sets, this element \(p\) is really an ordered pair of elements. It is probably a bit easier to follow what is going to happen if we make this clear from the start. With this in mind, let us restart things.
  • Let \((x,y) \in A \times (B \cup C) \text{.}\)
  • This means that \(x\in A\) and \(y \in B\cup C\text{.}\)
  • Hence \(y \in B\) or \(y \in C\text{.}\)
    • Let \(y \in B\text{,}\) then since \(x \in A\text{,}\) we know that \((x,y) \in A \times B\text{.}\) Thus \((x,y) \in (A\times B) \cup \text{(any set we choose)}\text{,}\) and so \((x,y) \in (A\times B) \cup (A \times C)\text{.}\)
    • Similarly, let \(y\in C\text{.}\) Since \(y\in C\) and \(x \in A\text{,}\) we know that \((x,y)\in A\times C\text{,}\) and so \((x,y) \in (A\times B) \cup (A\times C)\text{.}\)
  • So \((x,y) \in RHS\text{.}\)
And the other way around…
  • Let \((x,y) \in (A\times B) \cup (A\times C)\text{,}\) so \((x,y) \in (A\times B)\) or \((x,y) \in (A\times C)\text{.}\) Again, since \(A,B,C\) are non-empty we know that such an \((x,y)\) exists.
    • If \((x,y) \in (A\times B)\) then \(x\in A\) and \(y \in B\text{.}\) Hence \(y \in B\cup \text{(any set we choose)}\text{,}\) and so \(y\in B\cup C\text{.}\)
    • Similarly, if \((x,y) \in A \times C\) then \(x \in A\) and \(y \in C\text{.}\) Hence \(y \in C \cup B\text{.}\)
  • In either case \(x \in A\) and \(y \in B \cup C\text{,}\) so \((x,y) \in LHS\text{.}\)
Now we clean it up and make it a proof.
Solution.
We prove each inclusion in turn. Assume that \((x,y) \in A \times (B\cup C )\text{,}\) so that \(x \in A\) and \(y \in B\cup C\text{.}\) Since the sets are non-empty, such a \((x,y)\) exists. Since \(y \in B\cup C\text{,}\) we know that \(y \in B\) or \(y \in C\text{.}\)
  • If \(y\in B\text{,}\) then since \(x\in A\text{,}\) we know that \((x,y) \in A \times B\text{.}\)
  • Similarly, if \(y\in C\) we know that \((x,y) \in A \times C\text{.}\)
In both cases we have that \((x,y) \in (A \times B) \cup (A \times C)\text{,}\) and so \(LHS \subseteq RHS\text{.}\)
Now assume that \((x,y) \in RHS\text{,}\) so \((x,y) \in A \times B\) or \((x,y)\in A\times C\text{.}\) Again, since the sets are non-empty, such an \((x,y)\) exists.
  • If \((x,y) \in A \times B\text{,}\) then \(x\in A\) and \(y\in B\text{.}\) Hence \(y \in B \cup C\text{.}\)
  • Similarly, if \((x,y) \in A \times C\text{,}\) then \(x \in A\) and \(y \in C\text{.}\) Thus \(y \in C \cup B\text{.}\)
In either case we know that \(x \in A\) and \(y \in B\cup C\text{,}\) so \((x,y) \in A \times (B\cup C)\) as required.
A more challenging distributive law.

Example 8.4.9.

Let \(A,B,C\) be sets, then \(A \cup (B\cap C) = (A\cup C) \cap (A\cup B)\text{.}\)
Scratchwork.
Again, a picture helps.
Lets prove the inclusions one at a time. First LHS is a subset of the RHS.
  • Let \(x \in A\cup(B\cap C)\text{,}\) so that \(x\in A\) or \(x\in(B\cap C)\text{.}\)
    • Assume \(x\in A\text{.}\)
    • Hence \(x \in A\cup B\) and \(x\in A \cup C\) (again because we know that if \(x \in A\) then it is in the union of \(A\) and any set we choose).
    • Thus \(x \in (A\cup B) \cap (A\cup C)\text{.}\)
  • On the other hand, assume that \(x\in B\cap C\)
    • Hence \(x\in B\) and \(x \in C\text{.}\)
    • Since \(x\in B\text{,}\) we know that \(x\in B \cup A\text{.}\)
    • Similarly, since \(x \in C\text{,}\) we know that \(x \in C \cup A\)
    • Because both \(x\in A\cup B\) and \(x \in A\cup C\text{,}\) we have that \(x \in (A\cup B) \cap (A\cup C)\text{.}\)
  • In both cases, \(x \in (A\cup B) \cap (A\cup C)\text{.}\)
Now we prove that the RHS is a subset of the LHS.
  • Let \(x \in (A\cup B) \cap (A\cup C)\text{,}\) so that \(x \in A\cup B\) and \(x \in A \cup C\text{.}\)
  • At this point it is a good idea to explore the 4 possibilities that this suggests.
    • \((x \in A) \land (x\in A)\) — this is easy because we have that \(x \in A \cup \text{(any set we choose)}\)
    • \((x \in A) \land (x\in C) \) — this is also easy because we have that \(x \in A \cup \text{(any set we choose)}\)
    • \((x \in B) \land (x\in A)\) — similarly we have that \(x \in A \cup \text{(any set we choose)}\)
    • \((x \in B) \land (x\in C)\) — not too hard because \(x \in B \cap C\)
    So these four possibilities really break down into two cases. Either \(x\in A\) or \(x\not\in A\text{.}\)
    • If \(x \in A\text{,}\) then we know that \(x \in A \cup \text{anything}\) and so \(x \in A \cup(B\cap C)\text{.}\)
    • Otherwise, if \(x \not\in A\) then we must have that \(x\in B\) and \(x \in C\text{,}\) so \(x\in B\cap C\text{.}\) Then since \(x \in B\cap C\text{,}\) we also have that \(x \in (B\cap C) \cup A\text{.}\)
  • In either case we have that \(x \in A \cup (B \cap C)\text{.}\)
Solution.
We prove each inclusion in turn. Start by assuming that \(x \in A \cup(B \cap C)\text{.}\) Then \(x \in A\) or \(x \in B \cap C\text{.}\) We consider each case in turn.
  • Assume \(x \in A\text{.}\) Then \(x \in A \cup B\) and \(x \in A \cup C\) and so \(x \in RHS\text{.}\)
  • Assume now that \(x \in B \cap C\text{.}\) Then \(x \in B\) and \(x \in C\text{,}\) so \(x \in B \cup A\) and \(x \in C \cup A\text{.}\) Thus \(x \in RHS\text{.}\)
In either case we have \(x\in RHS\text{.}\)
Now assume that \(x \in (A\cup B) \cap (A\cup C)\text{,}\) and so \(x\in A\cup B\) and \(x\in A \cup C\text{.}\)
  • If \(x\in A\) then \(x\in A \cup (B \cap C)\text{.}\)
  • If \(x\not\in A\) then since \(x\in A \cup B\text{,}\) we must have \(x \in B\text{.}\) Similarly since \(x\in A \cup C\) we have \(x\in C\text{.}\) Since \(x\in B\) and \(x \in C\text{,}\) \(x \in B\cap C\text{.}\) Thus \(x \in A \cup (B\cap C)\text{.}\)
Thus if \(x\in LHS\) then \(x \in RHS\text{.}\) And so \(LHS \subseteq RHS\text{.}\)
We’ll prove that \(A-(B\cap C) = (A-B)\cup(A-C)\) using the distributive and DeMorgans laws.

Example 8.4.10.

Let \(A,B,C\) be sets included in a universal set \(U\text{.}\) Show that
\begin{align*} A-(B\cap C) &= (A-B) \cup (A-C). \end{align*}
Scratchwork.
A picture can help us understand this
Let us start with the LHS and we’ll use DeMorgan’s laws and distributive laws to arrive at the RHS.
\begin{align*} A - (B\cap C) &= A \cap \overline{(B\cap C)} & \text{set-difference as intersection}\\ &= A \cap (\bar{B} \cup \bar{C}) & \text{DeMorgan}\\ &= (A \cap \bar{B}) \cup (A \cap \bar{C}) & \text{distributive}\\ &= (A-B) \cup (A-C) & \text{intersection as set-difference} \end{align*}
That is much much easier than proving it from first principles — that is proving it as we proved the couple of examples above. Of course, this argument things requires that we have already done the hard work of proving those other results.
Now the above calculation is all but a proof, we just need a few words. Also, we probably don’t need to annotate our calculation as we have done above — though it wouldn’t hurt. If we don’t then we should, at a minimum, tell the reader what set laws we have used.
Solution.
Let \(A,B,C\) be sets, then
\begin{align*} A - (B\cap C) &= A \cap \overline{(B\cap C)}\\ &= A \cap (\bar{B} \cup \bar{C})\\ &= (A \cap \bar{B}) \cup (A \cap \bar{C})\\ &= (A-B) \cup (A-C) \end{align*}
where we have used DeMorgans’ laws, the distributive law and the fact that \(A-B = A\cap\bar{B}\text{.}\)
A couple more examples.

Example 8.4.11.

Let \(A,B\) be sets included in a universal set \(U\text{.}\) Show that
\begin{align*} (A\cup B) - (A \cap B) \amp = (A-B) \cup (B-A). \end{align*}
This quantity is called the symmetric difference of \(A\) and \(B\) and is sometimes denoted \(A \Delta B\text{.}\)
Scratchwork.
So we can start by trying to rewrite set differences as intersections and see what happens. Actually, we should start by drawing a picture of what is happening.
Now lets try
\begin{align*} (A\cup B) - (A\cap B)\amp = (A\cup B) \cap \overline{(A \cap B)} \amp \text{DeMorgan it} \\ \amp = (A\cup B)\cap (\bar{A} \cup \bar{B}) \amp \text{Distribute} \\ \amp = \big(A \cap (\bar{A} \cup \bar{B}) \big) \cup \big(B \cap (\bar{A} \cup \bar{B})\big) \amp \text{expand more}\\ \amp = (A\cap \bar{A}) \cup (A \cap \bar{B}) \cup (B \cap \bar{A}) \cup (B \cap \bar{B}) \amp \text{now clean up}\\ \amp = \es \cup (A \cap \bar{B}) \cup (B \cap \bar{A}) \cup \es \amp \text{rewrite}\\ \amp = (A - B) \cup (B-A) \end{align*}
Oof! Here we have used that \(C \cap \bar{C} = \es\) and \(C \cup \es = C\) for any set \(C\text{.}\)
What if we try starting with the right and work to the left?
\begin{align*} (A-B) \cup (B-A) \amp= (A \cap \bar{B}) \cup (B \cap \bar{A} ) \amp \text{expand}\\ \amp = \big( (A\cap \bar{B})\cup B \big) \cap \big( (A \cap \bar{B}) \cup \bar{A} \big) \amp \text{expand more}\\ \amp = \big( (A \cup B) \cap (B\cap \bar{B}) \big) \cap \big( (A\cup \bar{A})\cap (\bar{B} \cup \bar{A}) \big) \amp \text{clean up}\\ \amp = \big( (A\cup B)\cap U) \cap \big( U \cap (\bar{B} \cup \bar{A} )\big) \amp \text{clean more}\\ \amp = (A\cup B) \cap (\bar{B} \cup \bar{A} ) \amp \text{deMorgan it}\\ \amp = (A\cup B)\cap \overline{(A\cap B)} \\ \amp = (A\cup B) - (A\cap B) \end{align*}
Not much difference really. Here we have used that \(C \cup \bar{C} = U\) and \(C \cap U = C\text{.}\)
Solution.
Let \(A,B\) be sets. Then
\begin{align*} (A\cup B) - (A\cap B)\amp = (A\cup B) \cap \overline{(A \cap B)} \amp \text{DeMorgans law} \\ \amp = (A\cup B)\cap (\bar{A} \cup \bar{B}) \amp \text{distributive law} \\ \amp = \big(A \cap (\bar{A} \cup \bar{B}) \big) \cup \big(B \cap (\bar{A} \cup \bar{B})\big) \amp \text{distributive law again}\\ \amp = (A\cap \bar{A}) \cup (A \cap \bar{B}) \cup (B \cap \bar{A}) \cup (B \cap \bar{B})\\ \amp = \es \cup (A \cap \bar{B}) \cup (B \cap \bar{A}) \cup \es\\ \amp = (A - B) \cup (B-A) \amp\text{as required}. \end{align*}
Notice that in the last couple of steps we have used the following two facts
\begin{align*} C \cap \bar{C} \amp = \es \amp\text{ and } \amp \amp C \cup \es \amp = C \end{align*}
for any set \(C\text{.}\)
We can also prove this result from first principles — by showing each side is a subset of the other. We don’t present any scratch work here, rather we just leap into the proof. You can see that it is not really any cleaner than the proof we have presented above, but it is always worth seeing things from a different perspective.
We start by proving the left-hand side is a subset of the right-hand side and then the reverse inclusion. We also make use of the following two facts
\begin{align*} (x \not\in A\cap B) \amp \implies (x \not\in A) \lor (x \not\in B) \amp \text{and}\amp\amp (x\not\in A)\amp \implies (x \not\in A \cap B) \end{align*}
which are simply the contrapositives of the following statements
\begin{align*} (x\in A)\land (x\in B) \amp \implies (x\in A\cap B) \amp\text{and}\amp\amp (x\in A\cap B) \amp \implies (x\in A) \end{align*}
  • Assume \(x \in LHS\text{,}\) so \(x \in (A\cup B)\) and \(x \not\in (A\cap B)\text{.}\) This second fact implies that \(x \not\in A\) or \(x \not\in B\text{.}\)
    • If \(x \not \in A\) then since \(x \in A \cup B\text{,}\) it follows that we must have \(x \in B\text{.}\) Since \(x \in B\) and \(x \not\in A\text{,}\) we have that \(x \in B-A\text{.}\)
    • Similarly, if \(x \not\in B\) then since \(x \in A \cup B\text{,}\) we must have \(x \in A\text{.}\) Hence \(x \in A-B\text{.}\)
    In either case \(x \in (A-B) \cup (B-A)\text{,}\) so \(LHS \subseteq RHS\text{.}\)
  • Now assume that \(x \in RHS\text{,}\) so \(x \in A-B\) or \(x \in B-A\text{.}\)
    • If \(x \in A-B\text{,}\) then \(x\in A\) but \(x \not\in B\text{.}\) Since \(x\in A\text{,}\) \(x \in A\cup B\text{.}\) And since \(x \not\in B\text{,}\) we know that \(x \not\in B \cap A\text{.}\) Hence \(x \in (A\cup B) - (A \cap B)\text{.}\)
    • Similarly, if \(x \in B-A\text{,}\) then \(x\in B\) but \(x \not\in A\text{.}\) Since \(x\in B\text{,}\) \(x \in B\cup A\text{.}\) And since \(x \not\in A\text{,}\) we know that \(x \not\in A \cap B\text{.}\) Hence \(x \in (A\cup B) - (A \cap B)\text{.}\)
    Thus we know that \(RHS \subseteq LHS\text{.}\) Consequently \(LHS=RHS\) as required.

Example 8.4.12.

Let \(A,B,C\) be sets included in a universal set \(U\text{.}\) Prove that \(A-(B-C) = (A\cap C) \cup (A-B)\text{.}\)
Scratchwork.
Again, we start with a picture of what is going on:
And now we should play around with some of what we already know
\begin{align*} A - (B-C) &= A \cap \overline{(B-C)} & \text{set difference as intersection}\\ &= A \cap \overline{B \cap \bar{C}} & \text{set difference as intersection}\\ &= A \cap (\bar{B} \cup \bar{\bar{C}}) & \text{DeMorgan}\\ &= A \cap (\bar{B} \cup C) & \text{double complement}\\ &= (A \cap \bar{B}) \cup (A \cap C) & \text{distributive law}\\ &= (A \cap C) \cup (A - B) & \text{intersection as set difference} \end{align*}
oof!
Solution.
Let \(A,B,C\) be sets as given in the statement of the result. Then
\begin{align*} A - (B-C) &= A \cap \overline{(B-C)}\\ &= A \cap \overline{B \cap \bar{C}}\\ &= A \cap (\bar{B} \cup C)\\ &= (A \cap \bar{B}) \cup (A \cap C)\\ &= (A \cap C) \cup (A - B) \end{align*}
where we have used the fact that \(A-B = A\cap\bar{B}\text{,}\) DeMorgans laws and distributive laws.
The Venn diagram is good scratch work for a proof, but really what one is doing is showing that for a particular choice of sets (ie the ones drawn) everything works out. To be a proof it has to work for every choice.
Well … I guess we could draw \(A,B,C\) as one-dimensional sets lying on different axes, and then the product would be some rectangular region in the plane? Something like that might work. A good exercise for the eager reader.
<Prev^TopNext>