Corollary 4.2.2. A Corollary to the Distributive Law of Sets.
Let A and B be sets. Then \((A\cap B) \cup (A\cap B^c) = A\text{.}\)
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\) |
(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\) |
(1) | \((x,y)\in A \times (B\cap C)\) | Premise |
(2) | \(x \in A\) | (1), definition of Cartesian Product |
(3) | \(y \in B \cap C\) | (1), definition of Cartesian Product |
(4) | \(y \in B\) | (3),definition of intersection |
(5) | \((x,y) \in A\times B\) | (2),(4), definition of Cartesian Product |
(6) | \(y \in C\) | (3),definition of intersection |
(7) | \((x,y) \in A\times C\) | (2),(6), definition of Cartesian Product |
(8) | \((x,y) \in (A\times B)\cap (A\times C) \) | (5),(7), definition of Cartesian Product \(\quad \blacksquare\) |
(1) | \(x_0 \in A \cap C\) | Negated Conclusion - \(A\cap C\) non-empty |
(2) | \(x_0 \in A\) | (1), definition of intersection |
(3) | \(A \subseteq B\) | Premise |
(4) | \(x_0 \in B\) | (2),(3),definition of subset |
(5) | \(x_0 \in C\) | (1), definition of intersection |
(6) | \(x_0 \in B \cap C\) | (4),(5), definition of intersection |
(7) | \(B \cap C= \emptyset\) | Premise |
(7) | Contradiction | (6),(7) \(\quad \blacksquare\) |