Countability

**Drexel28** · December 22nd 2009, 07:41 PM

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 $X_1,\cdots,X_m$ be countable. Prove that $\prod_{\jmath=1}^{m}X_{\jmath}$ is countable.

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

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

For the first one, merely let $f:\mathbb{N}\mapsto\mathbb{N}^m$ be given by $n\mapsto(n,\underbrace{1,\cdots,1}_{m-1\text{ times}})$ . To see that this is injective assume that $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 $m$ -tuples are

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

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

$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, $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. $\blacksquare$ .

Proof:

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

$\hat{f}:\prod_{\jmath=1}^{m}X_\jmath\mapsto\mathbb {N}^{m}$ by $\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 $\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 $m$ -tuple we see that

$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 $x_1=x'_1,\cdots,x_m=x'_m$ and the conclusion follows.

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

$f\left(x_1\right)=n_1,\cdots,f\left(x_m\right)=n_m$ . But from this we see that for the above $x_1,\cdots,x_m$ that $\left(x_1,\cdots,x_m\right)\in\prod_{\jmath=1}^m X_\jmath$ and $\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 $\hat{f}$ 's surjectivity.

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

Is that correct? Thank you VERY much in advance for taking the time to read this.

**Moo** · December 23rd 2009, 12:06 AM

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

**Drexel28** · December 23rd 2009, 12:09 AM

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

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

Regardless, thank you very much Moo.

Thread: Countability

LinkBack

Thread Tools

Display

Countability

Similar Math Help Forum Discussions

countability of a set

Countability

Bijection - Countability

Countability

Countability

Search Tags