0

I know that from the other direction, the cardinality of the set of function that maps from $\{1,2,3\}$ to $\mathbb{N}$ is $\mathbb{N}\times\mathbb{N}\times\mathbb{N}=|\mathbb{N}|$, however, I don't know how should I work from the other direction.

Charlie
  • 87
  • 7

1 Answers1

1

The set of functions mapping $X\to Y$ is often denoted $Y^X$. It is known that $|Y^X| = |Y|^{|X|}$.

MPW
  • 43,638
  • I do not know this theorem. Can you show me why is that the case? – Charlie Nov 28 '20 at 01:11
  • @Charlie for the finite case, this is simply the rule of product. For each of the $|X|$ elements in $X$, you have $|Y|$ options for what it maps to. Making $|X|$ such choices you have then $|Y|\times |Y|\times \cdots \times |Y|=|Y|^{|X|}$ total outcomes. For the infinite case, some more care needs to be taken. – JMoravitz Nov 28 '20 at 01:13
  • @Charlie for this case, you should know that the number of functions from $\Bbb N$ to ${1,2}$ is in direct bijection with the power set $\mathcal{P}(\Bbb N)$. You should also know a result about the number of functions from $\Bbb N$ to $\Bbb N$. You should then be able to reason that your set lies between these as a superset of the first and as a subset of the second and reach a final conclusion. – JMoravitz Nov 28 '20 at 01:15
  • What if both $X$ and $Y$ are empty? There is exactly one mapping $\emptyset \rightarrow \emptyset$. But what is $0^0$? – shuhalo Feb 17 '24 at 10:56