# How to show that this set of functions is denumerable?

Let A be denumerable set. How is it possible to show that the set of functions f:{0,1,2} ->A is denumerable?

-
A general fact is: if $I$ is a set and if $S$ is the set of all functions $f:I\to A$, then $S$ is in one-to-one correspondence with $A^I$: the set of all tuples indexed by $I$ whose coordinates lie in $A$. – Amitesh Datta May 30 '11 at 6:52

For each triple of elements $(x,y,z)\in A^3$, let $f_{x,y,z}:\{0,1,2\}\rightarrow A$ be the function that satisfies $$f_{x,y,z}(0)=x,$$ $$f_{x,y,z}(1)=y,$$ $$f_{x,y,z}(2)=z.$$ Every function $f:\{0,1,2\}\rightarrow A$ is equal to some $f_{x,y,z}$ - specifically, $f_{f(0),f(1),f(2)}$ - and if $f_{x,y,z}=f_{a,b,c}$, then $$f_{x,y,z}(0)=x=a=f_{a,b,c}(0)$$ $$f_{x,y,z}(1)=y=b=f_{a,b,c}(1)$$ $$f_{x,y,z}(2)=z=c=f_{a,b,c}(2),$$ and therefore $(x,y,z)=(a,b,c)$. Thus, the set of functions $f:\{0,1,2\}\rightarrow A$ is in bijection with the set $A^3=\{(x,y,z)\mid x,y,z\in A\}$.

Let $g:\mathbb{N}\rightarrow A$ be a bijection (such a $g$ exists because $A$ is denumerable). Then $G:\mathbb{N}^3\rightarrow A^3$ defined by $G(n_1,n_2,n_3)=(g(n_1),g(n_2),g(n_3))$ is a bijection. Therefore, proving that $\mathbb{N}^3$ is denumerable will prove that $A^3$ is denumerable, and therefore prove that the set of functions $\{f:\{0,1,2\}\rightarrow A\}$ is denumerable.

Do you see a way of proving that $\mathbb{N}^3$ is denumerable? Say, by using a generalization of this technique?

-

Without loss of generality, take $A = \mathbb{N}$. Given $f : \{0,1,2\} \to \mathbb{N}$, identify $f$ with the natural number $2^{f(0)} 3^{f(1)} 5^{f(2)}$. By prime factorization, this identification is one-to-one.

-

The following steps lead to a proof:

(1) Show that we can identify the set of all functions $f:\{0,1,2\}\to A$ with the set of all three-tuples whose coordinates are elements of $A$: $A\times A\times A=\{(x_1,x_2,x_3):x_i\in A,1\leq i\leq 3\}$.

(2) Prove that the set $A^3=A\times A\times A$ ($\times$ denotes cartesian product) is countable. In fact, it suffices to prove that if $A$ and $B$ are countable, then $A\times B$ is countable. Once we have done this, we obtain (by induction on $n$) the more general fact that if $A_i$ ($1\leq i\leq n$) is a finite collection of countable sets, then $A_1\times\cdots\times A_n$ is also countable. (Hint: Show that it is enough to prove $\mathbb{Z}\times \mathbb{Z}$ is countable and use Cantor's diagonal argument.)

I hope this helps!

-