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

Thread: 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 $\displaystyle A_{1}$ and $\displaystyle A_{2}$ have the same cardinality that sets $\displaystyle A_{1}^{B}$ and $\displaystyle A_{2}^{B}$, which are sets of maps from some set $\displaystyle B$ to sets $\displaystyle A_{1}$ and $\displaystyle 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:
    $\displaystyle f:A_{1} \rightarrow A_{2}$

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

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

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

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

    So in the end, a bijection between sets $\displaystyle A_{1}^{B}$ and $\displaystyle A_{2}^{B}$ is a function $\displaystyle 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
    21,958
    Thanks
    2921
    Awards
    1

    Re: Formal proof of equal cardinality

    Quote Originally Posted by MachinePL1993 View Post
    I need to proof knowing that some two sets $\displaystyle A_{1}$ and $\displaystyle A_{2}$ have the same cardinality that sets $\displaystyle A_{1}^{B}$ and $\displaystyle A_{2}^{B}$, which are sets of maps from some set $\displaystyle B$ to sets $\displaystyle A_{1}$ and $\displaystyle 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:
    $\displaystyle f:A_{1} \rightarrow A_{2}$
    I have to create a bijection between $\displaystyle A_{1}^{B}$ and $\displaystyle A_{2}^{B}$ to prove that they have the same cardinality. So let $\displaystyle F$ be this bijection.
    $\displaystyle F$ is supposed to take a function that goes from $\displaystyle B$ to $\displaystyle A_{1}$ and return a function that goes from $\displaystyle B$ to $\displaystyle A_{2}$. $\displaystyle f_{1}:B \rightarrow A_{1} $ for some $\displaystyle b \in B$ equals $\displaystyle x \in A_{1}$ meaning $\displaystyle f_{1}(b)=x$.
    Let us construct a function $\displaystyle f2:B \rightarrow A_{2} $ that does this $\displaystyle f_{2}(b)=f(f_{1}(b))=f(x)$. This function takes $\displaystyle b$ from $\displaystyle B $ and returns an element in $\displaystyle A_{2}$ by assigning one to the result of $\displaystyle f_{1} $ by the bijection between sets $\displaystyle A_{1}$ and $\displaystyle A_{2}$.
    So in the end, a bijection between sets $\displaystyle A_{1}^{B}$ and $\displaystyle A_{2}^{B}$ is a function $\displaystyle F(f_{1})=f_{2}$.
    Have you proved that$\displaystyle 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
    21,958
    Thanks
    2921
    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 $\displaystyle \alpha\in A_1^B$ then $\displaystyle F(\alpha)=f\circ \alpha\in A_2^B$ is that correct?

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

    What is $\displaystyle 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

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

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,958
    Thanks
    2921
    Awards
    1

    Re: Formal proof of equal cardinality

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

    Correct. So is $\displaystyle 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: Dec 17th 2012, 03:23 PM
  2. Creating a bijection to show equal cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 15th 2012, 08:04 AM
  3. Proving Equal Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 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: Nov 12th 2008, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum