1. ## Cartesian product, countable?

Hi,
if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?

2. Originally Posted by posix_memalign
Hi,
if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?
Suppose that $\displaystyle A=\{a_1,a_2,a_3,\cdots\}~\&~B=\{b_1,b_2,b_3,\cdots \}$.

Then if $\displaystyle (a_n,b_m)\in A\times B$ define $\displaystyle \Theta[(a_n,b_m)]=2^n\cdot 3^m$.

Prove that $\displaystyle \Theta$ is an injection.

3. Originally Posted by Plato
Suppose that $\displaystyle A=\{a_1,a_2,a_3,\cdots\}~\&~B=\{b_1,b_2,b_3,\cdots \}$.

Then if $\displaystyle (a_n,b_m)\in A\times B$ define $\displaystyle \Theta[(a_n,b_m)]=2^n\cdot 3^m$.

Prove that $\displaystyle \Theta$ is an injection.
Thanks! But how did you deduce that $\displaystyle \Theta$ should be $\displaystyle \Theta[(a_n,b_m)]=2^n\cdot 3^m$?

4. Originally Posted by posix_memalign
Hi,
if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?
Basically the idea in Plaot's post is that you can prove that $\displaystyle \mathbb{N}^m$ is countable, because clearly the mapping $\displaystyle f:\mathbb{N}\mapsto\mathbb{N}^m$ given by $\displaystyle n\mapsto(n\underbrace{1,\cdots,1}_{m-1\text{ times}})$ is an injection and so is $\displaystyle g:\mathbb{N}^m\mapsto \mathbb{N}$ given by $\displaystyle \left(n_1,\cdots,n_m\right)\mapsto p_1^{n_1}\cdots p_m^{n_m}$ where $\displaystyle p_k$ is the $\displaystyle k$th prime. It follows by the Schroder- Bernstein theorem that the two sets are equipotent. But, if $\displaystyle E_1,\cdots,E_m$ is countable we know that for each there is a mapping $\displaystyle f_k:E_k\mapsto\mathbb{N}$ which is bijective. So, define a mapping $\displaystyle \prod_{j=1}^{m}f_j:\prod_{j=1}^{m}E_j\mapsto\mathb b{N}^m$ by $\displaystyle (e_1,\cdots,e_m)\mapsto\left(f_1(e_1),\cdots,f_m(e _m)\right)$.This is readily verified to be a bijection, and since $\displaystyle \mathbb{N}$ is countable it follows that $\displaystyle \prod_{j=1}^{m}E_j$ is countable.

Note: this is only true for finite cases. For example consider $\displaystyle \{0,1\}^{\aleph_0}$. This is uncountable, for if we could list it's elements in the fashion $\displaystyle \bold{x}_1,\bold{x}_2,\cdots$ then we can construct a tuple $\displaystyle \bold{x}$ where $\displaystyle \pi_j(\bold{x})=\begin{cases} 1 & \mbox{if} \quad \pi_j(\bold{x}_j)=0 \\ 0 & \mbox{if} \quad \pi_j(\bold{x}_j)=1\end{cases}$ and so it follows that $\displaystyle \bold{x}\in\{0,1\}^{\aleph_0}$ but $\displaystyle \bold{x}\notin\left\{\bold{x}_n\right\}_{n\in\math bb{N}}$. This clearly shows that we have not, and thus cannot, list all the elements of $\displaystyle \{0,1\}^{\aleph_0}$. It follows that $\displaystyle \{0,1\}^{\aleph_0}$ is uncountable.

5. Originally Posted by posix_memalign
Thanks! But how did you deduce that $\displaystyle \Theta$ should be $\displaystyle \Theta[(a_n,b_m)]=2^n\cdot 3^m$?
Practice, Practice, Practice.
All we must do is show that there is an injection from $\displaystyle A$ to $\displaystyle \mathbb{Z}^+$ in order to show that $\displaystyle A$ is countable.
That mapping just happens to work.