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.

How can I prove that the Cartesian product of two countable sets is also countable?

share|improve this question
    
Can you prove that $\mathbb N\simeq\mathbb N\times\mathbb N$? Compose that proof with the (product of the) bijections you get from knowing that $A$ and $B$ are countable. –  Henning Makholm Oct 12 '11 at 1:20
    
Do you know how to prove that $\mathbb{N}\times\mathbb{N}$ is countable? Because if you do, you can use essentially the same argument for $A\times B$. –  Brian M. Scott Oct 12 '11 at 1:21
add comment

2 Answers 2

up vote 7 down vote accepted

In your answer you use Cantor's pairing function. It is an important function indeed. However using Cantor-Bernstein's theorem we only need to find an injection from $\mathbb N\times\mathbb N$ into $\mathbb N$.

A useful example is: $$f(m,n) = 2^m\cdot 3^n$$

If $f(m,n)=f(l,k)$ then by the fundamental theorem of arithmetics we have that $m=l, n=k$.

We now can find an injection $g\colon\mathbb N\to\mathbb N\times\mathbb N$, for example $g(n)=(0,n)$.

Now Cantor-Bernstein's theorem tells us that if $f\colon A\to B$ and $g\colon B\to A$ are two injective functions, then there is a bijection from $A$ into $B$.

From this to $\mathbb N^k$ being countable, you can either go with induction, as you suggested, or map $(m_1,\ldots,m_k)$ to $p_1^{m_1}\cdot\ldots p_k^{m_k}$, where $p_i$ is the $i$-th prime number.

share|improve this answer
add comment

So I know $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ via (provided from class proof): $$f(x,y) = \frac{(x + y - 2)(x + y - 1)}{2}$$ Then it would mean that two countable sets, $A$ and $B$, can be set up as $f:\mathbb{N} \to A $ and $g: \mathbb{N} \to B$. This points to: $$f \times g : \mathbb{N} \times \mathbb{N} \to A \times B$$ There is now a surjection $\mathbb{N} \times \mathbb{N}$ to $A \times B$ $\implies$ $A \times B$ is also countable. So then induction can be used in the number of sets in the collection.

share|improve this answer
    
Yes, this is why the product of finitely many countable sets is still countable. –  Asaf Karagila Oct 12 '11 at 15:16
    
Another map in like yours is this: $f(x)=\frac{(x+y)^2+3x+y}{2}$ –  leo Oct 13 '11 at 0:10
add comment

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.