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)$ ....

  • $\begingroup$ Your welcome, franklin. Glad to help! $\endgroup$ – amWhy Dec 29 '12 at 1:14

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.


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.


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$

So x is in B and not A or in A but not B.

so x is in one of them but not both.


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.