Prove of disprove: for every 3 sets, $A,B,C: (A\setminus B)\cup (A\setminus C)=B\Longleftrightarrow A=B$ and $B \cap C = \emptyset$

Proof : We prove each statement implies the other.

1) First we show that $(A\setminus B)\cup (A\setminus C)=B\Longrightarrow A=B$ and $B \cap C = \emptyset$

2) $(A \setminus B)=A$ and $(A \setminus C)=A$, therefore $A=B$

3) Since $A=B$, then $(A\setminus C) = (B\setminus C)$

4) Therefore, $B\cap C = \emptyset$

5) Now we show that $A=B$ and $B\cap C = \emptyset \Longrightarrow (A\setminus B)\cup (A\setminus C)=B$

6) Since $A=B$, then $(A\setminus B) = \emptyset$

7) $B\cap C$ must not share any common elements for $B\cap C = \emptyset$ to hold

8) Thus, $(A \setminus C) = (B \setminus C) = B$ (since $A=B$)

9) Therefore $(A \setminus B) = \emptyset$ and $(A \setminus C) = B$

10) This gives us that: $\emptyset \cup B = B$

I would to like know if my proof is complete, correct and where it contains any faulty logic. I'm new to proof writing, so constructive criticism goes a long way for me.

  • $\begingroup$ How is 2) related to 1)? Note that $X\setminus Y = \{s\,|\,s\in X,s\notin Y\}$. $\endgroup$ – Nex Nov 10 '15 at 19:16
  • $\begingroup$ @Nex The set differences. No? $(A \setminus B)\Longrightarrow A$ and $(A \setminus C)\Longrightarrow A$ $\endgroup$ – Cherry_Developer Nov 10 '15 at 19:18

We have: $x \in B \Leftrightarrow x\in A\setminus C$ (because $x \notin A\setminus B$) $\Rightarrow A\setminus C=B \Rightarrow B=(A\setminus B)\cup(A\setminus C)=A\setminus B \cup B = A$.

On the other hand, $A\setminus C = B \Leftrightarrow B\setminus C = B \Leftrightarrow C= \emptyset \Rightarrow B\cap C=\emptyset$

  • $\begingroup$ Can you please clarify this? $\endgroup$ – Cherry_Developer Nov 10 '15 at 20:05
  • $\begingroup$ can you specify which part? $\endgroup$ – SiXUlm Nov 10 '15 at 20:37

Why does $(A \setminus B) = A$ in step 2) ? There is no explanation (it's false too, in general). $(A \setminus C) = A$ is similarly cryptic (and false), and why does it follow from these that $A = B$ ??

Why does it follow from $A \setminus C = B \setminus C$ that $B \cap C = \emptyset$ ? One can easily come up with counterexamples for this implication.

To see one implication: suppose $(A \setminus B) \cup (A \setminus C)=B$.

We want to show $A = B$. Suppose $x \in A$. Then, if $x \notin B$ were true, $x$ would be in $A \setminus B$, so in $(A\setminus B)\cup (A\setminus C)=B$ and so $x \in B$, and this is a contradiction ($x \notin B$ implies $X \in B$). So $x \in B$ must hold and this shows that $A \subseteq B$. On the other hand, suppose $x \in B = (A\setminus B)\cup (A\setminus C)$. Then $x \notin (A \setminus B)$, so $x \in A \setminus C$, so in particular $x \in A$. This shows that also $B \subseteq A$ and hence $A = B$ from the two inclusions.

We also want to show $B \cap C = \emptyset$. If $x \in B \cap C$, then $x \in B = (A\setminus B)\cup (A\setminus C)$. As $x \in C$, we know that $x \notin A \setminus C$. So it must be the case that $x \in A \setminus B$, but this cannot be as $x \in B$. So such an $x$ cannot exist, and the intersection is empty.

The reverse implciation is similar.

  • $\begingroup$ So the entire statement is false? $\endgroup$ – Cherry_Developer Nov 10 '15 at 20:16
  • $\begingroup$ $A \setminus B = A$ is, yes. The statement to prove is true, I think (the bi-implication), I showed one half. The steps themselves are not. You have to start thinking interms of proving inclusions, etc. See my proof of one half, which I wrote out as using the most elementary notions. $\endgroup$ – Henno Brandsma Nov 10 '15 at 20:20
  • $\begingroup$ Yes, what you wrote out is very helpful. Can I write up the entire proof and then have you look it over? $\endgroup$ – Cherry_Developer Nov 10 '15 at 21:01
  • $\begingroup$ Would you please be able to clarify where you showed that $A = B$. I'm confused by what you meant exactly. I'm especially confused by: so x∈B, and this is a contradiction (x∉B implies X∈B). $\endgroup$ – Cherry_Developer Nov 10 '15 at 23:28

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.