Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 4.2 Laws of Set Theory

Subsection 4.2.1 Tables of Laws

The following basic set laws can be derived using either the Basic Definition or the Set-Membership approach and can be illustrated by Venn diagrams.
Table 4.2.1. Basic Laws of Set Theory
Commutative Laws
(1) \(A \cup B = B \cup A\) (\(1^{\prime}\)) \(A \cap B = B\cap A\)
Associative Laws
(2) \(A \cup (B \cup C)= (A\cup B)\cup C\) (\(2^{\prime}\)) \(A \cap (B \cap C) = (A \cap B) \cap C \)
Distributive Laws
(3) \(A\cap (B \cup C)=(A\cap B )\cup (A\cap C)\) (\(3^{\prime}\)) \(A \cup (B \cap C) = (A \cup B ) \cap (A\cup C)\)
Identity Laws
(4) \(A \cup \emptyset = \emptyset \cup A = A\) (\(4^{\prime}\)) \(A \cap U = U \cap A = A\)
Complement Laws
(5) \(A\cup A^c= U\) (\(5^{\prime}\)) \(A\cap A^c= \emptyset\)
Idempotent Laws
(6) \(A \cup A = A\) (\(6^{\prime}\)) \(A\cap A = A\)
Null Laws
(7) \(A \cup U = U\) (\(7^{\prime}\)) \(A \cap \emptyset =\emptyset\)
Absorption Laws
(8) \(A \cup (A\cap B) = A\) (\(8^{\prime}\)) \(A\cap (A \cup B) = A\)
DeMorgan’s Laws
(9) \((A \cup B)^c= A^c\cap B^c\) (\(9^{\prime}\)) \((A\cap B)^c = A^c \cup B^c\)
Involution Law
(10) \((A^c)^c= A\)
It is quite clear that most of these laws resemble or, in fact, are analogues of laws in basic algebra and the algebra of propositions.

Subsection 4.2.2 Proof Using Previously Proven Theorems

Once a few basic laws or theorems have been established, we frequently use them to prove additional theorems. This method of proof is usually more efficient than that of proof by Definition. To illustrate, let us prove the following Corollary to the Distributive Law. The term "corollary" is used for theorems that can be proven with relative ease from previously proven theorems.
\begin{equation*} \begin{split} (A\cap B) \cup (A\cap B^c) & = A \cap (B \cup B^c)\\ & \quad \textrm{Why?}\\ & = A \cap U\\ &\quad \textrm{Why?}\\ & = A\\ &\quad \textrm{Why?} \end{split}\text{.} \end{equation*}

Subsection 4.2.3 Proof Using the Indirect Method/Contradiction

The procedure one most frequently uses to prove a theorem in mathematics is the Direct Method, as illustrated in Theorem 4.1.7 and Theorem 4.1.8. Occasionally there are situations where this method is not applicable. Consider the following:
Commentary: The usual and first approach would be to assume \(A\subseteq B\) and \(B\cap C = \emptyset\) is true and to attempt to prove \(A\cap C = \emptyset\) is true. To do this you would need to show that nothing is contained in the set \(A \cap C\text{.}\) Think about how you would show that something doesn’t exist. It is very difficult to do directly.
The Indirect Method is much easier: If we assume the conclusion is false and we obtain a contradiction --- then the theorem must be true. This approach is on sound logical footing since it is exactly the same method of indirect proof that we discussed in Subsection 3.5.3.
Assume \(A\subseteq B\) and \(B\cap C = \emptyset\text{,}\) and \(A\cap C \neq \emptyset\text{.}\) To prove that this cannot occur, let \(x\in A \cap C\text{.}\)
\begin{equation*} \begin{split} x \in A \cap C & \Rightarrow x \in A \textrm{ and } x \in C\\ & \Rightarrow x \in B \textrm{ and } x \in C\\ & \Rightarrow x \in B \cap C \end{split}\text{.} \end{equation*}
But this contradicts the second premise. Hence, the theorem is proven.

Exercises 4.2.4 Exercises

In the exercises that follow it is most important that you outline the logical procedures or methods you use.

1.

  1. Prove the associative law for intersection (Law \(2^{\prime}\)) with a Venn diagram.
  2. Prove DeMorgan’s Law (Law 9) with a membership table.
  3. Prove the Idempotent Law (Law 6) using basic definitions.
Answer.
  2. \begin{equation*} \begin{array}{ccccccc} A & B &A^c & B^c & A\cup B & (A\cup B)^c &A^c\cap B^c \\ \hline 0 & 0 &1 & 1 & 0 & 1 & 1 \\ 0 & 1 &1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \end{equation*}
    The last two columns are the same so the two sets must be equal.
  3. \begin{equation*} \begin{split} x\in A\cup A & \Rightarrow (x\in A) \lor (x\in A)\quad\textrm{by the definition of } \cap\\ &\Rightarrow x\in A \quad\textrm{ by the idempotent law of logic} \end{split} \end{equation*}
    Therefore, \(A\cup A\subseteq A\text{.}\)
    \begin{equation*} \begin{split} x\in A &\Rightarrow (x\in A) \lor (x\in A) \quad \textrm{ by conjunctive addition}\\ & \Rightarrow x\in A\cup A\\ \end{split} \end{equation*}
    Therefore, \(A \subseteq A\cup A\) and so we have \(A\cup A=A\text{.}\)

