# Thread: Formal proof of equal cardinality

1. ## 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?

2. ## Re: Formal proof of equal cardinality

Originally Posted by MachinePL1993
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?

3. ## 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?

4. ## Re: Formal proof of equal cardinality

Originally Posted by MachinePL1993
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)=~?$

5. ## Re: Formal proof of equal cardinality

$\displaystyle F(f^{-1}\circ\gamma)=~?$ is $\displaystyle \gamma$ right?

6. ## Re: Formal proof of equal cardinality

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

Correct. So is $\displaystyle F$ onto?

7. ## 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