Cardinality of composition functions

Question

Let $X$, $Y$, $Z$, and $W$ be any nonempty sets such that $|X|=|Y|$ and $|Z|=|W|$.

I want to show that collection of all functions from $Z$ to $X$ has same cardinality with that of all functions from $W$ to $Y$.

Here is my attempt.

First, let $f:Z \rightarrow X$ and $g:W \rightarrow Y$ be such functions. Then there exist bijections from $Z$ to $f(Z)$ and from $W$ to $g(W)$ so that we have $|Z|=|f(Z)|$ and $|W|=|g(W)|$.

Then obviously, $|f(Z)|=|g(W)|$ and I am done.

This proof must be wrong. I haven’t used anything about $|X|=|Y|$. Please correct me.

Answer 1

Your proof does not show anything about the number of functions, so you haven't shown anything.

Apart from that, if $f$ is not injective, there does not need to be a bijective function from $Z$ to $f(Z)$. Think for example of the function $f:\Bbb N\to\Bbb N$ that sends $x\mapsto 0$ for all $x\in\Bbb N$, then $\Bbb N$ and $f(\Bbb N)=\{0\}$ clearly do not have a bijective function between them. Therefore your claim that $|f(Z)|=|Z|=|W|=|g(W)|$ is false.

---

What you want to show is that if we have the set $X^Z=\{f\mid f:Z\to X\}$ of all functions from $Z$ to $X$ and the set $Y^W=\{g\mid g:W\to Y\}$ of functions from $W$ to $Y$, then $|X^Z|=|Y^W|$. So for each function in $X^Z$ we need to find a unique function in $Y^W$ and vice versa.

Let $\alpha:X\to Y$ be a bijective function between $X$ and $Y$ and $\beta:W\to Z$ be a bijective function between $Z$ and $W$ (these exist because $|X|=|Y|$ and $|Z|=|W|$).

Show that:

For any arbitrary function $f:Z\to X$ in $X^Z$, the function $\alpha\circ f\circ\beta$ is a function from $W$ to $Y$.

I claim that the map $H:X^Z\to Y^W$ that sends $f\mapsto \alpha\circ f\circ\beta$ is a bijective function.

To show this, you prove:

Injectivity: if $f$ and $f'$ are two distinct functions in $X^Z$, then $H(f)=\alpha\circ f\circ\beta$ and $H(f')=\alpha\circ f'\circ\beta$ are distinct functions in $Y^W$.

Surjectivity: If $g$ is a function in $Y^W$, then there is some function $f$ in $X^Z$ such that $H(f)=g$.

Both of these facts should be not too difficult to prove, using that $\alpha$ and $\beta$ are bijective functions.

---

Note that you don't need the assumption that $X$, $Y$, $Z$ or $W$ have to be nonempty: this fact holds for any sets $X$, $Y$, $Z$ and $W$.

This is very useful to know, since cardinal exponentiation is defined to be the size of the set of functions. That is, if $\kappa$ and $\lambda$ are cardinals, then $\kappa^\lambda$ is the cardinality of the set $B^A$ of functions from $A$ to $B$ with $|A|=\lambda$ and $|B|=\kappa$.

This definition only makes sense if $\kappa^\lambda$ is independent of which sets $A$ and $B$ you choose. This is exactly what this lemma gives us.