How many functions are there from a set with $n$ elements to another with $m$ elements?

The answer is $m^n$ but this doesn't seem to account for the fact that an element might not have an image by that function, right?

For each element of the domain of the function, there are $m+1$ ways of it being "mapped"; the $1$ accounts for it not being mapped. So shouldn't the result be $(m+1)^n$?


Functions, by definition, have a value for each element in their domain. They can't "not be mapped". If you allow elements to not be mapped, what you have is not a function, but a partial function.

You may have seen some examples of partial functions that weren't explicitly called so, though. Like the partial function $f$ from $\Bbb R$ to $\Bbb R$ given by $f(x) = \frac1x$, or other rational functions. These are often called "functions" throughout school, and proper care to the definition of a function and restricting the domain appropriately is often not taken until late high school or university.

  • $\begingroup$ Aha, thank you! $\endgroup$ – Luyw Apr 29 '20 at 7:29
  • 1
    $\begingroup$ Just for added clarity: the nomenclature, especially through high school, may get a little fuzzy. $f(x)=\frac1x$ is sometimes a function, if we define the domain to be $\mathbb R\setminus \{0\}$, and in fact, I think that's how most students are first introduced to it. It is only a partial function if you map from $\mathbb R$. $\endgroup$ – 5xum Apr 29 '20 at 7:33
  • $\begingroup$ Yes, thank you @5xum, I've understood that. :) $\endgroup$ – Luyw Apr 29 '20 at 7:35
  • $\begingroup$ @5xum True, restricting the domain of a partial function to the subset where it is defined makes it a function. But I don't think they worry too much about those specifics when the concept of function is first introduced to 13-14 year olds, at least not where I come from. I have taught it at that level a couple of times, and they are, in my opinion, not ready for that amount of abstraction. It's fine to give them a few years to get used to the intuitive notion of functions before we expect them to wrangle with the formal definition. $\endgroup$ – Arthur Apr 29 '20 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.