0
$\begingroup$

The problem statement is in the title.

I'm proving a problem in class and I need to show the above containment. I've drawn some Venn diagrams to make sure the containment makes sense, and it does to me, but I am still having problems proving this statement. I know that $A \Delta B = (A \cup B) – ( A \cap B)$, and I can see through the Venn diagrams I have drawn how [$C \subset A \Delta B$ iff $C \subset A \cup B$ and $A \cap B \cap C =\emptyset $], but I am having trouble explaining this to someone else.

$\endgroup$
  • $\begingroup$ Please make the question's body self-contained. $\endgroup$ – Asaf Karagila Apr 9 '14 at 16:32
1
$\begingroup$

Let's try necessity. Let $$c \in C \subseteq A \Delta B = (A \cup B) - (A \cap B).$$ Then, $c \in A \cup B$ and $c \not \in A \cap B$. Thus,

  • every $c \in C$ also satisfies $c \in A \cup B$, hence, $C \subseteq A \cup B$;
  • every $c \in C$ also satisfies $c \not \in A \cap B$, hence $C \cap A \cap B = \emptyset$.

Can you go the other way?

$\endgroup$
  • $\begingroup$ C ⊆ A Δ B = C ⊆ (A ⋃ B) ⋂ ¬(A ⋂ B) = C ⊆ (A ⋃ B) ⋂ (¬A ⋂ ¬B) = C ⊆ (A ⋂ ¬B) ⋃ (B ⋂ ¬A) Since c ϵ C also satisfies either A or B, but not A and B, the statement A ⋂ B ⋂ C must be an empty or null set. I’m still learning, so please tell me where I am either incorrect or where I could clean up my terminology. $\endgroup$ – Gabe Carr Apr 9 '14 at 17:05
  • $\begingroup$ @GabeCarr not sure what you mean. The event $z \in X - Y = X \cap \bar{Y}$ happens if and only if $z \in X$ and $z \not \in Y$. $\endgroup$ – gt6989b Apr 9 '14 at 17:07
  • $\begingroup$ What I was trying to convey was that C is a subset of A or B, but that C is not a subset of A and B. $\endgroup$ – Gabe Carr Apr 9 '14 at 17:40
  • $\begingroup$ @GabeCarr the phrase "the statement A ⋂ B ⋂ C must be an empty or null set" is wrong: $A \cap B \cap C$ is not a statement, and statements cannot be empty or null sets. What is meant to say is that the set $A \cap B \cap C$ is empty, i.e. $A \cap B \cap C = \emptyset$ $\endgroup$ – gt6989b Apr 9 '14 at 17:44
1
$\begingroup$

I would approach this as a simplification problem, which is straightforwardly solved by expanding the definitions from set theory and then simplifying using the rules of logic.

So I would start on the most complex side, and calculate as follows: \begin{align} & C \subseteq A \cup B \;\land\; A \cap B \cap C = \varnothing \\ \equiv & \qquad \text{"definitions of $\;\subseteq\;$; basic property of $\;\varnothing\;$"} \\ & \langle \forall x :: x \in C \;\Rightarrow\; x \in A \cup B \rangle \;\land\; \langle \forall x :: \lnot(x \in A \cap B \cap C) \rangle \\ \equiv & \qquad \text{"definition of $\;\cup\;$, and of $\;\cap\;$ twice; merge quantifications"} \\ & \langle \forall x :: (x \in C \;\Rightarrow\; x \in A \lor x \in B) \;\land\; \lnot(x \in A \land x \in B \land x \in C) \rangle \\ \equiv & \qquad \text{"logic: write $\;P \Rightarrow Q\;$ as $\;\lnot P \lor Q\;$ in left part;} \\ & \qquad \phantom{\text{"}}\text{DeMorgan for right part} \\ & \qquad \phantom{\text{"}}\text{-- to get everything in similar shape"} \\ & \langle \forall x :: (x \not\in C \lor x \in A \lor x \in B) \;\land\; (x \not\in A \lor x \not\in B \lor x \not\in C) \rangle \\ \equiv & \qquad \text{"logic: extract common disjunct $\;x \not\in C\;$"} \\ & \langle \forall x :: x \not\in C \lor ( (x \in A \lor x \in B) \;\land\; (x \not\in A \lor x \not\in B) ) \rangle \\ \equiv & \qquad \text{"logic: simplify $\;(P \lor Q) \land (\lnot P \lor \lnot Q)\;$ to $\;P \not\equiv Q\;$"} \\ & \langle \forall x :: x \in C \;\Rightarrow\; ( x \in A \not\equiv x \in B ) \rangle \\ \equiv & \qquad \text{"definition of $\;\triangle\;$; definition of $\;\subseteq\;$"} \\ & C \subseteq A \triangle B \\ \end{align} This completes the proof.

In the last step I used a not-too-well-known definition of set difference: $$ x \in A \triangle B \;\equiv\; x \in A \not\equiv x \in B $$

$\endgroup$

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.