Page 1 of 2 12 LastLast
Results 1 to 15 of 17
Like Tree2Thanks

Math Help - map (m,n) to N

  1. #1
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    map (m,n) to N

    This is a reply to Post QXQ countable sets which the system won't let me rreply to.

    let g(m,n) = (2m-1)2^(n-1)

    Is this a 1-1 mapping to N? If it is, it proves the rational numbers are countable since (m,n) can be interpreted as rational numbers.

    g maps (m,n) to a unique even positive integer P. OK

    Given P, is there a unique (m,n) st P=2N=(2m-1)2^(n-1), or,
    N=(2m-1)2^(n-2), for any N? Obviously not because the left side can be even or odd and the right side is even for n>2.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: map (m,n) to N

    Any positive integer k can be represented uniquely as a product k = m\cdot 2^a with m,a \in \mathbb{Z}_{\ge 0} such that 2 does not divide m. In other words, m is the "odd" part of k and 2^a is the "even" part of k. Here (Link) is information on the "Odd Part" of a number. Here (Link) is information on the "Even Part" of a number. It is obvious that m\cdot 2^a \in \mathbb{N} for any choice of nonnegative integers m,a such that m is odd. Next, let m_1 2^{a_1} = m_2 2^{a_2} with m_1,m_2 odd positive integers and a_1,a_2 nonnegative integers. Since 2^{a_1} must divide m_2 2^{a_2} and 2 does not divide m_2, it must be that a_1 \le a_2. Similarly, since 2^{a_2} must divide m_1 2^{a_1} and 2 does not divide m_1, it must be that a_2 \le a_1. Hence, a_1 = a_2. Then, by cancellation, m_1 = m_2. This shows that g is one-to-one. To show that g is onto, let k be any natural number. Let a be the highest power of 2 that divides k. Since k is a natural number, a\ge 0. Let m = \dfrac{k}{2^a}. Now, g\left(\dfrac{m+1}{2},a+1\right) = k. Since m is an odd positive integer, m+1 is an even positive integer, so \dfrac{m+1}{2} is a positive integer. Since a is a nonnegative integer, a+1 is a positive integer. Hence, \left(\dfrac{m+1}{2},a+1\right) \in \mathbb{N}\times \mathbb{N}, so g is onto.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    I can't reply with quote and I can't copy first sentence.

    Referencing your first sentence, if k =3, what are a and m?

    By the way I couldn't understand the links. Even if I took the time, I do not think they are in the spirit of this question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: map (m,n) to N

    If k = 3, then follow the method I gave. What is the highest power of 2 that divides 3? It is 2^0. So, a = 0. Then, m = \dfrac{k}{2^a} = \dfrac{3}{2^0} = 3. So, g\left(\dfrac{3+1}{2},0+1\right) = g(2,1) = 3.

    Edit: Also, the links were there to give you the mathematical definitions of the "even part" and "odd part" of an integer. Definitions are necessary to mathematical understanding. So, I am not sure what "spirit" you were looking for, but definitions are intrinsic to any understanding of a problem.
    Last edited by SlipEternal; November 6th 2013 at 10:21 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1

    Re: map (m,n) to N

    Quote Originally Posted by Hartlw View Post
    let g(m,n) = (2m-1)2^{n-1}
    Is this a 1-1 mapping to N? If it is, it proves the rational numbers are countable since (m,n) can be interpreted as rational numbers.
    Consider that mapping to be \mathbb{Z}^+\times\mathbb{Z}^+\to\mathbb{Z}^+

    Note that \forall x\in\mathbb{Z}^+ it possible to write x as an odd number times a power of two,

    g(2,1)=3 and g(9,4)=136.

    So g is both one-to-one and onto.

    However, because each subset of a countable set is countable one-to-oneness is all we need.

    The mapping \mathbb{Z}^+\times\mathbb{Z}^+\to\mathbb{Z}^+ given by (m,n)\mapsto 2^m\cdot 3^n is easy to show is one-to-one.

    As a side bar, this is a useful theorem:
    There is an injection A\to B\text{ if and only if } there is a surjection B\to A.
    Thanks from topsquark and Hartlw
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    From Rudin:

    Theorem: Let A be a countable set and let Bn be the set of all n-tuples (a1,a2,..an) where ak belong to A. Then the Bn are countable.

    If A= Z = 0,1,2,3,4,5,6,…,
    points in the plane are a subset of B4 and therefore countable.

    Explanation: Any rational number can be expressed as (n1,n2) and any point in the plane is (r1,r2) = (n1,n2,n3,n4).

    The Theorem follows from B2 and induction. For B2, map (m,n) to elements amn of a matrix, which are countable (diagonally from upper left).



    Previous posts seem to be based on the principle that (m,n) is countable if g exists st g maps ZxZ 1-1 into an infinite sequence of integers, which can then be numbered, to give g:ZxZ->Z.

    For Ex, Plato gives g = 2m3n, which is 1-1 because:
    2p3q=2r3s -> 2p-r=3s-q -> even=odd -> p=r and q=s.

    (From original thread but partly relevant here).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    Since multiple entries in a set don't count, g=(m+n) maps Z+XZ+ to Z+.

    or ZXZ to Z+. Z=0,1,-1,2,-2,....

    EDIT: It's not a unique mapping, but it might be thought through. Sorry. Would cancel if I could, unless someone can dig me out.

    EDIT: Actually, I think I can dig myself out: given m and n, m+x=n has a unique solution.
    Last edited by Hartlw; November 8th 2013 at 07:43 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: map (m,n) to N

    Quote Originally Posted by Hartlw View Post
    Since multiple entries in a set don't count, g=(m+n) maps Z+XZ+ to Z+.

    or ZXZ to Z+. Z=0,1,-1,2,-2,....

    EDIT: It's not a unique mapping, but it might be thought through. Sorry. Would cancel if I could, unless someone can dig me out.

    EDIT: Actually, I think I can dig myself out: given m and n, m+x=n has a unique solution.
    The existence of a surjection shows that the cardinality of the domain is at least as large as the cardinality of the range. The existence of an injection shows that the cardinality of the domain is no greater than the cardinality of the range. You provided a surjection, which does not show that the domain is countable.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    Damn, now the system let's me respond after I started a separate thread, which isn't that bad since it's a topic in itself. Oh well. In response to last post above which I can't reply to with quote:

    Slipstream has a valid point. My reason for g = (m+n) is as follow

    m+n maps Z+ to {2,3,3,4,4,4,5,5,5,5,.....) which is equal to {2,3,4,5,.....} and hence has the same size, cardinality, ie, is countable.

    But it involves an assumption which may be incorrect:

    {a,a,a,a,...........} is equal to {a}, ie, has the same size (cardinality, countability)

    (No problem with {a,a,a}={a})
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    Actually, the "size" question may be academic because, using Rudins' and other's counting scheme, (m+n) ls countable by arranging it in a Matrix form:

    2345678....
    3456789....
    456789......
    56789.....
    6789......
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    SlipEternal wrote: "The existence of a surjection shows that the cardinality of the domain is at least as large as the cardinality of the range. The existence of an injection shows that the cardinality of the domain is no greater than the cardinality of the range. You provided a surjection, which does not show that the domain is countable."

    Actually, any surjective map g(m,n) is countable:

    Proof: Let g(m,n) = amn. Then g(m,n) is countable because amn is countable (Rudin).

    So: g=(m+n) is countable because g is surjective.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: map (m,n) to N

    If a surjection were enough to show countability, then the map f:\mathbb{R} \to \mathbb{Z} defined by f(x) = \lfloor x \rfloor (this is the step function, which returns the greatest integer less than or equal to x, which is obviously a surjection) shows that \mathbb{R} is countable, which we know to be false. Therefore, no matter whose counting scheme you use (Rudin's or otherwise), showing the existence of a surjection to a countable set does not show that the domain is countable. It shows that the cardinality of the domain is at LEAST as large as the cardinality of the range. For example, there does not exist a surjection from the set of integers to the set of reals, so we know that the set of integers has a smaller cardinality than the set of reals. There does not exist any surjection from a finite set to an infinite set, so we know that infinite cardinalities exist. It is unknown whether or not there exists a set with cardinality greater than the cardinality of the set of integers, but less than the cardinality of the set of reals.

    So, to recap, your function g:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{N} \setminus \{1\} defined by g(m,n) = m+n is a surjection, which shows that \mathbb{Z}^+\times \mathbb{Z}^+ is no smaller than \mathbb{N}\setminus \{1\}. You provided a LOWER BOUND on the cardinality, not an upper bound. So, this does not show countability. It only shows that it contains a countably infinite subset.

    Edit: But, if you show that there exists a surjection from a set to a countable set, then show that the preimage of each element of the range is a finite subset of the domain, then you have a countable union of finite sets, which is countable.
    Last edited by SlipEternal; November 8th 2013 at 11:05 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: map (m,n) to N

    We are talking about g(m,n) where m,n are countable and g is surjective, to which Rudin applies.

    g(x) x real has absoluteley nothing to do with this.

    If you keep bringing up extraneous and irrelevant material this thread will never end.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: map (m,n) to N

    Quote Originally Posted by Hartlw View Post
    We are talking about g(m,n) where m,n are countable and g is surjective, to which Rudin applies.

    g(x) x real has absoluteley nothing to do with this.

    If you keep bringing up extraneous and irrelevant material this thread will never end.
    What does g(x) x real mean? I did not post anything about that. I gave an example of a surjection from an uncountable set to a countable set, and explained that does not prove the uncountable set is now countable. I think the issue is that you are trying to prove something unrelated to what I am trying to prove. You seem to be trying to prove that \mathbb{N} is countable by giving a surjection from a set of unknown cardinality to \mathbb{N}, then counting the number of elements in the image of the function. I am saying this is not helpful in any way to find the cardinality of \mathbb{N}\times \mathbb{N} and gave you several examples why not. If you truly believe that your method of proof is valid, then there is nothing more to discuss.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Nov 2013
    From
    Bestwebuys
    Posts
    6

    Re: map (m,n) to N

    Bài viết hữu ích!

    Văn pḥng phẩm, giấy photocopy, bút viết, b́a hồ sơ, và nhiều sản phẩm tiết kiệm hổ trợ công việc văn pḥng ★ ★ ★
    Vanphongpham.net 400 Trần Hưng Đạo, P.2, Q.5, Tp.Hồ Chí Minh Thứ 2 - 7 : 8:00am - 5:30pm
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Search Tags


/mathhelpforum @mathhelpforum