Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

3 Answers 3

up vote 2 down vote accepted

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?

share|improve this answer

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.

share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.