13
$\begingroup$

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

$\endgroup$

closed as off-topic by Xander Henderson, Xam, Arnaud Mortier, Ethan Bolker, David Hill Mar 22 '18 at 20:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Xam, Arnaud Mortier, Ethan Bolker, David Hill
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – Henning Makholm 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
19
$\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.

$\endgroup$
4
$\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.

$\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.
$\endgroup$

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