5

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?!

usukidoll
  • 2,074
  • 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)$. – DanielV Mar 03 '14 at 10:00
  • 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. – usukidoll Mar 03 '14 at 10:08
  • the only way I could think this is to prove the distributive law with that problem. – usukidoll Mar 03 '14 at 10:19
  • 1
    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. – DanielV Mar 03 '14 at 10:34
  • 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. – usukidoll Mar 03 '14 at 10:38
  • Each $\in$ has 2 cases (true or false), total you have have $2^3$ cases. As far as how to disprove something that is true, try to very subtly include a paradox or a misuse of logical inference, you can prove anything that way. – DanielV Mar 03 '14 at 10:55
  • oh wow forget proving that omg...... too many cases. What about if I disprove by letting C be the empty set? would that work? – usukidoll Mar 03 '14 at 11:46

2 Answers2

1

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.

DanielV
  • 23,556
  • 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$??? – usukidoll Mar 03 '14 at 11:49
0

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.

Community
  • 1
Eric Towers
  • 67,037
  • 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. – usukidoll Mar 03 '14 at 09:10