Suppose $A$, $B$, and $C$ are sets. Prove that $A\Delta B$ and $C$ are disjoint iff $A\cap C=B\cap C$.

elementary-set-theoryproof-writingsolution-verification

This is exercise $3.5.19$ from the book How to Prove it by Velleman $($$2^{nd}$ edition$)$:

Suppose $A$, $B$, and $C$ are sets. Prove that $A\Delta B$ and $C$ are disjoint iff $A\cap C=B\cap C$.

I am familiar with the proof by contradiction of the above theorem $($in both directions$)$ but I was wondering whether we could prove the left-to-right direction of the above theorem as a direct proof in the following way:

$(\rightarrow)$ Suppose $(A\Delta B)\cap C=\emptyset$. Let $x$ be an arbitrary element of $A\cap C$. This means $x\in A$ and $x\in C$. From $(A\Delta B)\cap C=\emptyset$ and $x\in C$, $x\notin A\Delta B$. This means $x\notin A\cup B$ or $x\in A\cap B$. Now we consider two cases.

Case $1.$ Suppose $x\notin A\cup B$ and so $x\notin A$ which is a contradiction.

Case $2.$ Suppose $x\in A\cap B$ and so $x\in B$. Therefore $x\in B\cap C$.

From case $1$ or case $2$ we obtain $x\in B\cap C$. Since $x$ is arbitrary, $\forall x(x\in A\cap C\rightarrow x\in B\cap C)$ and so $A\cap C\subseteq B\cap C$. A similar argument shows that $B\cap C\subseteq A\cap C$. Therefore if $A\Delta B$ and $C$ are dijoint then $A\cap C=B\cap C$. $Q.E.D.$

Is my proof valid$?$

Thanks for your attention.

Best Answer

Your proof is correct.

Based on this proof, and several of your other proofs in similar questions, it is clear that you have a good grasp of how to prove statements like this by arguing at the level of elements of sets.

