Results 1 to 5 of 5

Math Help - If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

  1. #1
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

    Set theory question.


    I need to prove that if f:A\to B is onto B, then P(B)\leq P(A). And  |B|\leq |A| under axiom of choice.


    Thank You!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

    You mean |P(B)| <= |P(A)| ?
    Last edited by Link; December 6th 2012 at 04:19 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,910
    Thanks
    1760
    Awards
    1

    Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

    Quote Originally Posted by Also sprach Zarathustra View Post
    Set theory question.
    I need to prove that if f:A\to B is onto B, then |P(B)|\leq |P(A)|. And  |B|\leq |A| under axiom of choice.

    The way one proves this depends on the way \le is defined.

    This might help. There must be an injection g:B\to A.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

    We have a surjection f from A to B. We need an injection g from P(b) to P(A).

    Let b in P(B), we define g like this : g(b)=f^-1(b). g is an injection, proof by contradiction :
    let b1 and b2 two subsets of B such that b1=/=b2 and g(b1)=g(b2)=S (S is some subset of A).
    Let c in b1\b2 (c is in b1 and not in b2) let x=f^-1(c). x exists because f is surjective. we know that x is in S and f(x)=c.
    But c=f(x) belongs to b2 also (because the image of an element of S is in b1 and in b2). This is a contradiction because c is in b1/b2.

    so we have an injection from P(b) to P(A) this means by definition |P(b)<=|P(A)|
    Last edited by Link; December 6th 2012 at 05:58 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,910
    Thanks
    1760
    Awards
    1

    Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

    Quote Originally Posted by Also sprach Zarathustra View Post
    Set theory question.
    I need to prove that if f:A\to B is onto B, then  |B|\leq |A| under axiom of choice.

    f is an surjection from A\to B.

    Let \mathcal{C}=\left\{f^{-1}(\{b\}):b\in B\right\}. Now \mathcal{C} is a partition of the set A.

    There is a choice function, (why?) on \mathcal{C} so that a_b\in  f^{-1}(\{b\}).

    Define g:B\to A by b\mapsto a_b.

    Show that g is an injection.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum