# Thread:

1. ## Countability Proof

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.

2. 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.

3. 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 29, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9349659085273743, "perplexity_flag": "middle"}