# How many functions are there from $\mathbb Z$ to $\mathbb Z$?

Repeating the question,

How many functions are there from $\mathbb Z$ to $\mathbb Z$?

A function $f \colon A \to B$ is a subset of $A \times B$ satisfying $$(a,b) = (a,c) \qquad \Rightarrow \qquad b = c,$$ so it's enough (maybe) to look at subsets of $\mathbb Z \times \mathbb Z$. We know $|\mathbb Z \times \mathbb Z| = |\mathbb Z|$, and that the number of subsets of $\mathbb Z$ is $2^{|\mathbb Z|}$, but this counts finite subsets as well. Unsure of where to proceed from here.

We have $|\mathbb{Z}^\mathbb{Z}| = |\mathbb{Z}|^{|\mathbb{Z}|} = 2^{|\mathbb{Z}|}$. To show this second equality, consider

$2^{|\mathbb{Z}|} \leq |\mathbb{Z}|^{|\mathbb{Z}|} \leq (2^{|\mathbb{Z}|})^{|\mathbb{Z}|} = 2^{|\mathbb{Z}|\cdot|\mathbb{Z}|} = 2^{|\mathbb{Z} \times \mathbb{Z}|} = 2^{|\mathbb{Z}|}$.

• Love this answer Commented Sep 10, 2016 at 23:51

You’ve made a start. As you say, each function from $\Bbb Z$ to $\Bbb Z$ is a subset of $\Bbb Z\times\Bbb Z$, so there are at most $2^{|\Bbb Z|}$ of them. To finish the argument you could prove that there are also at least $2^{|\Bbb Z|}$ such functions by actually finding that many that you can clearly identify as distinct.

HINT: For each $A\subseteq\Bbb Z$ let

$$f_A:\Bbb Z\to\Bbb Z:n\mapsto\begin{cases} 1,&\text{if }n\in A\\ 0,&\text{otherwise}\;. \end{cases}$$

Suppose $a,b,c,d,e,f,g,\ldots$ is an infinite sequence of positive integers (just use all of the infinitely many letters of the alphabet . . . . . ), thus a function from $\mathbb N$ to $\mathbb N$, and consider the number $$a + \cfrac 1 {b + \cfrac 1 {c + \cfrac 1 {d+ \cfrac 1 {e + \cfrac 1 {f + \cfrac 1 {g + \cdots}}}}}}.$$ This gets you a one-to-one correspondence between the set of all functions from $\mathbb N$ to $\mathbb N$ and the set of all positive irrational numbers.

Now show that there is a one-to-one correspondence between the set of all functions from $\mathbb N$ to $\mathbb N$ and the set of all functions from $\mathbb Z$ to $\mathbb Z$ (that's easy) and also a one-to-one corresponence between the set of all positive irrational numbers and $\mathbb R$, and then you've got it.