This is an exercise from Velleman's "How To Prove It":
- Suppose $A$, $B$, and $C$ are sets. Prove that $A \cup C \subseteq B \cup C$ iff $A \setminus C \subseteq B \setminus C$.
Proof: Suppose that $A \cup C \subseteq B \cup C$. Let $x \in A \setminus C$ be arbitrary. Then $x \in A$ and $x \notin C$. Suppose $x \notin B$. Since $x \notin B$ and $x \notin C$, $x \notin B \cup C$. Since $x \notin B \cup C$ and $A \cup C \subseteq B \cup C$, $x \notin A \cup C$. But this contradicts the fact that $x \in A$. Thus, $x \in B$. Since $x \in B$ and $x \notin C$, $x \in B \setminus C$. Since $x$ was arbitrary, it follows that $A \setminus C \subseteq B \setminus C$.
Now suppose that $A \setminus C \subseteq B \setminus C$. Let $x \in A \cup C$ be arbitrary. Then either $x \in A$ or $x \in C$. Suppose $ x \notin B \cup C$. Since $x \notin C$, it follows that $x \in A$, so $x \in A \setminus C$. Then since $A \setminus C \subseteq B \setminus C$, $x \in B \setminus C$. But this contradicts the fact that $x \notin B$. Thus, $x \in B \cup C$. $\square$
My first approach for the $\rightarrow$ direction was to use a proof by cases on whether $x \in B$ or $x \notin B$. If $x \in B$, then clearly $x \in B \setminus C$, but the other case leads to a contradiction (as shown in the proof above). In a proof by cases, is it valid to eliminate some cases by showing that they lead to a contradiction? I would appreciate any other comments on the proof as well. Thanks!
Best Answer
Yes you can eliminate cases using contradiction,your proof writing is totally ok..