0
$\begingroup$

In set theory and combinatorics, the cardinal number $n^m$ is the size of the set of functions from a set of size m into a set of size $n$.

I read this from this Wikipedia page.

I don't understand, however, why this is true. I reason with this example in which $M$ is a set of size $5$, and $N$ is a set of size $3$. For each element in set $M$, there are three functions to map the element from the set of size $5$ to an element in the set of size $3$.

By my reasoning, that means the total number of functions is just $3*5$, i.e. $3$ functions for each of the $5$ elements in the set. Why is it actually $3^5$? I saw on this thread that the number of functions from a set of size $n$ to a set of size $m$ is equivalent to "How many $m$-digit numbers can I form using the digits $1,2,...,n$ and allowing repetition?" I know how to answer that question, but I don't know why it's the same thing as finding the number of functions from the size $n$ set to the size $m$ set.

$\endgroup$
1

4 Answers 4

3
$\begingroup$

Consider a small example: the number of functions from a 2-element set $\{a,b\}$ to a 3-element set $\{1,2,3\}$. They are:

$$\begin{align} a,b\mapsto1,1\\ a,b\mapsto1,2\\ a,b\mapsto1,3\\ a,b\mapsto2,1\\ a,b\mapsto2,2\\ a,b\mapsto2,3\\ a,b\mapsto3,1\\ a,b\mapsto3,2\\ a,b\mapsto3,3 \end{align}$$

See? There are $9=3^2$, not $6=3\times 2$.

$\endgroup$
1
$\begingroup$

You can think of constructing your function by choosing the images of each element in the domain, one at a time. For the first element of the set, you have n choices (any element in the target space); for the second element of the set, you again have n choices, and so on. Therefore the number of ways to construct a function from the first set to the second is just $n\cdots n =n^m$.

$\endgroup$
1
$\begingroup$

Here's an attempt to explain it understandably through induction:

Suppose we want to make a function from $\{a,b,c\}$ to $\{1,2,3,4,5\}$. How many choices do we have?

Well, we have to start by choosing some $f(a)$. We have $5$ choices for that. We also have $5$ choices for $f(b)$. However, we can make this choice independently of $f(a)$, which means that for every function on $\{a\}$, there are $5$ choices for $f(b)$. So, there are $5\times 5=25$ choices for $f$ on $\{a,b\}$.

Now what about $\{a,b,c\}$? Well, there are $25$ choices for $f$ on $\{a,b\}$, and each such choice can be extended by choosing one of $5$ options for $f(c)$. So, there are $25\times5=5\times5\times5=5^3$ options for a function on $\{a,b,c\}$.

Hope that explanation helps a little bit.

$\endgroup$
1
$\begingroup$

An $m$-digit number $x_1 x_2 ... x_m$ where each $x_i$ can be a digit from the set $\{1,...,n\}$ is basically the same as a function from $M:=\{1,2,...,m\}$ to $N:=\{1,2,...,n\}$. Let $x:M\to N$ be such a map. Then you can construct the number $x(1)x(2)...x(m)$. If on the other hand you have a number $x_1 x_2 ... x_m$, then $x(i)=x_i$ yields a function from $M$ to $N$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .