Page 151 - Discrete Mathematics and Its Applications

130 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

TABLE 1 Set Identities.
Identity Name
A ∩ U = A Identity laws
A ∪⊆ =A
A ∪ U = U Domination laws
A ∩ ∅=∅
A ∪ A = A Idempotent laws
A ∩ A = A
(A) = A Complementation law

A ∪ B = B ∪ A Commutative laws
A ∩ B = B ∩ A
A ∪ (B ∪ C) = (A ∪ B) ∪ C Associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A ∩ B = A ∪ B De Morgan’s laws
A ∪ B = A ∩ B
A ∪ (A ∩ B) = A Absorption laws
A ∩ (A ∪ B) = A
A ∪ A = U Complement laws
A ∩ A =∅

EXAMPLE 10 Prove that A ∩ B = A ∪ B.

Solution: We will prove that the two sets A ∩ B and A ∪ B are equal by showing that each set
This identity says that
the complement of the is a subset of the other.
intersection of two sets First, we will show that A ∩ B ⊆ A ∪ B. We do this by showing that if x is in A ∩ B, then it
is the union of their must also be in A ∪ B. Now suppose that x ∈ A ∩ B. By the definition of complement, x ∈ A ∩
complements. B. Using the definition of intersection, we see that the proposition ¬((x ∈ A) ∧ (x ∈ B)) is true.
By applying De Morgan’s law for propositions, we see that ¬(x ∈ A) or ¬(x ∈ B). Using
the definition of negation of propositions, we have x ∈ A or x ∈ B. Using the definition of
the complement of a set, we see that this implies that x ∈ A or x ∈ B. Consequently, by the
definition of union, we see that x ∈ A ∪ B. We have now shown that A ∩ B ⊆ A ∪ B.
Next, we will show that A ∪ B ⊆ A ∩ B. We do this by showing that if x is in A ∪ B, then
it must also be in A ∩ B. Now suppose that x ∈ A ∪ B. By the definition of union, we know that
x ∈ A or x ∈ B. Using the definition of complement, we see that x ∈ A or x ∈ B. Consequently,
the proposition ¬(x ∈ A) ∨¬(x ∈ B) is true.
By De Morgan’s law for propositions, we conclude that ¬((x ∈ A) ∧ (x ∈ B)) is true.
By the definition of intersection, it follows that ¬(x ∈ A ∩ B). We now use the definition of
complement to conclude that x ∈ A ∩ B. This shows that A ∪ B ⊆ A ∩ B.
Because we have shown that each set is a subset of the other, the two sets are equal, and the
identity is proved. ▲

We can more succinctly express the reasoning used in Example 10 using set builder notation,
as Example 11 illustrates.