Results 1 to 7 of 7
Like Tree3Thanks
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By Plato

Math Help - Formal proof of equal cardinality

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Formal proof of equal cardinality

    Hello,

    I need to proof knowing that some two sets  A_{1} and  A_{2} have the same cardinality that sets  A_{1}^{B} and  A_{2}^{B}, which are sets of maps from some set  B to sets  A_{1} and  A_{2} respectively, also have the same cardinality.

    So here's my attempt:

    So we know that those two sets are equal, so that means that there's a bijection between them, like this:
     f:A_{1} \rightarrow A_{2}

    I have to create a bijection between  A_{1}^{B} and  A_{2}^{B} to prove that they have the same cardinality. So let F be this bijection.

     F is supposed to take a function that goes from B to A_{1} and return a function that goes from B to A_{2}.

     f_{1}:B \rightarrow A_{1} for some  b \in B equals x \in A_{1} meaning  f_{1}(b)=x.

    Let us construct a function  f2:B \rightarrow A_{2} that does this  f_{2}(b)=f(f_{1}(b))=f(x). This function takes  b from  B and returns an element in  A_{2} by assigning one to the result of  f_{1} by the bijection between sets  A_{1} and A_{2}.

    So in the end, a bijection between sets  A_{1}^{B} and  A_{2}^{B} is a function  F(f_{1})=f_{2}.

    Is this even partly correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1

    Re: Formal proof of equal cardinality

    Quote Originally Posted by MachinePL1993 View Post
    I need to proof knowing that some two sets  A_{1} and  A_{2} have the same cardinality that sets  A_{1}^{B} and  A_{2}^{B}, which are sets of maps from some set  B to sets  A_{1} and  A_{2} respectively, also have the same cardinality.
    So here's my attempt:
    So we know that those two sets are equal, so that means that there's a bijection between them, like this:
     f:A_{1} \rightarrow A_{2}
    I have to create a bijection between  A_{1}^{B} and  A_{2}^{B} to prove that they have the same cardinality. So let F be this bijection.
     F is supposed to take a function that goes from B to A_{1} and return a function that goes from B to A_{2}.  f_{1}:B \rightarrow A_{1} for some  b \in B equals x \in A_{1} meaning  f_{1}(b)=x.
    Let us construct a function  f2:B \rightarrow A_{2} that does this  f_{2}(b)=f(f_{1}(b))=f(x). This function takes  b from  B and returns an element in  A_{2} by assigning one to the result of  f_{1} by the bijection between sets  A_{1} and A_{2}.
    So in the end, a bijection between sets  A_{1}^{B} and  A_{2}^{B} is a function  F(f_{1})=f_{2}.
    Have you proved that F is a bijection?
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Formal proof of equal cardinality

    Okay, I figured out how to prove that this function is injective, but I'm at a loss when it comes to proving it's surjectivity.

    Can anyone please give me a hint?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1

    Re: Formal proof of equal cardinality

    Quote Originally Posted by MachinePL1993 View Post
    Okay, I figured out how to prove that this function is injective, but I'm at a loss when it comes to proving it's surjectivity.
    Can anyone please give me a hint?

    I may use different notation from you.
    If \alpha\in A_1^B then F(\alpha)=f\circ \alpha\in A_2^B is that correct?

    If \gamma\in A_2^B then f^{-1}\circ\gamma \in A_1^B. Yes?

    What is F(f^{-1}\circ\gamma)=~?
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Formal proof of equal cardinality

    F(f^{-1}\circ\gamma)=~? is \gamma right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1

    Re: Formal proof of equal cardinality

    Quote Originally Posted by MachinePL1993 View Post
    F(f^{-1}\circ\gamma)=~? is \gamma right?

    Correct. So is F onto?
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Formal proof of equal cardinality

    Yes because for any member of the second set we proved that we can find a corresponding member of the first set, thereby the functions is surjective. Thank you very much
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: December 17th 2012, 03:23 PM
  2. Creating a bijection to show equal cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2012, 08:04 AM
  3. Proving Equal Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 12th 2011, 11:41 AM
  4. Formal Proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 30th 2011, 01:12 PM
  5. Formal Proof
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 12th 2008, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum