Results 1 to 5 of 5

Thread: 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; Sep 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 $\displaystyle A$ and $\displaystyle P(A)$ have different cardinalities.

    Proof (by contradiction):

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

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

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

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

    Thus, we've proved that f is not onto. $\displaystyle \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"?
    $\displaystyle f : A \rightarrow B$ is onto if $\displaystyle \forall b \in B$ $\displaystyle \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
    $\displaystyle f : A \rightarrow B$ is onto if $\displaystyle \forall b \in B$ $\displaystyle \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: Dec 14th 2009, 08:17 PM
  3. Exponents power to a power
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Feb 27th 2009, 12:39 AM
  4. Replies: 6
    Last Post: May 1st 2008, 01:21 PM
  5. Replies: 10
    Last Post: Apr 18th 2008, 10:35 PM

Search Tags


/mathhelpforum @mathhelpforum