The function space from $n$ to $m$ and the exponent $m^n$ are equinumerous (proof)

Question

Can someone provide a tip with creating the bijection for the titular problem? Any tip is helpful!

Update: $n=\{ 0,\ldots,n-1 \}$, $m=\{ 0,\ldots,m-1 \}$, and $ m^n=\{0,\ldots,m^n-1\} $. In other words, natural numbers (in set theory) are sets consisting of its predecessors.

Answer 1

I've never worked this out on my own. It's about time I did.

Recall the definition of exponentiation. Exponentiation is the unique function from $\Bbb N\times \Bbb N$ such that

• $m^0=1$ for all $m\in\Bbb N$
• $m^{n+1}=m\cdot m^n$ for all $m,n\in\Bbb N$

We will denote the set of function from $X$ to $Y$ by $X\rightarrow Y$. Now we show that the cardinality of $n\rightarrow m$ is $m^n$. We will proceed by induction, but we need two lemmas:

Lemma 1. For finite sets $X$ and $Y$ with cardinality $n$ and $m$ respectively, we have that the cardinality of $X\times Y$ is $n\cdot m$

Lemma 2. For disjoint sets $X$ and $Y$, we have that $(X\cup Y)\rightarrow Z\simeq (X\rightarrow Z)\times(Y\rightarrow Z)$

With these two lemmas we can proceed.

Base case: For any set $X$, we have that there is a unique function from $\varnothing$ to $X$. Thus for any finite ordinal $m$, we have that the cardinality of $0\rightarrow m$ is $1=m^0$.

Induction: Suppose for any finite set $X$ with cardinality $k$ less than or equal to $n$, we have that the cardinality of $X\rightarrow m$ is $m^k$. Now let $Y$ be a set of cardinality $n+1$. Let $Y=\{x_1, \ldots, x_{n+1}\}=\{x_1,\ldots, x_n\}\cup\{x_{n+1}\}$. By Lemma 2, we have that $Y\rightarrow m\simeq \left(\{x_1,\ldots, x_n\}\rightarrow m\right)\times\left(\{x_{n+1}\}\rightarrow m\right)$. And by induction and our first lemma, we know the cardinality of this latter set is $m^n\cdot m=m^{n+1}$.

Thus by induction we have for any two set $X$ and $Y$ of cardinality $n$ and $m$ respectively, we have that the cardinality of $X\rightarrow Y$ is $m^n$.

I'll leave the lemmas for you to prove. ;)