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

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!

• "It's clear that $j$ is injective" is not enough, you still need a proof, but it is good apart from this – Holo Sep 12 '18 at 17:08
• @LeAnhDung Great! Then note that $A \times B = \bigcup_{a \in A} \{a\} \times B$. – Randall Sep 12 '18 at 17:12
• @MikeEarnest he use this to prove the generalization – Holo Sep 12 '18 at 17:14
• @Holo I just meant that. You are faster than me ^^ – Le Anh Dung Sep 12 '18 at 17:14
• @LeAnhDung hah, nice(after sitting on my butt and being on the computer most of the day I learned to type fast :P) – Holo Sep 12 '18 at 17:16