I came across a question which requires one to check if there's a bijection from the set $ \mathbb N^\mathbb N$ to another set. I've never seen a set defined this way and was wondering if this was just a typo. Could anyone clarify this for me? If this is correct, then what does the set actually mean? I mean, I can think of elements in $\mathbb R$ or in $\mathbb N$, but how do I think of elements in $\mathbb N^\mathbb N$?

  • 2
    $\begingroup$ The set of all functions from $\mathbb{N}$ to $\mathbb{N}$ $\endgroup$ – Amr Nov 11 '13 at 16:56
  • $\begingroup$ I'm sorry, but could you elaborate on that for me? How are the elements of such a set, functions? $\endgroup$ – Train Heartnet Nov 11 '13 at 16:58

The elements of $A^B$ are function of the form $f\colon B\to A$. That is function whose domain is exactly $B$ and their values are elements from $A$.

If so, $\Bbb{N^N}$ is the set of all functions from $\Bbb N$ to itself. Or the set of infinite sequences of natural numbers (as a sequence is just a function).

As a footnote remark, I should add that this set is sometimes denoted by ${}^BA$ instead of $A^B$, especially in contexts were exponentiation is used in set theory.

  • $\begingroup$ Thank you for the quick reply. May I ask why the elements are functions in the form you mentioned? Are they defined in this manner, or is there a mathematical reason behind it? $\endgroup$ – Train Heartnet Nov 11 '13 at 17:05
  • $\begingroup$ That is the definition. We do it this way because it fits with out intuition about exponentiation of natural numbers. That is, if $M$ has $m$ elements and $N$ has $n$ elements, then $N^M$ has $n^m$ elements. $\endgroup$ – Asaf Karagila Nov 11 '13 at 17:06
  • $\begingroup$ Okay, so if I understand it correctly, the set of all functions from $\mathbb N$ to $\mathbb N$ generates as many elements as the (No. of elements in $\mathbb N$) ^ (No. of elements in $\mathbb N$). Is that correct? $\endgroup$ – Train Heartnet Nov 11 '13 at 17:12
  • $\begingroup$ Yes, but that is almost trivial, since the definition of the cardinal exponentiation of $|\Bbb{N|^{|N|}}$ is exactly $|\Bbb{N^N}|$. $\endgroup$ – Asaf Karagila Nov 11 '13 at 17:14
  • $\begingroup$ Oh, I see. Thank you so much! $\endgroup$ – Train Heartnet Nov 11 '13 at 17:18

To elaborate on / illustrate Asaf's answer, and to provide some context for why this notation makes sense:

Let $A$ be the set of letters in the alphabet $\{a,b,\dots,z\}$. Let $B$ be the set of digits $\{0,\dots,9\}$. Then $A^B$, the set of functions from $B$ to $A$, is the set of all ways I could assign a letter to each digit. For example, one element of $A^B$ is the function

$$0\mapsto a$$ $$1\mapsto b$$ $$2\mapsto c$$ $$\vdots$$ $$9\mapsto j$$

Another element of $A^B$ is the function

$$0\mapsto z$$ $$1\mapsto y$$ $$2\mapsto x$$ $$\vdots$$ $$9\mapsto q$$

Yet another is the function

$$0\mapsto m$$ $$1\mapsto m$$ $$2\mapsto m$$ $$\vdots$$ $$9\mapsto m$$

Of course there are a lot of other choices. All my choices had nice patterns that made them easy to write down, but most functions are much more random-seeming in terms of which digit gets which letter. In fact, each function can be constructed by going through the digits and choosing one of the 26 letters for each of them. There are a lot of choices, so the set of functions $A^B$ is big.

Just how big?

Well, what choices have to get made to determine a function? For each of the 10 digits, you have to choose one of the $26$ letters. Thus you choose 10 times among 26 choices. Therefore the total number of functions is $26^{10}$.

Notice that $26^{10}=(\text{size of }A)^{\text{size of B}}$. This is why the notation $A^B$ is used! Because that way, we get

$$\text{size of }A^B = (\text{size of }A)^{\text{size of B}}$$

Back to your original question, $\mathbb{N}^\mathbb{N}$ refers to the set of functions from $\mathbb{N}$ to $\mathbb{N}$, just as in the above toy example. As Asaf mentioned, this can also be looked at as the set of infinite sequences of natural numbers, since a sequence like $1,1,2,5,14,\dots$ can be seen as a function that takes a position in the sequence to the entry found in that spot: $$1\mapsto 1$$ $$2\mapsto 1$$ $$3\mapsto 2$$ $$4\mapsto 5$$ $$5\mapsto 14$$ $$\vdots$$

  • $\begingroup$ Thank you for making it very clear for me! $\endgroup$ – Train Heartnet Nov 11 '13 at 17:26
  • $\begingroup$ I have a related question on the topic, which I've written as a comment below Asaf's answer. Could you help me on that as well, please? $\endgroup$ – Train Heartnet Nov 12 '13 at 7:04
  • $\begingroup$ I think you should put up a new question! $\endgroup$ – Ben Blum-Smith Nov 12 '13 at 17:32

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.