Let A be denumerable set. How is it possible to show that the set of functions f:{0,1,2} ->A is denumerable?
How to show that this set of functions is denumerable?
-
2A 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$. – 2011-05-30
3 Answers
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!
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.
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?