0
$\begingroup$

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.

  • 1
    Have you tried searching the site?2012-12-14
  • 1
    Was the hint not helpful enough?2012-12-14
  • 0
    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.2012-12-14
  • 0
    Note that the question found by @Asaf covers only (b).2012-12-14
  • 0
    @Brian: Thanks, luckily Amr's duplicate covers (a).2012-12-14
  • 0
    @Asaf: But not in a way compatible with the hint in the problem, which is why I won’t vote to close.2012-12-14

1 Answers 1

0

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.