2.

  1. Prove the Absorption Law (Law \(8^{\prime}\)) with a Venn diagram.
  2. Prove the Identity Law (Law 4) with a membership table.
  3. Prove the Involution Law (Law 10) using basic definitions.

3.

Prove the following using the set theory laws, as well as any other theorems proved so far.
  1. \(\displaystyle A \cup (B - A) = A \cup B\)
  2. \(\displaystyle A - B = B^c - A ^c\)
  3. \(\displaystyle A\subseteq B, A\cap C \neq \emptyset \Rightarrow B\cap C \neq \emptyset\)
  4. \(\displaystyle A\cap (B - C) = (A\cap B) - (A\cap C)\)
  5. \(\displaystyle A - (B \cup C) = (A - B)\cap (A - C)\)
Answer.
For all parts of this exercise, a reason should be supplied for each step. We have supplied reasons only for part a and left them out of the other parts to give you further practice.
  1. \begin{equation*} \begin{split} A \cup (B-A)&=A\cup (B \cap A^c) \textrm{ by Exercise 1 of Section 4.1}\\ & =(A\cup B)\cap (A\cup A^c) \textrm{ by the distributive law}\\ &=(A\cup B)\cap U \textrm{ by the null law}\\ &=(A\cup B) \textrm{ by the identity law } \square \end{split}\text{.} \end{equation*}
  2. \begin{equation*} \begin{split} A - B & = A \cap B ^c\\ & =B^c\cap A\\ &=B^c\cap (A^c)^c\\ &=B^c-A^c\\ \end{split}\text{.} \end{equation*}
  3. Select any element, \(x \in A\cap C\text{.}\) One such element exists since \(A\cap C\) is not empty.
    \begin{equation*} \begin{split} x\in A\cap C\ &\Rightarrow x\in A \land x\in C \\ & \Rightarrow x\in B \land x\in C \\ & \Rightarrow x\in B\cap C \\ & \Rightarrow B\cap C \neq \emptyset \quad \square \\ \end{split}\text{.} \end{equation*}
  4. \begin{equation*} \begin{split} A\cap (B-C) &=A\cap (B\cap C^c) \\ & = (A\cap B\cap A^c)\cup (A\cap B\cap C^c) \\ & =(A\cap B)\cap (A^c\cup C^c) \\ & =(A\cap B)\cap (A\cup C)^c \\ & =(A-B)\cap (A-C) \quad \square\\ \end{split}\text{.} \end{equation*}
  5. \begin{equation*} \begin{split} A-(B\cup C)& = A\cap (B\cup C)^c\\ & =A\cap (B^c\cap C^c)\\ & =(A\cap B^c)\cap (A\cap C^c)\\ & =(A-B)\cap (A-C) \quad \square\\ \end{split}\text{.} \end{equation*}

4.

Use previously proven theorems to prove the following.
  1. \(\displaystyle A \cap (B\cap C)^c= (A\cap B^c)\cup (A\cap C^{c })\)
  2. \(\displaystyle A \cap (B\cap (A\cap B)^c)= \emptyset\)
  3. \(\displaystyle (A\cap B) \cup B^c = A \cup B^c\)
  4. \(A \cup (B - C) = (A \cup B) - (C - A)\text{.}\)

5. Hierarchy of Set Operations.

The rules that determine the order of evaluation in a set expression that involves more than one operation are similar to the rules for logic. In the absence of parentheses, complementations are done first, intersections second, and unions third. Parentheses are used to override this order. If the same operation appears two or more consecutive times, evaluate from left to right. In what order are the following expressions performed?
  1. \(A \cup B^c\cap C\text{.}\)
  2. \(A\cap B \cup C\cap B\text{.}\)
  3. \(\displaystyle A \cup B \cup C^c\)
Answer.
  1. \(\displaystyle A\cup ((B^c)\cap C)\)
  2. \(\displaystyle (A\cap B)\cup (C\cap B)\)
  3. \(\displaystyle (A\cup B)\cup (C^c)\)

6.

There are several ways that we can use to format the proofs in this chapter. One that should be familiar to you from Chapter 3 is illustrated with the following alternate proof of part (a) in Theorem 4.1.7:
Table 4.2.4. An alternate format for the proof of Theorem 4.1.7
(1) \(x \in A \cap (B \cup C)\) Premise
(2) \((x \in A) \land (x \in B \cup C)\) (1), definition of intersection
(3) (\(x \in A) \land ((x \in B) \lor (x \in C))\) (2), definition of union
(4) \((x \in A)\land (x\in B)\lor (x \in A)\land (x\in C)\) (3), distribute \(\land\) over \(\lor\)
(5) \((x \in A\cap B) \lor (x \in A \cap C)\) (4), definition of intersection
(6) \(x \in (A \cap B) \cup (A \cap C)\) (5), definition of union \(\blacksquare\)
Prove part (b) of Theorem 4.1.8 and Theorem 4.2.3 using this format.
<Prev^TopNext>