Expert: Paul Klarreich - 11/11/2008

Question
Let A and B be sets. Show, in general, that A x B(the A and the B are both under a symbol ~) are not equal  to (~over A) X (~over B). (The ~ is to be interpreted as all those elements of the universe that are not in the A or B)

Answer
Questioner:   Tonya
Category:  Advanced Math
Private:  No
 
Subject:  Proofs
Question:  Let A and B be sets. Show, in general, that A x B(the A and the B are both under a symbol ~) are not equal  to (~over A) X (~over B). (The ~ is to be interpreted as all those elements of the universe that are not in the A or B)
............................
Hi, Tonya,

Write your 'set' examples this way:

Write AB for intersection.
Write A+B for union.
Write  ~A for complement.
Write  x in A to mean x is an element of A.
Write /= to mean 'is not equal'.

Your example is:

~(A + B) = ~A ~B

I.e. the complement of a union is the intersection of the complements.  You can do this:

Let x be an element of the left side.  Now (A + B), the union, is the set of all elements that belong to AT LEAST ONE of A and B.  If x is OUTSIDE (in the complement of) this union, it must be outside A and outside B.  

Therefore x in ~A  and  x in ~B, so  x in ~A ~B.

............................
Wait a minute, I hear you saying -- that's not the example. It said,
show that, in general, ~(AB) /= ~A ~B

I assume you mean that it is NOT ALWAYS TRUE.  That is not the same as saying ALWAYS FALSE.  In fact, if A and B are the same set, it is true.

So all you have to do is find a simple counterexample.

Such as:
U = {1,2,3}
A = {1},   B = {2}

AB = { }
~(AB) = {1,2,3}

BUT -----------
~A = { 2,3 }
~B = { 1,3 }

~A ~B = { 3 }
----------- not the same.