Answer:
Explanation:
Math 311
Set Proofs Handout and Activity
Recall that a set A is a subset of a set B, written A ⊆ B if every element of the set A is also an element of the set B. To show
that one set is a subset of another set using a paragraph proof, we usually use what is called a “general element argument”.
Here is an example:
Example 1: We will prove that A ∩ B ⊂ A
Proof: Let x be an arbitrary element of A ∩ B. By definition of set intersection, since x ∈ A ∩ B, then x ∈ A and x ∈ B.
In particular, x ∈ A. Since every element of A ∩ B is also an element of A, A ∩ B ⊆ A ✷
Since that was a fairly straightforward example, let’s try another.
Example 2: We will prove that If A ⊆ B, then B ⊆ A.
Proof: Let x ∈ B. By definition of set complement, x /∈ B. Recall that since A ⊆ B, whenever y ∈ A, we also have y ∈ B.
Therefore, using contraposition, whenever y /∈ B, we must have y /∈ A. From this, since x /∈ B, then x /∈ A. Therefore x ∈ A.
Hence B ⊆ A. ✷
Lastly, in order to formally prove that two sets are equal, say S = T, we must show that S ⊆ T and that T ⊆ S. This will
require two general element arguments.
Example 3: We will prove that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
Proof:
“⊆” Let x ∈ A ∪ (B ∩ C). Then x ∈ A or x ∈ B ∩ C. We will consider these two cases separately.
Case 1: Suppose x ∈ A. Then, by definition of set union, x ∈ A ∪ B. Similarly, x ∈ A ∪ C. Thus. by definition of set
intersection, we must have x ∈ (A ∪ B) ∩ (A ∪ C).
Case 2: Suppose x ∈ B ∩ C. Then, by definition of set intersection, x ∈ B and x ∈ C. Since x ∈ B, then again by the
definition of set union, x ∈ A ∪ B. Similarly, since x ∈ C, then x ∈ A ∪ C. Hence, again by definition of set intersection,
x ∈ (A ∪ B) ∩ (A ∪ C).
Since these are the only possible cases, then A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C)
“⊇” Let x ∈ (A ∪ B) ∩ (A ∪ C). Then, by definition of set intersection, x ∈ A ∪ B and x ∈ A ∪ C. We will once again split
into cases.
Case 1: Suppose x ∈ A. Then, by definition of set union, x ∈ A ∪ (B ∩ C).
Case 2: Suppose x /∈ A. Since x ∈ A ∪ B, then, by definition of set union, we must have x ∈ B. Similarly, since x ∈ A ∪ C,
we must have x ∈ C. Therefore, by definition of set intersection, we have x ∈ B ∩ C. Hence, again by definition of set union,
A ∪ (B ∩ C).
Since these are the only possible cases, then A ∪ (B ∩ C) ⊇ (A ∪ B) ∩ (A ∪ C)
Thus A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). ✷
Instructions: Use general element arguments to show that following (Note that only 3, 4, and 5 may be used as portfolio
proofs):
1. Proposition 1: B − A ⊆ B
2. Proposition 2: A − (A − B) ⊆ B
3. Proposition 3: A − (A − B) = A ∩ B
4. Proposition 4: (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B)
5. Proposition 5: A × (B ∩ C) = (A × B) ∩ (A × C)