For the next step in your self-study, I strongly suggest you try out some proofs where you argue at the level of sets themselves. I will explain what I mean. (By the way, this is the first step toward understanding Oliver's answer.)

In basic arithmetic, you have certain operations on the integers, like addition and multiplication, which you can combine into complicated calculations. By analogy, you can think of "complement", "union", "intersection", "set difference", and "symmetric difference" as operations on sets that behave according to certain rules. The "subset" relation is similar in that it behaves like an ordering. Here are some fundamental rules for these operations. (In each statement, the sets involved are arbitrary.)

  1. associativity: \begin{align} A \cap (B \cap C) &= (A \cap B) \cap C\\ A \cup (B \cup C) &= (A \cup B) \cup C \end{align}

  2. commutativity \begin{align} A \cap B &= B \cap A\\ A \cup B &= B \cup A\\ \end{align}

  3. distributivity \begin{align} A \cap (B \cup C) &= (A \cap B) \cup (A \cap C)\\ A \cup (B \cap C) &= (A \cup B) \cap (A \cup C) \end{align}

  4. subsets $$ A \subseteq B \Leftrightarrow A \cap \neg B = \emptyset $$

  5. identity and annihilation of $\emptyset$ \begin{align} A \cup \emptyset &= A\\ A \cap \emptyset &= \emptyset \end{align}

  6. idempotence \begin{align} A \cup A &= A\\ A \cap A &= A \end{align}

  7. absorption \begin{align} A \cap (A \cup B) &= A \\ A \cup (A \cap B) &= A \end{align}

  8. complementation \begin{align} A \cap \neg A &= \emptyset\\ \neg (\neg A) &= A \end{align}

  9. De Morgan's Laws \begin{align} \neg (A \cap B) &= \neg A \cup \neg B\\ \neg (A \cup B) &= \neg A \cap \neg B \end{align}

Here are some remarks about these rules.

  1. This list is not exhaustive, and the whole setting can be made more abstract. For more, check out the Wikipedia article on "boolean algebras"

  2. This list is not "minimal" in the sense that there are many rules that can be derived as easy consequences of other rules.

  3. Each of these rules must be proved of course, and many of them you have already proved. But, in addition to proving the formally and rigorously (e.g., at the level of elements and with cases, etc.) it is a good idea to think about why each rule intuitively makes sense and what the rules are saying about sets. Venn diagrams can be useful here.

  4. I have left out the rules that mention the "universe" (e.g., $A\cup\neg A=U$) on purpose. It seems like most of the exercises you have posted from this book do not reference the universe. But again, more can be found in the Wikipedia article.

So now, with these rules in hand, I would encourage you to go back over all of the exercises you have asked about from this book and look for proofs using just these rules that don't mention specific elements of sets (or at least mention elements as little as possible). My important remark here is that I'm not saying these kinds of proofs are inherently "better" or "more correct" (although you'll find that people sometimes view them as more aesthetically pleasing). An understanding of both proof strategies is valuable.

Here are some examples of useful facts you can prove with the rules above.

Lemma 1: If $A,B,C$ are sets, and $A \cap C = \emptyset$, then $A \cap B= A \cap (B \cup C)$.

Proof: \begin{align} A \cap (B \cup C) &= (A \cap B) \cup (A \cap C) \tag{distributivity}\\ &= (A \cap B) \cup \emptyset \tag{assumption}\\ &= A \cap B \tag{identity} \end{align}

Lemma 2: If $A$ and $B$ are sets then $A\Delta B=\emptyset$ iff $A=B$.

Proof. By definition, $A \Delta B = (A \cap \neg B) \cup (B \cap \neg A)$. Note also that the union of two sets is empty if and only if both sets in the union are empty (you could formally prove this using absorption and identity rules; but a direct proof with elements is probably better). Therefore \begin{align} A \Delta B=\emptyset &\Leftrightarrow A \cap \neg B = \emptyset \textrm{ and } B \cap \neg A = \emptyset\\ &\Leftrightarrow A \subseteq B \textrm{ and } B \subseteq A \tag{subset rule}\\ &\Leftrightarrow A = B \end{align}

Lemma 3: If $A,B,C$ are sets then $(A\Delta B)\cap C=(A\cap C)\Delta (B\cap C)$

Proof: \begin{align} (A \Delta B) \cap C &= C \cap (A \Delta B) \tag{commutativity}\\ &= C \cap ((A \cap\neg B) \cup (B \cap \neg A)) \tag{definition of $\Delta$}\\ &= (C \cap (A \cap \neg B)) \cup (C \cap (B \cap \neg A)) \tag{distributivity}\\ &= \big((C \cap A) \cap\neg B \big) \cup \big((C \cap B) \cap \neg A \big) \tag{associativity}\\ &= \big((A \cap C) \cap \neg B \big) \cup \big(B \cap C) \cap \neg A \big) \tag{commutativity}\\ &= \big((A \cap C) \cap (\neg B \cup \neg C) \big) \cup \big((B \cap C) \cap (\neg A \cup \neg C) \big) \tag{Lemma 1}\\ &= \big((A \cap C) \cap \neg (B\cap C) \big) \cup \big((B\cap C) \cap \neg (A \cap C) \big) \tag{De Morgan}\\ &= (A\cap C)\Delta (B\cap C) \tag{definition} \end{align}

Remarks. Eventually people take very basic rules like commutativity and associativity for granted, and so you wouldn't necessarily need make those steps explicit. You can experiment with this, and try to find a simpler or shorter proof.

You can now think of the previous lemmas as "new rules" to add to the toolkit. For example Lemma 3 is like a "distribution rule" for symmetric difference and intersection. Having these new results will help add to your insight and intuition, and also save time later so that you don't keep re-proving the same basic rules over and over again. For example, I have chosen the previous lemmas on purpose to provide the following nice proof of the main problem in your question above.

Corollary 4: If $A,B,C$ are sets then $(A \Delta B) \cap C = \emptyset$ iff $A \cap C = B \cap C$.

Proof: \begin{align} (A \Delta B) \cap C = \emptyset &\Leftrightarrow (A \cap C) \Delta (B \cap C) = \emptyset \tag{Lemma 3}\\ &\Leftrightarrow A \cap C = B \cap C \tag{Lemma 2} \end{align}

Related Question