Cartesian product, countable?

Printable View

February 28th 2010, 02:40 PM
posix_memalign

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?
February 28th 2010, 02:52 PM
Plato

Quote:

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 $A=\{a_1,a_2,a_3,\cdots\}~\&~B=\{b_1,b_2,b_3,\cdots \}$ .

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

Prove that $\Theta$ is an injection.
February 28th 2010, 03:02 PM
posix_memalign

Quote:

Originally Posted by Plato

Suppose that $A=\{a_1,a_2,a_3,\cdots\}~\&~B=\{b_1,b_2,b_3,\cdots \}$ .

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

Prove that $\Theta$ is an injection.

Thanks! But how did you deduce that $\Theta$ should be $\Theta[(a_n,b_m)]=2^n\cdot 3^m$ ?
February 28th 2010, 03:11 PM
Drexel28

Quote:

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 $\mathbb{N}^m$ is countable, because clearly the mapping $f:\mathbb{N}\mapsto\mathbb{N}^m$ given by $n\mapsto(n\underbrace{1,\cdots,1}_{m-1\text{ times}})$ is an injection and so is $g:\mathbb{N}^m\mapsto \mathbb{N}$ given by $\left(n_1,\cdots,n_m\right)\mapsto p_1^{n_1}\cdots p_m^{n_m}$ where $p_k$ is the $k$ th prime. It follows by the Schroder- Bernstein theorem that the two sets are equipotent. But, if $E_1,\cdots,E_m$ is countable we know that for each there is a mapping $f_k:E_k\mapsto\mathbb{N}$ which is bijective. So, define a mapping $\prod_{j=1}^{m}f_j:\prod_{j=1}^{m}E_j\mapsto\mathb b{N}^m$ by $(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 $\mathbb{N}$ is countable it follows that $\prod_{j=1}^{m}E_j$ is countable.

Note: this is only true for finite cases. For example consider $\{0,1\}^{\aleph_0}$ . This is uncountable, for if we could list it's elements in the fashion $\bold{x}_1,\bold{x}_2,\cdots$ then we can construct a tuple $\bold{x}$ where $\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 $\bold{x}\in\{0,1\}^{\aleph_0}$ but $\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 $\{0,1\}^{\aleph_0}$ . It follows that $\{0,1\}^{\aleph_0}$ is uncountable.
February 28th 2010, 03:16 PM
Plato

Quote:

Originally Posted by posix_memalign

Thanks! But how did you deduce that $\Theta$ should be $\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 $A$ to $\mathbb{Z}^+$ in order to show that $A$ is countable.
That mapping just happens to work.