# I need help with proofs pertaining to countability [duplicate]

Let $A$ and $B$ be countable sets.

(a) Show that $A \times B$ is countable. Hint: Show that there is a bijection from $A\times B$ onto a subset of $\Bbb Z \times\Bbb Z$:

(b) Use induction on $n$ to show that $A_1 \times A_2 \times \ldots \times A_n$ is countable if $A_1, A_2,\ldots, A_n$ are countable.

-
Have you tried searching the site? –  Asaf Karagila Dec 14 '12 at 21:04
Was the hint not helpful enough? –  Hagen von Eitzen Dec 14 '12 at 21:08
Note, though that the proofs in the answers to the question that @Amr mentions are very different from the one suggested in your hint. They are direct proofs; yours makes use of the result that $\Bbb Z\times\Bbb Z$ is countable, which presumably you’ve already proved. –  Brian M. Scott Dec 14 '12 at 21:19
Note that the question found by @Asaf covers only (b). –  Brian M. Scott Dec 14 '12 at 21:21
@Brian: Thanks, luckily Amr's duplicate covers (a). –  Asaf Karagila Dec 14 '12 at 21:26
show 1 more comment

## marked as duplicate by Asaf Karagila, Amr, JSchlather, TMM, QiL Dec 14 '12 at 22:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 1 Answer

A small additional nudge for (a): if $f:W\to Y$ and $g:X\to Z$ are injections, the map

$$W\times X\to Y\times Z:\langle w,x\rangle\mapsto\big\langle f(w),g(x)\big\rangle$$

is an injection. Why, and how is this useful for your problem?

There really isn’t much to say about (b) that isn’t already present in Use induction. Note, though, that you can work on (b) even without having done (a). The proof of (b) does not require that you know how to prove (a): it requires only that you assume (a) to be true.

-
add comment