0
$\begingroup$

Here's the proof than a Cartesian product of two countable sets is countable(the proof is used, for example, in C.Pugh's "Real Mathematical Analysis" with one exception: they prove equicardinality of $\mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$, but there isn't really any difference):

Let $A$ and $B$ be countable sets. We think of $A \times B$ as of a "infinite" matrix $\infty \times \infty$ or $\infty \times n$ or $m \times \infty$(the case when it's finite $m \times n$ matrix is obvious):

$(a_1, b_1), (a_1, b_2), ..., (a_1, b_m), ...$

$(a_2, b_1), (a_2, b_2), ..., (a_2, b_m), ...$

$ \ \ \ ... \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ ... \ \ \ \ \ \ ... \ \ \ \ \ \ ...$

$(a_n, b_1), (a_n, b_2), ..., (a_n, b_m), ...$

$ \ \ \ ... \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ ... \ \ \ \ \ \ ... \ \ \ \ \ \ ...$

This gives a sequence $(a_1, b_1), (a_2, b_1), (a_1, b_2), ...$ and proves that $A \times B$ is countable(or denumerable, since the finite case is a different one).

Doesn't strike me as rigorous, though. Can this proof be helped and be given more rigour? For example, if both $A$ and $B$ are denumerable, we can state(using $\infty \times \infty$ matrix above) that $|A \times B| = |A_1 \cup A_2 \cup ... \cup A_n \cup ... |$ where $A_k$ is a member of a denumerable family of pairwise disjoint sets $ \{A_i \}, i \in \mathbb{N}$. Maybe, we can first prove that a union of a countable family of countable sets is countable.

$\endgroup$
2
$\begingroup$

Have a look at the explicit bijective map $\Bbb N\times\Bbb N\to\Bbb N$, $(a,b)\mapsto \frac{(a+b)(a+b+1)}{2}+b$.

The case of countable family of countable set is almost the same - except that it may involve a bit more need for Choice (we need an enumeration for each $A_i$).

$\endgroup$
  • $\begingroup$ Suppose we know that $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$ and we know that $|A| = |B| = |\mathbb{N}|$. How do we get from there to $|A \times B| = |\mathbb{N} \times \mathbb{N}|$? It's intuitively obvious, but how to prove it rigorously? $\endgroup$ – Jxt921 May 16 '16 at 19:10
  • $\begingroup$ Ah, I got it. We know that there are bijections $f: A \to \mathbb{N}$ and $g: B \to \mathbb{N}$. Then we define $f \times g: A \times B \to \mathbb{N} \times \mathbb{N}$ by setting $(f \times g)((a,b)) = (f(a), g(b))$ and we prove it is a bijection. $\endgroup$ – Jxt921 May 16 '16 at 19:20
0
$\begingroup$

I want to suggest one more way to prove that $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$. We use two injections:

1) $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}, f(m,n) = 2^m3^n$. Fundamental theorem of arithmetic tells us $f$ is injective.

2) $g: \mathbb{N} \to \mathbb{N} \times \mathbb{N}, f(n) = (n,0)$. Obviously, it is also injective.

Schröder–Bernstein theorem then tells us there is a bijection between these sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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