1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Power sets and Cartesian products.

  1. Feb 14, 2014 #1
    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. jcsd
  3. Feb 14, 2014 #2
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted