# What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to?

What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to? I have figured out the question when it's the other way around, but I am not making any progress here. The worst thing is, I don't know how to think of such problems, and even when it was functions from $\mathbb{N}$ to $\{0, 1\}$, I would have never gotten it myself without help. When I think about this I think of the following: it's a function, so one thing can't be sent to two+ things, but two things can be sent to the same thing. So at least, we are mapping both 0 and 1 to the same element, and at most we are mapping it to two different elements. But that doesn't really give me anything... Thanks!

-
By the time I wrote my answer you have accepted the first one given. Five minutes later and two more answers were added as well. For a recent discussion about this on the meta: meta.math.stackexchange.com/questions/2553/… –  Asaf Karagila Jul 12 '11 at 18:10
@Asaf: Thanks for the link and for your answer. I have been running into the issue of not knowing which answer to accept on numerous occasions now (I feel like more than half of them deserve being accepted, if not all), and I certainly haven't been giving them that much time... I will do better next time. –  confused Jul 12 '11 at 20:30

$|\{\text{functions } \{0,1\} \to \mathbb{N} \}|= |\mathbb{N}^{\{0,1\}}|= |\mathbb{N}^2|$

Indeed, if you are thinking of $\mathbb{N}^2$ as the set of ordered pairs of natural numbers, then the function

$\varphi: \{\text{functions } \{0,1\} \to \mathbb{N} \} \to \mathbb{N}^2$ defined as $\varphi(f)= (f(0),f(1))$

is a bijection.

It is an injection: if $f\not=g$, then $f(0)\not=g(0)$ or $f(1)\not=g(1)$, hence $\varphi(f)\not= \varphi(g)$.

It is a surjection: given $(m,n)\in \mathbb{N}^2$, define $f:\{0,1\} \to \mathbb{N}$ as $f(0)=m$, $f(1)=n$. Then $\varphi(f)=(m,n)$.

In fact, for some intuition, think that what this bijection is saying is that a function $\{0,1\}\to \mathbb{N}$ is completely determined by a couple of natural numbers. Who could they be but $f(0)$ and $f(1)$? :)

So, now I claim that $|\mathbb{N}^2|=|\mathbb{N}|$. Indeed, it is the cartesian product of two countable sets, and the cartesian product of a finite number of countable sets is countable, hence the set of functions $\{0,1\} \to \mathbb{N}$ is countable, i.e. it is equinumerous to $\mathbb{N}$.

You comment you can't use cardinal arithmetic: a more constructive proof would be to exhibit a bijection. See this question: How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$? which attacks the problem of showing that $|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|$ more directly.

ADDED: An obvious generalization of the above leads to the fact that, for $n\in \mathbb{N}$, $|\{\text{functions } \{0,\dots,n-1\} \to \mathbb{N}\}| = |\mathbb{N}^n|$. Having this in mind, now forget you ever defined $\mathbb{N}^k$ for any $k\in \mathbb{N}$. Let's have a different approach.

Let $I$ be any given set. Define $\mathbb{N}^I$ as $$\mathbb{N}^I := \{\text{functions } I \to \mathbb{N}\}$$

This is the usual notation for the set of functions from $I$ to $\mathbb{N}$.

Now, in set theory (Zermelo-Fraenkel), the number $k\in \mathbb{N}$ is defined as the set $\{0,\dots,k-1\}$. So what if we take $I=\{0,\dots,k-1\}$? We have that $$\mathbb{N}^k=\mathbb{N}^{\{0,\dots,k-1\}} = \{\text{functions } \{0,\dots,k-1\} \to \mathbb{N}\}$$

In particular, with $k=2$, we obtain that $\mathbb{N}^2=\{\text{functions } \{0,1\} \to \mathbb{N} \}= \{\text{functions } 2 \to \mathbb{N}\}$. Now the above proof shows that our new $\mathbb{N}^2$ is equinumerous to the set of ordered pairs of natural numbers. This is nice. Why?

Well, first observe that equinumerous sets are indistinguishable from the point of view of set theory (in fancy words: bijections are isomorphisms in Set). So if two sets are equinumerous, there is no harm done with taking any of them as the definition of the set.

Then, observe that this definition is in much bigger generality. We have defined $\mathbb{N}^I$ for any set $I$. With our previous definition, we could only extend the generality for any finite set $I$, namely defining $\mathbb{N}^I$ as the set of $|I|$-uples of natural numbers: this definition makes no sense a priori for infinite $I$.

A final observation: in this final addendum, $\mathbb{N}$ can be taken to be any set, of course.

-
Thanks, but I don't think I can use any cardinal arithmetic, just general wit... I have proved than $\mathbb{N}^2$ is equinumerous to $\mathbb{N}$ before, it's a question of getting to $\mathbb{N}^2$ w/o cardinal arithmetic here, I guess. –  confused Jul 12 '11 at 17:33
Bruno, since I can't use cardinal arithmetic, I don't think I am allowed to make the step of $|\{\text{functions } \{0,1\} \to \mathbb{N} \}|= |\mathbb{N}^{\{0,1\}}|= |\mathbb{N}^2|$, I think I just don't "know" this is true. OHH nevermind, I see your update, I think it makes sense now! Thanks –  confused Jul 12 '11 at 17:41
@confused: I've added a couple of things which may be nice to you. To think of $\mathbb{N}^2$ as pairs of natural numbers is the same that thinking $\mathbb{N}^2$ as the set of functions $2\to \mathbb{N}$, since $2=\{0,1\}$ in ordinary set theory. This is easily generalized. –  lentic catachresis Jul 13 '11 at 13:47
I don't understand what is the problem with $\omega$-tuples or $\omega_3$-tuples of numbers. –  Asaf Karagila Jul 13 '11 at 13:50
@Asaf: they can't be defined on a first year undergraduate course :) –  lentic catachresis Jul 13 '11 at 14:26

The set of functions from $\{0,1\}$ to $\mathbb N$ (denoted by $A$ from here on end) can be seen as the set of all ordered pairs in $\mathbb N\times\mathbb N$.

Let us prove that:

• Suppose $f\in A$, then $f(0)\in\mathbb N$ and $f(1)\in\mathbb N$, therefore the pair $\langle f(0),f(1)\rangle\in\mathbb N\times\mathbb N$, this means that this mapping is indeed well defined.

• Suppose $f,g\in A$ two different functions, either $f(0)\neq g(0)$ or $f(1)\neq g(1)$. Either way $\langle f(0),f(1)\rangle\neq\langle g(0),g(1)\rangle$, we also have that this mapping is injective (sends two different elements to different results).

• Suppose $\langle a,b\rangle\in\mathbb N\times\mathbb N$, define $f\in A$ as $f(0)=a, f(1)=b$ then $f$ is mapped to $\langle a,b\rangle$, therefore the mapping is onto $\mathbb N\times\mathbb N$.

All in all we have the mapping is a bijection, so it is enough to understand what is the size of $\mathbb N\times\mathbb N$.

The cardinality of this collection is indeed $\aleph_0$. There are two common ways to show that:

1. Cantor's pairing function, $\langle a,b\rangle\mapsto \frac{(a+b)(a+b+1)}{2}+a$, and show it is indeed a bijection.

2. Cantor-Bernstein's theorem, we find injections from $\mathbb N$ into $\mathbb N\times\mathbb N$ and vice-versa. Clearly $\mathbb N$ is not of larger cardinality (by $n\mapsto \langle 0,n\rangle$ which is clearly injective), on the other hand $\langle a,b\rangle\mapsto 2^a3^b$ is also an injective mapping, implying $|\mathbb N\times\mathbb N|\le|\mathbb N|$, and therefore $\mathbb N$ and $\mathbb N\times\mathbb N$ have the same cardinality.

-

HINT $\rm\quad\ \ |Maps(\{0,1\},\mathbb N)| \le |\mathbb N|\$ since $\rm\ f\:\mapsto\: 2^{\:f(0)}\ 3^{\:f(1)}\$ is injective (one-to-one).

Reversely $\rm\:|Maps(\{0,1\},\mathbb N)| \ge |\mathbb N|\:$ as it includes the $\rm\:|\mathbb N|\:$ constant maps $\rm\:f_{\:n}\:$ mapping$\rm\ 0,1\:$ to $\rm\:n\:.$

-

Let $f$ be a function from $\{0,1\}$ to $\mathbb{N}$. Then $f$ is uniquely determined by its values at $0$ and $1$. $f(0)$ can be any natural number, and so can $f(1)$. So this corresponds to $\mathbb{N}^2$. Another way to say this is that the map $f \rightarrow (f(0),f(1))$ is a bijection from the set of all functions from $\{0,1\}$ to $\mathbb{N}$ to $\mathbb{N}^2$.

-