Cardinality of Set of All Mappings

Theorem

Let $S$ and $T$ be sets.

The cardinality of the set of all mappings from $S$ to $T$ (that is, the total number of mappings from $S$ to $T$) is:

$\left|{T^S}\right| = \left|{T}\right| ^ {\left|{S}\right|}$

Proof for Finite Sets

Let $\left|{S}\right| = n$ and $\left|{T}\right| = m$.

• First suppose that $n = 0$, i.e. that $S = \varnothing$.

The only element of $T^\varnothing$ is the null relation $\varnothing \times T$. So $\left|{T^\varnothing}\right| = 1 = m^0$.

So the result holds for $n = 0$.

• Next, suppose that $m = 0$, i.e. that $T = \varnothing$.

From Null Mapping, the null relation $\mathcal{R} = \varnothing \subseteq S \times T$ is not a mapping unless $S = \varnothing$.

So if $n > 0$, then $\left|{\varnothing^S}\right| = 0 = 0^n$ and the result holds.

If $S = \varnothing = T$, $\left|{T^S}\right| = 1 = 0^0 = m^n$, and the result holds.

This fits in with the preferred definition of the value of $0^0$.

• Finally, suppose $m > 0$ and $n > 0$.

Let $\sigma: \N_n \to S$ and $\tau: T \to \N_n$ be bijections.

Then the mapping $\Phi: T^S \to \left({\N_m}\right)^{\left({\N_n}\right)}$ defined as:

$\forall f \in T^S: \Phi \left({f}\right) = \tau \circ f \circ \sigma$

(where $\left({\N_m}\right)^{\left({\N_n}\right)}$ is the set of all mappings from $\N_n$ to $\N_m$) is also a bijection.

So we need only consider the case where $S = \N_n$ and $T = \N_m$.

• Let $m \in \N^*$.

For each $n \in \N$, let $\Bbb T \left({n, m}\right)$ be the set of all mappings from $\N_n$ to $\N_m$. Let:

$\Bbb S = \left\{{n \in \N: \left|{\Bbb T \left({n, m}\right)}\right| = m^n}\right\}$

We have seen that $0 \in \Bbb S$.

Let $n \in \Bbb S$.

Let $\rho: \Bbb T \left({n+1, m}\right) \to \Bbb T \left({n, m}\right)$ defined by:

$\forall f \in \Bbb T \left({n+1, m}\right): \rho \left({f}\right) =$ the restriction of $f$ to $\N_n$

Given that $g \in \Bbb T \left({n, m}\right)$, and $k \in \N_m$, let $g_k: \N_{n+1} \to \N_m$ be defined by:

$\forall x \in \N_{n+1}: g_k \left({x}\right) = \begin{cases} g \left({x}\right): & x \in \N_n \\ k: & x = n \end{cases}$

Then:

$\rho^{-1} \left({\left\{{g}\right\}}\right) = \left\{{g_0, \ldots, g_{m-1}}\right\}$

Thus $\rho^{-1} \left({\left\{{g}\right\}}\right)$ has $m$ elements. So clearly:

$\left\{{\rho^{-1} \left({\left\{{g}\right\}}\right): g \in \Bbb T \left({n, m}\right)}\right\}$

is a partition of $\Bbb T \left({n+1, m}\right)$.

Hence, as $n \in \Bbb S$, the set $\Bbb T \left({n+1, m}\right)$ has $m \cdot m^n = m^{n+1}$ elements by Number of Elements in Partition.

Thus $n + 1 \in \Bbb S$.

By induction, $\Bbb S = \N$ and the proof is complete.

$\blacksquare$

Comment

The question of whether to define $0^0 = 0$ or $0^0 = 1$ keeps students awake arguing for hours.

Here's another argument, in case you're not convinced, for defining $0^0 = 1$ as opposed to $0^0 = 0$ - another result kept nice and neat.

Sources

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Chapter $\text{I}: \ \S 1$
• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 8$: Functions
• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 13$: Arithmetic
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.2$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $1.9$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 19$: Theorem $19.4$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $4.4 \ \text{(i)}$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.10$