Proving Set Theorems

Proving Set Theorems

We have looked at some various equalities between sets and proven them. We will now formally demonstrate how to prove that two sets are equal. Recall that we can say that for two sets $A$ and $B$, that $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$. Therefore, we must show that both hold for two sets to be equal.

Before we look at proving some set equalities or even proving that a set is a subset of another set, let's first review some important properties regarding sets. Notice the difference between "or", "and" in the following as well:

  • 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$.

More examples can be found on the Proving Set Theorems Examples 1 page.

Example 1

Prove that if $A \cup ( A \cap B ) = A$ (one of the absorption laws of sets).

  • Proof: $\Rightarrow$ We want to first show that $A \cup (A \cap B) \subseteq A$. If $A \cup (A \cap B) = \emptyset$ then we are done since the empty set is a subset of any set. If not, then let $x \in A \cup (A \cap B)$. Then $x \in A$ or $x \in A \cap B$. If $x \in A$ we are done. If $x \in A \cap B$ then $x \in A$ and we are done and so $A \cup (A \cap B) \subseteq A$.
  • $\Leftarrow$ We want to now show that $A \subseteq A \cup (A \cap B)$. If $A = \emptyset$ then we are done. If not then let $x \in A$. Then $x \in A$ and $x \in A \cap B$ so $x \in A \cup (A \cap B)$. Therefore $A \subseteq A \cup (A \cap B)$.

Example 2

Prove that $A \setminus (A \setminus B) \subseteq B$.

Notice that in this example we are not asked to prove a set equality. In fact, we're only asked to prove that one set is a subset of another!

  • Proof: We want to show $A \setminus ( A \setminus B ) \subset B$. Let $x \in A \setminus (A \setminus B)$. Then $x \in A$ and $x \not \in (A \setminus B)]]. If [[$ x \not \in (A \setminus B)$ then $x \not in A$ or $x \in B$. Therefore $A \setminus (A \setminus B) \subseteq B$.

Example 3

Prove that if $A \subseteq C$ and $B \subseteq C$ and $C \setminus A \subseteq B$, then $C = A \cup B$.

  • Proof: $\Rightarrow$ We want to first show that $C \subseteq A \cup B$. If $C = \emptyset$ then we are done since the empty set is always a subset of any set. Now if $C \neq \emptyset$, then let some element $x \in C$. So either $x \in A$ or $x \not \in A$. If $x \in A$ then $x \in A \cup B$ and we are done. If $x \not \in A$ then $x \in (C \setminus A)$. But if $x \in (C \setminus A)$ then $x \in B$ so $x \in A \cup B$ or rather, $C \subseteq A \cup B$.
  • $\Leftarrow$ We want to now show that $A \cup B \subseteq C$. If $A \cup B = \emptyset$ then we are done once again. If not, let $x \in A \cup B$. Then $x \in A$ or $x \in B$. If $x \in A$ then $x \in C$ since $A \subseteq C$. If $x \in B$ then $x \in C$ since $B \subseteq C$. Therefore $x \in C$ or rather, $A \cup B \subseteq C$.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License