15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Oct 12 '11 at 1:20
  • $\begingroup$ 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$. $\endgroup$ – Brian M. Scott Oct 12 '11 at 1:21
  • $\begingroup$ math.stackexchange.com/q/2357899/631742 $\endgroup$ – Maximilian Janisch Dec 12 '19 at 9:57
22
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

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

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

enter image description here


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.
| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.