# Power sets and Cartesian products.

1. Feb 14, 2014

### cgjolberg

1. The problem statement, all variables and given/known data
For every pair of sets (A,B) we have P(AxB)=P(A)xP(B)
Prove or disprove the above statement.

2. Relevant equations

3. The attempt at a solution
I have attempted solving this using A={1,2} and B={a,b}
AxB={(1,a),(1,b),(2,a),(2,b)}
P(AxB)={ø,{(1,a)},{(1,b)},{(2,a)},{(2,b)},{(1,a),(1,b)},{(1,a),(2,a)},{(1,a),(2,b)},{(1,b),(2,a)},{(1,b),(2,b)},{(2,a),(2,b)},{(1,a),(1,b),(2,a)},{(1,a),(1,b),(2,b)},{(1,a),(2,a),(2,b)},{(1,b),(2,a),(2,b)},{(1,a),(1,b),(2,a),(2,b)}}

P(A)={ø,{1},{2},{1,2}}
P(B)={ø,{a},{b},{a,b}}
P(A)xP(B)={(ø,ø),(ø,{a}),(ø,{b}),(ø,{a,b}),({1},ø),({1},{a}),({1},{b}),({1},{a,b}),({2},ø),({2},{a}),({2},{b}),({2},{a,b}),({1,2},ø),({1,2},{a}),({1,2},{b}),({1,2},{a,b})}

So from this it seems clear that they are not equal. The easiest way to state that without all of the work I just did seems to be that P(AxB) creates sets of sets, whearas P(A)xP(B) creates pairs of sets or something along those lines.
However, from several websites I have found through searching, several say these two statements are equivalent, so now I am confused.

Also, am I correct in crossing the ø through like I did in P(A)xP(B)? I am not sure if you are suppose to do it like I did or just have one ø at the beginning of the answer.
Thanks for the help!

2. Feb 14, 2014

### kduna

What you did was correct.

You can also use a combinatorial argument to disprove.

Let |A| denote the order of A.

Suppose $|A| = m$ and $|B| = n$. Then $|P(A)| = 2^m$ and $|P(B)| = 2^n$.

$|A \times B| = mn$ so $|P(A \times B)| = 2^{mn}$.

But $|P(A) \times P(B)| = 2^m*2^n = 2^{m+n}$.

So if $mn \neq m + n$ they have different sizes.

Funny enough, you pick m and n to be 2 so they have the same size. But your example is perhaps more insightful because you see that the objects in these sets are fundamentally different.