Results 1 to 6 of 6

Math Help - Infinite Sets

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    6

    Unhappy Infinite Sets

    I am trying to prove why N x N x N is countable. N being the natural numbers. I am wondering how it needs to be changed from just N x N. Help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by undmath11 View Post
    I am trying to prove why N x N x N is countable. N being the natural numbers. I am wondering how it needs to be changed from just N x N. Help!
    There are zillions of ways to do this.

    The easiest is to notice that f:\mathbb{N}^3\to \mathbb{N}:n\mapsto 2^n3^n5^n is an injection. Why does that help?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    6
    It means that it is one-to-one and the graph will hit all the natural numbers.... ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Since you have that NxN is countable, it follows that (NxN)xN is countable and that Nx(NxN) is countable. Just use these facts, for any sets S and T:

    If S is equinumerous with R, then SxT is equinumerous with RxT.

    If S is equinumerous with R, then TxS is equinumerous with TxR.

    In fact, for any natural number k, by induction, we may infer that

    Nx(N...xN) (i.e. "k number of times") is equinumerous with N
    and
    (N...xN)xN (i.e. "k number of times") is equinmumerous with N
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by MoeBlee View Post
    Since you have that NxN is countable, it follows that (NxN)xN is countable and that Nx(NxN) is countable. Just use these facts, for any sets S and T:

    If S is equinumerous with R, then SxT is equinumerous with RxT.

    If S is equinumerous with R, then TxS is equinumerous with TxR.

    In fact, for any natural number k, by induction, we may infer that

    Nx(N...xN) (i.e. "k number of times") is equinumerous with N
    and
    (N...xN)xN (i.e. "k number of times") is equinmumerous with N
    But isn't proving these facts the point of the exercise then? I know you know why they are correct, but does the OP?

    Of course:

    Spoiler:


    If you have that \left\{f_\alpha\right\}_{\alpha\in\mathcal{A}} is a set of bijections from the corresponding \left\{U_\alpha\right\}_{\alpha\in\mathcal{A}} to the corresponding \left\{V_\alpha\right\}_{\alpha\in\mathcal{A}} then \prod_{\alpha\in\mathcal{A}}f_\alpha:\prod_{\alpha  \in\mathcal{A}}U_\alpha\to\prod_{\alpha\in\mathcal  {A}}V_\alpha:\prod_{\alpha\in\mathcal{A}}\{x_\alph  a\}\mapsto\prod_{\alpha\in\mathcal{A}}\left\{f_\al  pha(x_\alpha)\right\} is a bijection. Or, for just the two case that MoeBlee stated just take x_1,x_2)\mapsto (f_1(x_1),f_2(x_2))" alt="f_1\times f_2:U_1\times U_2\to V_1\times V_2x_1,x_2)\mapsto (f_1(x_1),f_2(x_2))" />

    Prove it!

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Yes, it is always a question: What theorems have been proven previous to the stated exercise?

    I would think that in a set theory course (is this exercise from a set theory course?) the more basic theorem about Cartesian products would have been proven previously (and if it had not been, then it should be as soon as possible).

    My point would be that there's no reason for the exercise to mention 'N' specifically when the result is general anyway, unless the intent of the exercise was just to remind the student to apply the more general result to N in particular. Moreover, as a matter of "style" I'd prefer a proof that appeals to the more general principle than to one that appeals to specific properties of N (that is, all other things being equal, better to prove something in a general way).

    Anyway, the general theorem about Cartesian products is itself quite easy to prove just by putting the given bijections to their obvious use.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finite and infinite sets
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: August 6th 2011, 04:53 PM
  2. Infinite sets
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: March 13th 2011, 07:30 AM
  3. Proving that A~B then B~A for infinite sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 21st 2010, 11:11 AM
  4. Functions between Infinite Sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 8th 2010, 05:26 AM
  5. Bijection in infinite sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: May 25th 2008, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum