Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Countable Sets and the Cartesian Product of them
Inductive Proof of a countable set Cartesian product

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.

share|improve this question

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.

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

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.