3
$\begingroup$

This is an exercise from Velleman's "How To Prove It". The end of chapter questions have escalated in difficulty, so I just want to make sure that I am on the right track.

  1. Suppose $A$, $B$, and $C$ are sets. Prove that $A \vartriangle B \subseteq C$ iff $A \cup C = B \cup C$.

Proof: Suppose $A \vartriangle B \subseteq C$. Let $x$ be arbitrary. Suppose $x \in A \cup C$, then either $x \in A$ or $x \in C$. We consider these two cases:

Case 1. $x \in A$. Suppose $x \notin B \cup C$. So $x \notin B$ and $x \notin C$. Since $x \in A$ and $x \notin B$, $x \in A\setminus B$. It follows that $x \in A \setminus B \cup B \setminus A$, so $x \in A \vartriangle B$. Since $A \vartriangle B \subseteq C$ and $x \in A \vartriangle B $, $x \in C$. But then we have $x \in C$ and $x \notin C$, which is a contradiction. Thus, $x \in B \cup C$

Case 2. $x \in C$. It immediately follows that $x \in B \cup C$.

In every case, we have shown that $x \in B \cup C$. The proof of $x \in B \cup C \implies x \in A \cup C$ will be similar, but with the roles of $A$ and $B$ switched. Therefore, $A \cup C = B \cup C$.

Now suppose $A \cup C = B \cup C$. Let $x \in A \vartriangle B$ be arbitrary. Then $x \in A \setminus B \cup B \setminus A$, which means that $x \in A \setminus B$ or $x \in B \setminus A$. We consider these two cases:

Case 1. $x \in A \setminus B$. Then $x \in A$ and $x \notin B$. Suppose $x \notin C$. Then since $x \notin B$ and $x \notin C$, $x \notin B \cup C$. Since $x \in A$, $x \in A \cup C$. Then since $A \cup C = B \cup C$, $x \in B \cup C$. But then we have $x \in B \cup C$ and $x \notin B \cup C$, which is a contradiction. Thus, $x \in C$.

Case 2. $x \in B \setminus A$. By similar reasoning as case 1 with $A$ and $B$ switched, we also find that $x \in C$.

In every case, we have shown that $x \in C$. Since $x$ was arbitrary, it follows that $A \vartriangle B \subseteq C$. Therefore, $A \vartriangle B \subseteq C$ iff $A \cup C = B \cup C$. $\square$

$\endgroup$
1
  • 1
    $\begingroup$ A suggested shorter proof, easier (for me at least!) to grasp as a whole: $$ (A \cup C) \setminus (B \cup C) = ((A \cup C) \setminus C) \setminus B = (A \setminus C) \setminus B = (A \setminus B) \setminus C, $$ and similarly $(B \cup C) \setminus (A \cup C) = (B \setminus A) \setminus C,$ therefore: $$ (A \cup C) \vartriangle (B \cup C) = (A \vartriangle B) \setminus C, $$ whence the result. $\endgroup$ Apr 7, 2020 at 14:59

1 Answer 1

1
$\begingroup$

Your proof is fine. I'll go a little further and compliment the way you explained the result in detail.

Having said that, I believe that it can be proven using "iff" statements all the way.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks! What does it mean to use the iff statements all the way? $\endgroup$
    – Iyeeke
    Apr 7, 2020 at 14:07
  • 1
    $\begingroup$ You're welcome, @Iyeeke. I mean starting with $A \vartriangle B\subseteq C$ then using iff statements to get intermediate results until, eventually, you get $A\cup C=B\cup C$. I'm thinking of how to do it myself, so I might update this answer soon. $\endgroup$
    – Shaun
    Apr 7, 2020 at 14:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .