Step-by-step 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)