# how do you prove this set problem?

I'm trying to teach myself set-theory. I have been unable to prove algebraically that:

$(A \cup B) \cap \overline{(A \cap B)} = (A \cap \overline{B}) \cup (\overline{A} \cap B)$

I know it's elementary but I just want to see an example. (The book doesn't provide one.)

Correct me if I'm wrong...the first step is to use De Morgan's law to expand the left side. i.e.

$(A \cup B) \cap \overline{(A \cap B)} = (A \cup B) \cap \overline{A} \cup \overline{B}$

$(A \cup B) \cap \overline{(A \cap B)} = A \cup (B \cap \overline{A}) \cup \overline{B}$, by associative property.

$(A \cup B) \cap \overline{(A \cap B)} = (A \cup \overline{A}) \cap (B \cup \overline{B} )$, by commutative property.

after that I don't know what to do.

I don't know whether I should rewrite these or if different notation would help. i.e. should I expand both sides to use the notations/definition of set-union? i.e. $A \cup B = \{x \mid x \in A \lor x \in B \}$

-

$$(A \cup B) \cap \overline{(A \cap B)} = (A \cap \overline{B}) \cup (\overline{A} \cap B)\tag{1}$$

Step (1) $(A \cup B) \cap \overline{(A \cap B)} = (A \cup B) \cap \overline{A} \cup \overline{B}$

Yes, correct, but you should keep parentheses: $(A \cup B) \cap \overline{(A \cap B)} = (A \cup B) \cap (\overline{A} \cup \overline{B})$

Step (2) Not correct: $(A \cup B) \cap \overline{(A \cap B)}$ = $A \cup (B \cap \overline{A}) \cup \overline{B}$, by associative property.

No: the associative property (like the commutative property) applies to a chain of unions, or a chain of intersections, but not a mixed chains of unions and intersections. This is why parentheses in the first step are needed. You need to use distribution:

$(A \cup B) \cap \overline{(A \cap B)}$ = $(A \cup B) \cap (\overline{A} \cup \overline{B}) = [(A\cup B) \cap \overline{A}] \cup [(A \cup B) \cap \overline{B}]$

Can you take it from here? You can use distributivity again...then use that fact that $A \cap \overline{A} = \varnothing$. Likewise for $B\cap \overline{B} = \varnothing$. Simplify.

Another approach is to unpack what proving your equality $(1)$ requires:

In general, we prove that for two sets $P, Q$, $$P = Q \iff P \subseteq Q \text{ AND}\;\;Q\subseteq P$$

For your equality $(1)$, that means you can prove the equality by proving: $$[(A \cup B) \cap \overline{(A \cap B)}] \subseteq [(A \cap \overline{B}) \cup (\overline{A} \cap B)]\tag{2}$$

and by proving $$[(A \cap \overline{B}) \cup (\overline{A} \cap B)] \subseteq [(A \cup B) \cap \overline{(A \cap B)}]\tag{3}$$

Unpack what this means in terms of "chasing elements", for which I'll give you a start:

$(2)$ If $x \in [(A \cup B)\cap \overline{(A \cap B)}]$ then $x \in (A\cup B)$ AND $x \notin (A \cap B)$, which means $(x \in A$ OR $x \in B)$ AND $(x \notin A$ OR $x \notin B)$...

$(3)$ If $x \in [(A\cap \overline{B})\cup (\overline{A} \cap B)]$, then ...$(x \in A \cap \overline{B})$ OR $(x \in \overline{A} \cap B)$ ....

-
thanks that was perfect. –  franklin Dec 29 '12 at 1:09
Your welcome, franklin. Glad to help! –  amWhy Dec 29 '12 at 1:14

Good first effort, but you don't have associativity and commutativity when dealing with the operations $\cup$ and $\cap$, so parentheses are super important.

It looks like you are missing what it means for two sets, call them $X$ and $Y$, to be equal. The definition is pretty simple: $X = Y$ means that any element $x \in X$ is also in $Y$, and every element $y \in Y$ is also contained in $X$.

Formally, $X = Y$ $\iff$ $X \subseteq Y$ and $Y \subseteq X$.

So you want to break this into two problems, showing that each is a subset of the other. So start out with "Let $x \in (A \cup B) \cap \overline{(A \cap B)}$..." and go from there. Let me know if you need more.

-

Your first step is almost correct: you dropped the parentheses. Thus, you should have \begin{align}(A\cup B)\cap\overline{(A\cap B)}&=(A\cup B)\cap(\overline{A}\cup\overline{B})\\ &= \big[(A\cup B)\cap\overline{A}\big]\cup\big[(A\cup B)\cap\overline{B}\big]\\ &= (B\cap\overline{A})\cup(A\cap\overline{B}).\end{align}

As an example, we can take intervals on the real line, say $A=[0,2]$ and $B=[1,3]$. As an exercise, you can try to work it out to verify the identity as an example.

-

For future reference, the solution:

prove: $\ (A \cup B) \cap \overline{(A \cap B)} = (\overline{A} \cap B) \cup (\overline{B} \cap A)$

I will manipulate the left side only:

$\ (A \cup B) \cap (\overline{A} \cup \overline{B})$, use De Morgan's law

= $\ (( A \cup B) \cap \overline{A} ) \cup ((A \cup B) \cap \overline{B})$ , distribution

= $\ ( (\overline{A} \cap B) \cup (\overline{A} \cap A)) \cup ( (\overline{B} \cap B) \cup (\overline{B} \cap A))$ , distribution

remember that $\ \overline{A} \cap A = \emptyset$

= $\ (\overline{A} \cap B) \cup (\overline{B} \cap A)$

-
$x \in A \wedge \not\in B \vee \not\in A \wedge \in B$