Results 1 to 9 of 9
Like Tree3Thanks
  • 1 Post By Plato
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Proof regarding power sets?

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    Proof regarding power sets?

    Let A and B be sets. Prove that A ~ B implies that P(A) ~ P(B), where P(A): power set of A and P(B): power set of B.

    I'm not sure how to approach this problem. My thoughts are to try to construct a bijective function g: P(A) -> P(B) and then use the fact A~B to help show this is a bijection. But I am not sure how to define g.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1

    Re: Proof regarding power sets?

    Quote Originally Posted by gridvvk View Post
    Let A and B be sets. Prove that A ~ B implies that P(A) ~ P(B), where P(A): power set of A and P(B): power set of B.

    There are multiple ways this has been done over many years.
    You need the Schroder-Bernstein_theorem

    If A is a set, then 2^A is the set of all functions A\to\{0,1\}.

    Then using the Characteristic function you can show that \mathcal{P}(A) \sim {2^A}.

    Working with functions, we can show that A \sim B\, \Rightarrow \,{2^A} \sim {2^B}.

    Now there is a huge amount of work to be done there. This is not an easy problem.
    Last edited by Plato; May 9th 2013 at 02:51 PM.
    Thanks from gridvvk
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    Re: Proof regarding power sets?

    Quote Originally Posted by Plato View Post
    There are multiple ways this has been done over many years.
    You need the Schroder-Bernstein_theorem

    If A is a set, then 2^A is the set of all functions A\to\{0,1\}.

    Then using the Characteristic function you can show that \mathcal{P}(A) \sim {2^A}.

    Working with functions, we can show that A \sim B\, \Rightarrow \,{2^A} \sim {2^B}.

    Now there is a huge amount of work to be done there. This is not an easy problem.
    I think I can take for granted (or prove separately) that if A and B are finite, and if |A| = |B| = n. Then |P(A)| = |P(B)| = 2^n; however, I wasn't sure if the same idea would hold if A and B were infinite sets. Does using the characteristic function take care of this problem?
    Last edited by gridvvk; May 9th 2013 at 03:02 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Proof regarding power sets?

    Why isn't it easy to define g(X) = {h(x) | x ∈ X} for X ⊆ A? A proof that g is a bijection seems straightforward.
    Last edited by emakarov; May 9th 2013 at 03:23 PM. Reason: Changed the name of bijection between A and B to h.
    Thanks from HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1

    Re: Proof regarding power sets?

    Quote Originally Posted by gridvvk View Post
    I think I can take for granted (or prove separately) that if A and B are finite, and if |A| = |B| = n. Then |P(A)| = |P(B)| = 2^n; however, I wasn't sure if the same idea would hold if A and B were infinite sets. Does using the characteristic function take care of this problem?
    You said absolutely nothing about these being finite sets..

    All proof about finite sets are trivial.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    Re: Proof regarding power sets?

    Quote Originally Posted by emakarov View Post
    Why isn't it easy to define g(X) = {g(x) | x ∈ X} for X ⊆ A? A proof that g is a bijection seems straightforward.
    Wouldn't we need to use a different letter for a different function that goes from A to B? Like h: A -> B then g(X) = {h(x) | x ∈ X}? Then just show g is injective and surjective?

    Quote Originally Posted by Plato View Post
    You said absolutely nothing about these being finite sets..


    All proof about finite sets are trivial.
    A and B aren't necessarily finite. You were correct in your interpretation of the problem. Based on what you said working with functions probably doesn't lead to the problems I was thinking.
    Last edited by gridvvk; May 9th 2013 at 03:17 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Proof regarding power sets?

    Quote Originally Posted by gridvvk View Post
    Wouldn't we need to use a different letter for a different function that goes from A to B? Like h: A -> B then g(X) = {h(x) | x ∈ X}?
    You are right; sorry.

    Quote Originally Posted by gridvvk View Post
    Then just show g is injective and surjective?
    Yes.
    Thanks from gridvvk
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Proof regarding power sets?

    Quote Originally Posted by Plato View Post
    You said absolutely nothing about these being finite sets..

    All proof about finite sets are trivial.
    Yes, that was his point. gridvvk was saying that ifA and B were finite it would be easy but he didn't think he could use that method for infinite sets.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Proof regarding power sets?

    But emakarov has the right approach. If A and B have the same cardinality, there exist a bijection, h, from A to B. Given X a subset of A, let g(A) be the set {h(x)| where x is in X}.
    Show that g is a bijection.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of Union of Power Sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 24th 2010, 10:26 PM
  2. proof involving power sets, and intersection
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 12th 2010, 02:29 PM
  3. [SOLVED] Proof involing power sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 12:52 PM
  4. Power Sets Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 20th 2007, 12:41 PM
  5. inductive proof of size of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 14th 2007, 11:01 AM

Search Tags


/mathhelpforum @mathhelpforum