# Is this proof about equicardinality correct and/or rigorous? Can it be helped?

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.

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$).

• 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? – Jxt921 May 16 '16 at 19:10
• 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. – Jxt921 May 16 '16 at 19:20

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.