Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 \}$

share|improve this question
add comment

5 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
thanks that was perfect. –  franklin Dec 29 '12 at 1:09
    
Your welcome, franklin. Glad to help! –  amWhy Dec 29 '12 at 1:14
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.