Corollary4.2.2A Corollary to the Distributive Law of Sets
Let A and B be sets. Then \((A\cap B) \cup (A\cap B^c) = A\).
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.
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.
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.
Let A and B be sets. Then \((A\cap B) \cup (A\cap B^c) = A\).
The procedure one most frequently uses to prove a theorem in mathematics is the Direct Method, as illustrated in Theorems 4.1.1 and 4.1.2. Occasionally there are situations where this method is not applicable. Consider the following:
Let \(A, B, C\) be sets. If \(A\subseteq B\) and \(B\cap C = \emptyset\), then \(A\cap C = \emptyset\).
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\). 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 Chapter 8.
Assume \(A\subseteq B\) and \(B\cap C = \emptyset\), and \(A\cap C \neq \emptyset\). To prove that this cannot occur, let \(x\in A \cap C\).
But this contradicts the second premise. Hence, the theorem is proven.
In the exercises that follow it is most important that you outline the logical procedures or methods you use.
The last two columns are the same so the two sets must be equal.
Therefore, \(A\cup A\subseteq A\).
Therefore, \(A \subseteq A\cup A\) and so we have \(A\cup A=A\).
Prove the following using the set theory laws, as well as any other theorems proved so far.
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.
Select any element, \(x \in A\cap C\). One such element exists since \(A\cap C\) is not empty.
Use previously proven theorems to prove the following.
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?
\(A\cup ((B^c)\cap C)\)
\((A\cap B)\cup (C\cap B)\)
\((A\cup B)\cup (C^c)\)
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:
(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.