# Thread: Formal proof of equal cardinality

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

2. ## Re: Formal proof of equal cardinality

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

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 $\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)=~?$

5. ## Re: Formal proof of equal cardinality

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

6. ## Re: Formal proof of equal cardinality

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

Correct. So is $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