Fix . Show that if A1,A2, . . . ,An are countable, then A1×A2× . . . × An is countable.
Does this require knowledge of the fact that N x N is countably infinite?
Thanks in advance.
Hello,
You can use the fact that is countable. Which can be done by induction, and you'll have to use the fact that is countable.
1.
You know that there exists an injective mapping
Let
Basis : for n=2, it's verified (I assume it's a know fact for you)
Inductive hypothesis : assume that there exists an injective mapping
Now, you have to prove that there exists an injective mapping
For this, define this way :
It is easy to show that it's injective, knowing that is injective.
2.
Now prove that there exists an injection from to
Since are countable, there exist injections
Define
Once again, it's easy to show that it's injective.
3.
We know that are injective.
Now you just have to prove that the composite of two injective functions is injective, in particular .
And you're done.