If $A$ and $B$ are countable, then $A\times B$ is countable

248 Views Asked by At

If $A$ and $B$ are countable, then $A\times B$ is countable.


My attempt:

Lemma 1: $A$ is countable if and only if there exists a injective mapping $f:A \to \Bbb N$.

Lemma 2: $\Bbb N\times\Bbb N$ is countable.

Since $A$ and $B$ are countable, there exist injections $j_A:A \to \Bbb N$ and $j_B:B \to \Bbb N$ by Lemma 1.

We define a mapping $j:A\times B \to \Bbb N\times\Bbb N$ by $j(a,b)=(j_A(a),j_B(b))$. It's clear that $j$ is injective.

Since $\Bbb N\times\Bbb N$ is countable by Lemma 2, there exists an injection $f:\Bbb N\times\Bbb N \to \Bbb N$ by Lemma 1.

Hence $f\circ j:A\times B \to \Bbb N$ in injective and hence $A\times B$ is countable by Lemma 1.


Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!