3
$\begingroup$

This is Velleman's exercise 3.5.21 (And NO, not a duplicate of "Suppose $A, B$, and C are sets. Prove that $C\subset A\Delta B \Leftrightarrow C \subset A \cup B$ and $A \cap B \cap C = \emptyset $", my question is different):

Suppose $A$, $B$, and $C$ are sets. Prove that $C \subseteq A\,\triangle\,B$ iff $C \subseteq A \cup B$ and $A \cap B \cap C = \emptyset$.

And here's my proof of it:

Proof.

($\rightarrow$) Suppose $C ⊆ A △ B$ and let $x$ be an arbitrary element of $C$, then we have $x ∈ A △ B$. We now consider two cases:

Case 1. $x ∈ A\setminus B$, which means $x ∈ A$ but $x ∉ B$. Thus $x ∈ A ∪ B$.

Case 2. $x ∈ B\setminus A$, which means $x ∈ B$ but $x ∉ A$. Thus $x ∈ A ∪ B$.

Now suppose $A ∩ B ∩ C \neq ∅$. From $x ∈ A △ B$ we have that either $x ∉ A$ or $x ∉ B$ which in either case is a contradiction and hence $A ∩ B ∩ C = ∅$.

We have $x ∈ A ∪ B$ and $A ∩ B ∩ C = ∅$ and therefore, if $C ⊆ A △ B$, then $C ⊆ A ∪ B$ and $A ∩ B ∩ C = ∅$.

($\leftarrow$) Suppose $C ⊆ A ∪ B$ and $A ∩ B ∩ C = ∅$ and let $x$ be an arbitrary element of $C$. We now have two different cases to consider:

Case 1. $x ∈ B\setminus A$, then clearly $x ∈ A △ B$.

Case 2. $x ∉ B\setminus A$, which means $x ∈ A$ but $x ∉ B$. Since $A ∩ B ∩ C = ∅$ is equivalent to $∀x(x ∈ A \Rightarrow (x ∈ C \Rightarrow x ∉ B))$, then by $x ∈ A$ we have $(x ∈ C \Rightarrow x ∉ B)$. Since we had $x ∈ C$, then $x ∉ B$ and then $x ∈ A\setminus B$. Ergo $x ∈ A △ B$.

From both case we have $x ∈ A △ B$. Since $x$ was arbitrary, $C ⊆ A △ B$ and therefore, if $C ⊆ A ∪ B$ and $A ∩ B ∩ C = ∅$, then $C ⊆ A △ B$.

By ($\rightarrow$) and ($\leftarrow$) we have $C ⊆ A △ B$ iff $C ⊆ A ∪ B$ and $A ∩ B ∩ C = ∅$.

Now here are my questions:

  1. Is my proof valid?

  2. In part one (i.e. ($\rightarrow$)), is there anything wrong with the proof of $A ∩ B ∩ C = ∅$?

  3. In part two (i.e. ($\leftarrow$)), the second case seems to be a little redundant to me! Is that correct (i.e. is my proof of it correct)?

Thanks in advance.

$\endgroup$
2
$\begingroup$

In the forward direction, I don't see how you obtain a contradiction after "From $x\in A\,\triangle\,B$ we have that either $x\not\in A$ or $x\not\in B$..." Just because we have $A\cap B\cap C\ne\emptyset$ doesn't mean that everything in $A$ must also be in $B$, or visa versa. The fix is to just assume you have something in the intersection instead of working with the same $x$ as from before:

Since $A\cap B\cap C\ne\emptyset$, then there is $y\in A\cap B\cap C$. Since $y\in C$, then $y\in A\,\triangle\,B$. Thus $y\not\in A$ or $y\not\in B$, which contradicts $y\in A\cap B$.

In case 2 of the reverse direction, you wrote "...which means $x\in A$ but $x\not\in B$". This is true, but you are skipping a few steps. Since $x\in C$ and $x\not\in B\setminus A$, then we must have $x\in A\setminus B$ or $x\in A\cap B$. However the later is impossible because $A\cap B\cap C=\emptyset$. From here there is no need for the next line, because $x\in A$ and $x\not\in B$ means $x\in A\setminus B$.

After these fixes you have a perfectly valid proof. However I would consider different cases in the reverse direction. You know that $x\in C\subseteq A\cup B$. Thus it would seem more natural to consider the cases:

Case 1: $x\in A$. Since $x\in A\cap C$ and $A\cap B\cap C=\emptyset$, we deduce $x\not\in B$. Thus $x\in A\setminus B$ and consequently $x\in A\,\triangle\,B$.

Case 2: $x\in B$. Similar to case $1$, we get $x\in B\setminus A$ and thus $x\in A\,\triangle\,B$.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot and great as always. One more thing. I don't want to be rude but is it possible for you to answer this another unanswered question of mine: "math.stackexchange.com/questions/2401172/…" as well? $\endgroup$ – Heptapod Aug 21 '17 at 16:14
  • 1
    $\begingroup$ @Heptapod Sure I'll take a look! $\endgroup$ – John Griffin Aug 21 '17 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.