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!

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


You must log in to answer this question.

Browse other questions tagged .