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.

Printable View

- Jan 20th 2009, 08:28 PMh2ospreyCountability Proof
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. - Jan 21st 2009, 02:17 AMMoo
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. - Jan 21st 2009, 08:56 AMThePerfectHacker