Proving Set Theorems Examples 1
We will now look at some more examples of Proving Set Theorems. Before we look at these examples, please recall the following implications as they are fundamentally important for writing up our proofs.
- If $A \subseteq B$ and $x \in A$ implies $x \in B$.
- $x \in A \cup B$ implies $x \in A$ or $x \in B$.
- $x \not \in A \cup B$ implies $x \not \in A$ and $x \not \in B$
- $x \in A \cap B$ implies $x \in A$ and $x \in B$.
- $x \not \in A \cap B$ implies $x \not \in A$ or $x \not \in B$
- $x \in A \setminus B$ implies $x \in A$ and $x \not \in B$.
- $x \not \in A \setminus B$ implies $x \not \in A$ or $x \in B$.
Example 1
Prove that $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.
- Proof: $\Rightarrow$ If $A \cup (B \cap C) = \emptyset$ then we are done. If not, then let $x \in A \cup (B \cap C)$. Then $x \in A$ or $x \in B \cap C$. If $x \in A$ then $x \in A cup B$ and $x \in A cup C$ so $x \in (A \cup B) \cap (A \cup C)$ and we're done. If $x \in B \cap C$, then $x \in B$ and $x \in C$. So $x \in A$ or $x \in B$ and $x \in A$ or $x \in C$ so $x \in (A \cup B) \cap (A \cup C)$. Therefore $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.
Example 2
Let $S := \{ x \in \mathbb{R} : x^2 > x + 6 \}$ and let $T := \{ x \in \mathbb{R} : x > 3 \: \mathrm{or} \: x < -2 \}$. Prove that $S = T$.
This example is different from our past examples, but we will tackle it on in the same approach.
- Proof: $\Rightarrow$ We first want to show $S \subseteq T$. First let $x \in S$. So $x \in \mathbb{R}$ and $x^2 > x + 6$. Using some algebraic manipulation we see that $x^2 - x - 6 > 0$ or rather $(x + 2)(x - 3) > 0$. There are two cases to consider.
- Our first case is that both factors are positive. Then $x + 2 > 0$ and $x - 3 > 0$. Therefore $x > -2$ and $x > 3 %]]. Since [[$ x > 3$ we have that $x \in T$ and we are done.
- Our second case is that both factors are negative. Then $x + 2 < 0$ and $x - 3 < 0$. Therefore $x < -2$ and $x < 3$. Since $x < -2$ we have that $x \in T$ once again, and we are done. So $S \subseteq T$.
- $\Leftarrow$ We now want to show $T \subseteq S$. Let $x \in T$. Then $x \in \mathbb{R}$ such that $x > 3$ or $x < -2$. If $x > 3$ then $x - 3 > 0$ and $x + 2 > 0$ and so $(x - 3)(x + 2) > 0$ so then $x \in S$ and we are done. If $x < -2$ then $x - 3 < 0$ and $x + 2 < 0$ and so $(x - 3)(x + 2) < 0$ so then $x \in S$ once again and we're done. Therefore $T \subseteq S$ and we conclude $S = T$.
Example 3
Prove that if $A$ and $B$ are sets then $P(A) \cup P(B) \subseteq P(A \cup B)$.
We note that in this example we are working with the power sets of sets $A$ and $B$ denoted $P(A)$ and $P(B)$ respectively. Thus an element in a power set by definition will be a subset of either $A$ or $B$ so we will use a capital $X$ to denote an element in either power set.
- Proof: $\Rightarrow$ Let $X \in P(A) \cup P(B)$. Then $X \in P(A)$ or $X \in P(B)$. If $X \in P(A)$ then by the definition of a power set $X \subseteq A$. So then $X \subseteq A \cup B$ and so $X \in P(A \cup B)$. If $X \in P(A)$ then by the definition of a power set $X \subseteq B$. So then $X \subseteq A \cup B$ and so $X \in P(A \cup B)$. We conclude then that $P(A) \cup P(B) \subseteq P(A \cup B)$.