Results 1 to 5 of 5

Math Help - Power Set

  1. #1
    Junior Member
    Joined
    Sep 2007
    Posts
    46

    Power Set

    I have to prove that given any set, there's no function f : A -> P(A), where P(A) is the power set of A, that is onto.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by seerTneerGevoLI View Post
    I have to prove that given any set, there's no function f : A -> P(A), where P(A) is the power set of A, that is onto.
    well, if the set A has n elements, then P(A) will have 2^n elements. therefore, |P(A)| will always be larger than A, and therefore the function f:A -> P(A) cannot be injective and hence cannot be onto. that's the gist of it. write that more formally and it should be fine

    EDIT: wait, am i mixing up "onto" with "bijective"?
    Last edited by Jhevon; September 12th 2007 at 05:50 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Quote Originally Posted by seerTneerGevoLI View Post
    I have to prove that given any set, there's no function f : A -> P(A), where P(A) is the power set of A, that is onto.
    Ah, Cantor's Theorem.

    First note that A and P(A) have different cardinalities.

    Proof (by contradiction):

    Suppose f : A \rightarrow P(A) is onto.
    We want to find B \in P(A) that is not in the image of A.

    Define B = {a \in A \ni a \notin f(a)}
    Since f is onto, \exists a_0 \in A \ni f(a_0) = B.

    Case 1: If a_0 \in B, then by definition, a_0 \in f(a_0) = B
    This is a contradiction.

    Case 2: If a_0 \notin B then a_0 \notin B = f(a_0) and so by definition of B, a_0 \in B
    This is a contradiction.

    Thus, we've proved that f is not onto. \square
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Quote Originally Posted by Jhevon View Post
    well, if the set A has n elements, then P(A) will have 2^n elements. therefore, |P(A)| will always be larger than A, and therefore the function f:A -> P(A) cannot be injective and hence cannot be onto. that's the gist of it. write that more formally and it should be fine

    EDIT: wait, am i mixing up "onto" with "bijective"?
    f : A \rightarrow B is onto if \forall b \in B \exists a \in A \ni f(a) = b
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by AfterShock View Post
    f : A \rightarrow B is onto if \forall b \in B \exists a \in A \ni f(a) = b
    yes, i remember now. it's all coming back to me. thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. power(n)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 21st 2010, 04:40 PM
  2. Power set of N
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 14th 2009, 08:17 PM
  3. Exponents power to a power
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 27th 2009, 12:39 AM
  4. Replies: 6
    Last Post: May 1st 2008, 01:21 PM
  5. Replies: 10
    Last Post: April 18th 2008, 10:35 PM

Search Tags


/mathhelpforum @mathhelpforum