# Countability

• Dec 22nd 2009, 07:41 PM
Drexel28
Countability
Hello, friends. As you well know, many times in math you formulate a proof that seems air-tight yet always seems to hold some infinitesimal flaw. Particularly, I have recently been reviewing some old stuff for fun and the following bothers me. I know and have been able to do the normal proofs rather easily, but the following proof to me seems simpler. Is there anything wrong with it?

Problem: Let $\displaystyle X_1,\cdots,X_m$ be countable. Prove that $\displaystyle \prod_{\jmath=1}^{m}X_{\jmath}$ is countable.

Lemma: $\displaystyle \mathbb{N}^m$ is countable for any finite $\displaystyle m$.

Proof: By virtue of the Schroder-Bernstein theorem we must only find an injection from $\displaystyle \mathbb{N}$ to $\displaystyle \mathbb{N}^m$ and one backwards.

For the first one, merely let $\displaystyle f:\mathbb{N}\mapsto\mathbb{N}^m$ be given by $\displaystyle n\mapsto(n,\underbrace{1,\cdots,1}_{m-1\text{ times}})$. To see that this is injective assume that $\displaystyle f(n)=f\left(n'\right)\implies \left(n,1,\cdots,1\right)=\left(n',1,\cdots,1\righ t)$ and since a pair of $\displaystyle m$-tuples are

equal only when their components are equal we see that particularly we must have that $\displaystyle n=n'$ and the conclusion follows.

For an injection backwards let $\displaystyle 2,\cdots,p_m$ be the first $\displaystyle m$ primes and let $\displaystyle \tilde{f}:\mathbb{N}^m\mapsto\mathbb{N}$ be given by $\displaystyle \left(n_1,\cdots,n_m\right)\mapsto 2^{n_1}\cdot 3^{n_2}\cdots p_m^{n_m}$. Now suppose that

$\displaystyle f\left(n_1,\cdots,n_m\right)=f\left(n'_1,\cdots,n' _m\right)\implies 2^{n_1}\cdot 3^{n_2}\cdots p_m^{n_m}=2^{n'_1}\cdot 3^{n'_2}\cdots p_m^{n'_m}$. To see that this is injective we may either use a congruence argument noting the coprimeness of all primes, or more

simply, note that the LHS and RHS of the above represent a prime factorization of the same natural number and by virtue of the FTA (particularly that prime factorizations are unique) we must have

that the exponents of each prime are equal. Thus, $\displaystyle n_1=n'_1,\cdots,n_m=n'_m\implies \left(n_1,\cdots,n_m\right)=\left(n'_1,\cdots,n'_m \right)$ and the conclusion follows. $\displaystyle \blacksquare$.

Proof:

Now, considering the problem at hand. We know that since $\displaystyle X_1,\cdots,X_,$ are countable that there exists $\displaystyle f_1:X_1\mapsto\mathbb{N},\cdots,f_m:X_m\mapsto\mat hbb{N}$ which are bijections. Therefore, define a mapping

$\displaystyle \hat{f}:\prod_{\jmath=1}^{m}X_\jmath\mapsto\mathbb {N}^{m}$ by $\displaystyle \left(x_1,\cdots,x_m\right)\mapsto\left(f_1\left(x _1\right),\cdots,f_m\left(x_m\right)\right)$. To see that this is a bijeciton we first show that it is injective.

Suppose that $\displaystyle \hat{f}\left(x_1,\cdots,x_m\right)=\hat{f}\left(x' _1,\cdots,x'_m\right)\implies \left(f_1\left(x_1\right),\cdots,f_m\left(x_m\righ t)\right)=\left(f_1\left(x'_1\right),\cdots,f_m\le ft(x'_m\right)\right)$. Now, appealing, once again, to the definition of an $\displaystyle m$-tuple we see that

$\displaystyle f_1\left(x_1\right)=f_1\left(x'_1\right),\cdots,f_ m\left(x_m\right)=f_m\left(x'_m\right)$ and since each of these functions are individually injective it follows that $\displaystyle x_1=x'_1,\cdots,x_m=x'_m$ and the conclusion follows.

To show that $\displaystyle \hat{f}$ is surjective let $\displaystyle \left(n_1,\cdots,n_m\right)\in\mathbb{N}^m$. Since $\displaystyle n_1,\cdots,n_m\in\mathbb{N}$ and $\displaystyle f_1:X_1\mapsto\mathbb{N},\cdots,f_m:X_m\mapsto \mathbb{N}$ are surjective we know there exists some $\displaystyle x_1\in X_1,\cdots,x_m\in X_m$ such that

$\displaystyle f\left(x_1\right)=n_1,\cdots,f\left(x_m\right)=n_m$. But from this we see that for the above $\displaystyle x_1,\cdots,x_m$ that $\displaystyle \left(x_1,\cdots,x_m\right)\in\prod_{\jmath=1}^m X_\jmath$ and $\displaystyle \hat{f}\left(x_1,\cdots,x_m\right)=\left(f_1\left( x_1\right),\cdots,f_m\left(x_m\right)\right)=\left (n_1,\cdots,n_m\right)$ which shows $\displaystyle \hat{f}$'s surjectivity.

From this we see that $\displaystyle \hat{f}:\prod_{\jmath=1}^{m}\mapsto\mathbb{N}^m$ is a bijection, and in particulary we see that $\displaystyle \prod_{\jmath=1}^m X_\jmath\cong\mathbb{N}^m$ (where $\displaystyle \cong$ denotes having the same cardinal number), but from the lemma we know that $\displaystyle \mathbb{N}^m\cong\mathbb{N}$ and since $\displaystyle \cong$ is an equivalence relation (specifically transitive) we see that $\displaystyle \prod_{\jmath=1}^m X_\jmath\cong\mathbb{N}$ which finishes the arugment. $\displaystyle \blacksquare$

Is that correct? Thank you VERY much in advance for taking the time to read this.
• Dec 23rd 2009, 12:06 AM
Moo
Hello,

Unless I missed something, it's correct.
But I wonder what the "normal proofs" were, as it seems to me that it's a common one you used (Surprised)
• Dec 23rd 2009, 12:09 AM
Drexel28
Quote:

Originally Posted by Moo
Hello,

Unless I missed something, it's correct.
But I wonder what the "normal proofs" were, as it seems to me that it's a common one you used (Surprised)

I guess that I have weird books. The books that I have on the subject seem give rather geometric argumens to prove that $\displaystyle X_1\times X_2$ is countable and then use induction to prove the general case.

Regardless, thank you very much Moo.