Results 1 to 3 of 3

Math Help - Countability

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    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 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Moo View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countability of a set
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 6th 2011, 04:18 AM
  2. Countability
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: February 15th 2010, 09:36 PM
  3. Bijection - Countability
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 20th 2009, 09:42 AM
  4. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 28th 2008, 11:49 AM
  5. Countability
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2008, 07:26 AM

Search Tags


/mathhelpforum @mathhelpforum