Results 1 to 3 of 3

Math Help - Power sets and cardinality

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Power sets and cardinality

    Show that if A and B are sets with the same cardinality, then the power set of A and the power set of B have the same cardinality.

    Since A and B have the same cardinality there is a bijection between A and B.

    Therefore each element of A can be paired with each element of B.

    It then follows that every subset of A can be paired with every subset of B.

    This means that there is a bijection between the power set of A and the power set of B.

    Which proves that the power set of A has the same cardinality as the power set of B.

    Can anyone validate or show if and where this proof is wrong? I have a quiz tomorrow.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by oldguynewstudent View Post
    Show that if A and B are sets with the same cardinality, then the power set of A and the power set of B have the same cardinality.

    Since A and B have the same cardinality there is a bijection between A and B.

    Therefore each element of A can be paired with each element of B.

    It then follows that every subset of A can be paired with every subset of B.

    This means that there is a bijection between the power set of A and the power set of B.

    Which proves that the power set of A has the same cardinality as the power set of B.

    Can anyone validate or show if and where this proof is wrong? I have a quiz tomorrow.

    Thanks

    I'd be a little less verbose and more symbolic: since A, B have the same card., there's a bijection f:A\rightarrow B, and this means that if C\subset A \mbox{ then } C'=\{f(c)\slash\,\, c \in C\}\subset B

    Now just show that  C \longrightarrow C' as defined above is a bijection P(A) \longrightarrow P(B) and we're done.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by tonio View Post
    I'd be a little less verbose and more symbolic: since A, B have the same card., there's a bijection f:A\rightarrow B, and this means that if C\subset A \mbox{ then } C'=\{f(c)\slash\,\, c \in C\}\subset B

    Now just show that  C \longrightarrow C' as defined above is a bijection P(A) \longrightarrow P(B) and we're done.

    Tonio
    Thanks for the advice, just getting used to the Latex format. Here is the actual problem from the quiz. Another student came up with the basis of the proof but it wasn't finished. So any critique of the following proof is greatly appreciated.

    Given,
    |A| = |B|

    Prove that | A^n| = | B^n| where A^n implies the cartesian product.

    |A| = |B| \Rightarrow \exists f:A \toB | f is bijective

    A^n={ (a_1, a_2, ... , a_n) | a_i \epsilon A_i for i = 1,2, ... ,n}

    B = {b | b = f(a)}

    B^n= { ( b_1, b_2, ... , b_n) | b_i \epsilon B_i for i = 1,2, ... , n}

    but b_i = f( a_i)

    we can then define a function

    g( a_1, a_2, ... , a_n) = ( b_1, b_2, ... , b_n) = (f( a_1), f( a_2), ... , f( a_n))

    We need to prove g is bijective in order to show | A^n| = | B^n|

    Let g( a_1, a_2, ... , a_n) = g( c_1, c_2, ... , c_n)

    but g( a_1, a_2, ... , a_n) = ( b_1, b_2, ... , b_n)

    also g( c_1, c_2, ... , c_n) = ( b_1, b_2, ... , b_n)

    obviously ( b_1, b_2, ... , b_n) = ( b_1, b_2, ... , b_n)

    Therefore g is injective.

    To prove g is surjective:

    \forall ( b_1, b_2, ... , b_n) \epsilon B^n \exists ( a_1, a_2, ... , a_n) \epsilon A^n |

    g( a_1, a_2, ... , a_n) = ( b_1, b_2, ... , b_n)

    but ( b_1, b_2, ... , b_n) = (f( a_1), f( a_2), ... , f( a_n))

    since f is bijective this proves g is surjective.

    Therefore g is bijective which proves | A^n| = | B^n|
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 05:26 PM
  2. Cardinality of these sets!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 4th 2010, 07:27 AM
  3. Induction proof: Cardinality of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 04:59 PM
  4. Cardinality of sets Q and R
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2009, 12:30 PM
  5. Cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2007, 03:30 PM

Search Tags


/mathhelpforum @mathhelpforum