# Cartesian Product of Two Countable Sets is Countable [closed]

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

• 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. – hmakholm left over Monica 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
• math.stackexchange.com/q/2357899/631742 – Maximilian Janisch Dec 12 '19 at 9:57

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.

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.

• 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

We have a general result.

We use the notation $$[n] = \{0,1,2,3,\cdots ,n-1 \}$$.

Proposition 1: Let $$A$$ be a set and let $${(G_k)}_{k \in \mathbb N}$$ be a countable family of sets satisfying:

$$\tag 1 \text{Each } G_k \text{ is a nonempty finite subset of } A \text{ with cardinality } \alpha_k$$
$$\tag 2 \text{The family } G_k \text{ of sets is a partition of } A$$

For each $$k \ge 0$$ let there be given a bijective mapping

$$\tag 3 \tau_k: [\alpha_k] \to G_k$$

Then there exist a bijection $$f: \mathbb N \to A$$.
Proof
For each $$m \in \mathbb N$$ let $$K_m = \sum_{i=0}^{m-1} \alpha_i$$; note that $$K_0 = 0$$.
For each $$n \ge 0$$, define $$\lambda(n) = \text{max(} \{ m \, | \, K_m \le n \} \text{)}$$.
Since $$0 \le n - K_{\lambda(n)} \le \alpha_{\lambda(n)} - 1$$, we can define a function

$$\quad f(n) = \tau_{\lambda(n)}(n - K_{\lambda(n)})$$

It can be shown that this function $$f$$ is a bijective correspondence between $$\mathbb N$$ and $$A$$. $$\quad \blacksquare$$

Note that we defined an explicit function based on a sequence of given functions, so we are not using any form of the Axiom of Choice. This is a subtle point - we know the functions exist but an axiom in necessary if we want to pull them together out of 'thin air'.

Exercise: Define a bijective correspondence between $$\mathbb N$$ and $$\mathbb N \times \mathbb N$$ using the Cantor pairing function, as described in Wikipedia as Although using the summation notation might be using some implied induction/recursion, Proposition 1 describes a function directly. So the function doesn't have to carry an 'internal state baggage' as it executes. In practice, the mechanism will be much easier to program/calculate than it might appear.

Following is a Python program that implements the bijection.

L = 1
while True:
for y in range(0, L):
x = L - 1 - y
print((x,y), '', end='')
if x==0:
break
if L == 10:
print('...', end='')
print("\nProgram stopping after printing", L, 'levels.')
break
else:
L = L + 1
continue


OUTPUT:

(0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (0, 2) (3, 0) (2, 1) (1, 2) (0, 3) (4, 0) (3, 1) (2, 2) (1, 3) (0, 4) (5, 0) (4, 1) (3, 2) (2, 3) (1, 4) (0, 5) (6, 0) (5, 1) (4, 2) (3, 3) (2, 4) (1, 5) (0, 6) (7, 0) (6, 1) (5, 2) (4, 3) (3, 4) (2, 5) (1, 6) (0, 7) (8, 0) (7, 1) (6, 2) (5, 3) (4, 4) (3, 5) (2, 6) (1, 7) (0, 8) (9, 0) (8, 1) (7, 2) (6, 3) (5, 4) (4, 5) (3, 6) (2, 7) (1, 8) (0, 9) ...
Program stopping after printing 10 levels.