Countability Proof

**h2osprey** · January 20th 2009, 09:28 PM

Fix $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.

**Moo** · January 21st 2009, 03:17 AM

Hello,

Originally Posted by h2osprey

Fix $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.

You can use the fact that $\mathbb{N}^n$ is countable. Which can be done by induction, and you'll have to use the fact that $\mathbb{N} \times \mathbb{N}$ is countable.

1.
You know that there exists an injective mapping $\phi_2 ~:~ \mathbb{N}^2 \to \mathbb{N}$
Let $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 $\phi_n ~:~ \mathbb{N}^n \to \mathbb{N}$
Now, you have to prove that there exists an injective mapping $\phi_{n+1} ~:~ \mathbb{N}^{n+1} \to \mathbb{N}$
For this, define $\phi_{n+1}$ this way :
$\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 $\phi_n$ is injective.

2.
Now prove that there exists an injection $\psi$ from $A_1 \times \dots \times A_n$ to $\mathbb{N}^n$
Since $A_1,\dots,A_n$ are countable, there exist injections $\psi_i ~:~ A_i \to \mathbb{N}$
Define $\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.
$A_1 \times \dots \times A_n \stackrel{\psi}{\longrightarrow} \mathbb{N}^n \stackrel{\phi_n}{\longrightarrow} \mathbb{N}$
We know that $\psi, \phi_n$ are injective.
Now you just have to prove that the composite of two injective functions is injective, in particular $\phi_n \circ \psi$ .

And you're done.

**ThePerfectHacker** · January 21st 2009, 09:56 AM

Originally Posted by h2osprey

Fix $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.

If you know that $\mathbb{N}\times \mathbb{N}$ is countable then it is easy to prove this result.

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

Thus, $|A_1\times ... \times A_n| = |\mathbb{N} \times ... \times \mathbb{N}|$ .
We established that $\mathbb{N}^2$ was countable.
If $\mathbb{N}^k$ , $k\geq 2$ is countable then $\mathbb{N}^{k+1} = \mathbb{N}^k \times \mathbb{N}$ is countable.
The rest follows by induction.

Thread: Countability Proof

LinkBack

Thread Tools

Display

Countability Proof

Similar Math Help Forum Discussions

Interval Countability proof

Countability of Subsets proof

Countability proof.

Inductive Proof of Countability of Algebraic Numbers

Proof of countability

Search Tags