Fix $\displaystyle n >= 1$. 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 $\displaystyle n >= 1$. 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 $\displaystyle \mathbb{N}^n$ is countable. Which can be done by induction, and you'll have to use the fact that $\displaystyle \mathbb{N} \times \mathbb{N}$ is countable.

**1.**

You know that there exists an injective mapping $\displaystyle \phi_2 ~:~ \mathbb{N}^2 \to \mathbb{N}$

Let $\displaystyle n \geqslant 2$

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 $\displaystyle \phi_n ~:~ \mathbb{N}^n \to \mathbb{N}$

Now, you have to**prove**that there exists an injective mapping $\displaystyle \phi_{n+1} ~:~ \mathbb{N}^{n+1} \to \mathbb{N}$

For this, define $\displaystyle \phi_{n+1}$ this way :

$\displaystyle \phi_{n+1}(x_1,\dots,x_n,x_{n+1})=(\phi_n(x_1,\dot s,x_n),x_{n+1})$

It is easy to show that it's injective, knowing that $\displaystyle \phi_n$ is injective.

**2.**

Now prove that there exists an injection $\displaystyle \psi$ from $\displaystyle A_1 \times \dots \times A_n$ to $\displaystyle \mathbb{N}^n$

Since $\displaystyle A_1,\dots,A_n$ are countable, there exist injections $\displaystyle \psi_i ~:~ A_i \to \mathbb{N}$

Define $\displaystyle \psi (x_1,\dots,x_n)=(\psi_1(x_1),\dots,\psi_n(x_n))$

Once again, it's easy to show that it's injective.

**3.**

$\displaystyle A_1 \times \dots \times A_n \stackrel{\psi}{\longrightarrow} \mathbb{N}^n \stackrel{\phi_n}{\longrightarrow} \mathbb{N}$

We know that $\displaystyle \psi, \phi_n$ are injective.

Now you just have to prove that the composite of two injective functions is injective, in particular $\displaystyle \phi_n \circ \psi$.

And you're done. - Jan 21st 2009, 08:56 AMThePerfectHacker
If you know that $\displaystyle \mathbb{N}\times \mathbb{N}$ is countable then it is easy to prove this result.

If $\displaystyle |A| = |B|= |\mathbb{N}|$ then $\displaystyle |A\times B| = |\mathbb{N}\times \mathbb{N}|$ is countable.

Thus, $\displaystyle |A_1\times ... \times A_n| = |\mathbb{N} \times ... \times \mathbb{N}|$.

We established that $\displaystyle \mathbb{N}^2$ was countable.

If $\displaystyle \mathbb{N}^k$, $\displaystyle k\geq 2$ is countable then $\displaystyle \mathbb{N}^{k+1} = \mathbb{N}^k \times \mathbb{N}$ is countable.

The rest follows by induction.