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 \}$
Best Answer
$$(A \cup B) \cap \overline{(A \cap B)} = (A \cap \overline{B}) \cup (\overline{A} \cap B)\tag{1}$$
Yes, correct, but you should keep parentheses: $ (A \cup B) \cap \overline{(A \cap B)} = (A \cup B) \cap (\overline{A} \cup \overline{B})$
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)$ ....