Hi,

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

Printable View

- Feb 28th 2010, 02:40 PMposix_memalignCartesian 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? - Feb 28th 2010, 02:52 PMPlato
- Feb 28th 2010, 03:02 PMposix_memalign
- Feb 28th 2010, 03:11 PMDrexel28
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. - Feb 28th 2010, 03:16 PMPlato