4
$\begingroup$

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!

$\endgroup$
  • 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$ – Holo Sep 12 '18 at 17:08
  • 3
    $\begingroup$ @LeAnhDung Great! Then note that $A \times B = \bigcup_{a \in A} \{a\} \times B$. $\endgroup$ – Randall Sep 12 '18 at 17:12
  • 1
    $\begingroup$ @MikeEarnest he use this to prove the generalization $\endgroup$ – Holo Sep 12 '18 at 17:14
  • 1
    $\begingroup$ @Holo I just meant that. You are faster than me ^^ $\endgroup$ – Le Anh Dung Sep 12 '18 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$ – Holo Sep 12 '18 at 17:16

Your Answer

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

Browse other questions tagged or ask your own question.