Expert: Paul Klarreich - 3/20/2009

Question
QUESTION: Hi, this problem is quite difficult to understand, but I will do my best.

If (A intersect complement B) union (complement A intersect B)=A, then B={}

I started with proof by contradiction so

Assume the above hypothesis, but also assume that B does not equal the empty set.  That means there is some x in B.  What do I do next?

Thank you very much!!

ANSWER: Questioner:   Amanda
Category:  Advanced Math
Private:  No
 
Subject:  Set Relationship
Question:  Hi, this problem is quite difficult to understand, but I will do my best.

If (A intersect complement B) union (complement A intersect B)=A, then B={}

I started with proof by contradiction so

Assume the above hypothesis, but also assume that B does not equal the empty set.  That means there is some x in B.  What do I do next?

Thank you very much!!
.........................................
Notation I will use (I hate a lot of typing)

(A intersect B) is written AB.

(A union B) is written A + B.

complement B is written  B'.

x is an element of A is written      x isin A.  (Yuk!)  Sorry.
x is not an element of A is written  x notin A.
.........................................
OK, let's get to work. You have to prove:

If  (AB') + (A'B) = A  then B = {}  (empty set, yes, that's the way to write it.)

You could do it with a Venn diagram.(See attached.)

In the picture, the A and B are the circles, and one,two,three, four are individual regions, perhaps with mucho points in them, perhaps not.


So if x in A, it could be in two or in three, and it could be in B, but it could not be in A'.

If x in two, it could be in A or it could be in B', but it could not be in one,three, or four.

I.e. the numbered regions are exclusive of each other.
...........................
Here we go with computing the left side:

A = {two,three},  B = {three,four}

B' = {one,two}
AB' = {two}

A' = {one,four}
A'B = {four}

AB' + A'B = {two} + {four} = {two,four}

But A = {two,three}, so

{two,four} = {two,three}

So what does that say?

If two sets are equal, they must contain exactly the same elements.

Suppose x in three.  Then it is not in two or four, so it is not in the left side set.  Therefore it is not in the right hand set.  Therefore set three is empty.

Suppose x in four.  Then it is not in two or three, so it is not in the right side set.  Therefore it is not in the left hand set.  Therefore set four is empty.

Therefore {three,four} is empty.  But {three,four} is B.

-------------------------------------------------
Don't like the diagram?  You say you're not satisfied?  Tell you what I'm going to do.  [Ask your grandpa about that -- he'll remember.]

Here is a proof without the picture.

Prove:  AB' + A'B = A

I will show that the assumption that  x in B leads to a contradiction.  We shall see that if x isin A, then it is NOT in the left side, and if x notin A, then it IS in the left side, but not the right.  Therefore there can be no such x, so B is empty.

Ready?

Suppose x in B.  Then either

Case 1:  x notin A.  (that means  x isin A')

  Then x isin A' and  x isin B, so x isin A'B.

  Then x isin the left side. (Union, remember?)

  But x notin A, so it's not in the right side.

  THAT IS NOT GOOD.


Case 2: x isin A.

   x notin B' means  x notin AB'
   x isin A means x notin A', means x notin A'B.
  (x notin AB') and  (x notin A'B) means x notin their union.
  And that means x notin left side.
  But x isin A, the right side.

  THAT IS ALSO NOT GOOD.

so the assumption  x isin B leads to no good. (i.e. a contradiction.)

Whew!


---------- FOLLOW-UP ----------

QUESTION: Thank you so much for the help!  I have another question about this problem, only this time it is reverse:

If B={}, then (AB')+(A'B)=A.  How can I prove this without a Venn diagram?

Answer
QUESTION: Thank you so much for the help!  I have another question about this problem, only this time it is reverse:

>> the word is CONVERSE.  (Not just a brand of sneakers.)

Notation (yes, more of that):

U = the universe.  Properties of the universe (besides being 14 billion years old):

X + U = U
XU = X
U' = {}

Also, of course, properties of the empty set are:

{}' = U
X{} = {}
X + {} = X
.............................
Now to your proof:

If B={}, then (AB')+(A'B)=A.  How can I prove this without a Venn diagram?


If  B = {}, then A'B = A'{} = {}

So (AB')+(A'B) = (AB')+{} = AB'.

But AB' = A{}' = AU = A  

Finito.