5
$\begingroup$

Prove or disprove $(A + B) \cap C = (A \cap C) +(B \cap C)$

I want to disprove this statement.

$(A+B)$ is the symmetric difference and has the form of $(A \cup B) \backslash (A \cap B)$

I am starting on the left which is $(A + B) \cap C $

If I take the complement definition of $(A+B)$, I would have

$[x: x \in A \cup B \land x \notin A \cap B]$

So I am left with $A \cup B$

now I'm going to use the distributive law $\cap C$ on $A \cup B$

The result would be $(A \cup C) \cap (B \cup C)$

$(A \cup C) \cap (B \cup C) \neq (A \cap C) +(B \cap C)$

because in the middle we have $\cap$ on the left and $+$ on the right... but that's wrong.

What if I let $ C = \emptyset$ ?

Then I would have $(A +B) \cap \emptyset = (A \cap \emptyset) +(B \cap \emptyset )$

I'm going to start at the right this time .. because I've seen some properties already and it's similar to what I did weeks before

$= (A \cap \emptyset) +(B \cap \emptyset )$

Universal Bound Law $A \cap \emptyset = \emptyset$

$= (\emptyset) +(\emptyset )$

If I take the symmetric difference of $= (\emptyset) +(\emptyset )$ it's an empty set.

hmmm now that I think about it...if I approach it this way it looks like I'm proving that they are indeed equal.

$(A + B) \cap \emptyset$ [ distributive law]

$(A \cap \emptyset ) + (B \cap \emptyset)$ [universe bound laws]

$( \emptyset ) + ( \emptyset)$ [symmetric difference]

that's an empty set...

I want to disprove this statement... but how?

edit: another attempt at this problem using set intersection definition

Prove or disprove $(A + B) \cap C = (A \cap C) +(B \cap C)$

Suppose $x \in (A +B) \cap C$, then $[x \in (A +B)] \cap C$ and we have $(x \in A + x \in B) \cap C$

For $x \in A$, by set intersection definition, we have $x \in A \land C$ and $x \in B \land C$

[maybe for $x \in C$, by set intersection definition, we have $x \in A \land C$ and $x \in B \land C$ since C is being distributed, not A. ]

By symmetric difference definition, we have $x \in A \land C + x \in B \land C$

Therefore, $(A \cap C) +(B \cap C)$

Is this correct?!

$\endgroup$
  • $\begingroup$ You can just prove it the same way you would prove $(a \text{ xor } b) \land c \equiv (a \text{ xor } b) \land (a \text{ xor } c)$. $\endgroup$ – DanielV Mar 3 '14 at 10:00
  • $\begingroup$ how though? I mean we are dealing with $+$ here... I don't think just flat out use the distributive law will work on this...and I want to disprove it. $\endgroup$ – usukidoll Mar 3 '14 at 10:08
  • $\begingroup$ the only way I could think this is to prove the distributive law with that problem. $\endgroup$ – usukidoll Mar 3 '14 at 10:19
  • 1
    $\begingroup$ The most direct way to prove the statement is to look at the 8 cases of $x \in A$, $x \in B$, and $x \in C$, and evaluate the expressions and show equivalence in all 8 cases. It isn't glorious, but it's very reliable. $\endgroup$ – DanielV Mar 3 '14 at 10:34
  • $\begingroup$ so I gotta do one for $x \in A$, $x \in B$, and $x \in C$?! balh what if I want to disprove it? That's my original intent. $\endgroup$ – usukidoll Mar 3 '14 at 10:38
1
$\begingroup$

There is a duality between sets and functions. $\cap$ becomes $\land$ , $\cup$ becomes $\lor$, $+$ becomes $\text{ xor }$, $\text{universe minus set}$ becomes $\lnot$. If you wish to be pedantic, you can convert everything manually:

$$x \in (A + B) \cap C$$ $$x \in (A + B) \lor x \in C$$ $$(x \in A \text{ xor } x \in B) \lor x \in C$$

The above statements are equivalences, the same for the rhs:

$$x \in (A \cap C) + (B \cap C)$$ $$...$$ $$(x \in A \land x \in C) \text{ xor } (x \in B \land x \in C)$$

Replace $x \in A$ with $a$, same for $B$ and $C$.

$$(a \text { xor } b ) \land c \equiv (a \land c) \text{ xor } (b \land c)$$

That's how they come up with these set problems; just look at the dual Boolean expression.

$\endgroup$
  • $\begingroup$ So I do the same thing except I will have $x \in B$ so that would mean that the place for $x \in B$ would be switched like $x \in (B+A)$?! or $x \in (B+C) \cap A$??? $\endgroup$ – usukidoll Mar 3 '14 at 11:49
0
$\begingroup$

Use the answer at #697330 but with "$x \in A+B \iff (x \in A \cup B) \wedge \neg (x \in A \cap B) $. The rest of the structure is the same and you'll do a little more propositional calculus, but you'll follow the same path.

$\endgroup$
  • $\begingroup$ what does that bring though?! if I use complement definition on $A+B$ I will only have $A \cup B$ which means there are elements in A or B. $\endgroup$ – usukidoll Mar 3 '14 at 9:10

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.