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

Math Help - countable set, Q X Q

  1. #1
    Super Member
    Joined
    Sep 2008
    Posts
    607

    countable set, Q X Q

    I need a little help with this question, I understand that to show a set is countable you have to show that it has a some sort of injection / surjection to N or R, i.e sets that are know to be countable, but i am still not quite sure how to show this has a function relation to either sets?

    Any help appreciated.

    thank you

    p.s I need help with part b, I have done part a, although the diagram I drew does not help me understand the question any better.
    Attached Thumbnails Attached Thumbnails countable set, Q X Q-screen-shot-2013-11-05-20.48.54.png  
    Last edited by Tweety; November 5th 2013 at 11:57 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    708

    Re: countable set, Q X Q

    Since \mathbb{Q} is countable, define f:\mathbb{Q} \to \mathbb{N} to be any bijection. Then, define g: \mathbb{N}\times \mathbb{N} \to \mathbb{N} by g(m,n) = (2m-1)2^n.

    Show that g is a bijection.

    Then g\circ(f\times f) is a bijection from \mathbb{Q}\times\mathbb{Q} \to \mathbb{N}.
    Thanks from Tweety
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,423
    Thanks
    1331

    Re: countable set, Q X Q

    Have you already proved, or do you know, that Q, the set of all rational numbers, is countable? If so, then you know that you can label the rational numbers as \{q_2, q_2, q_3, ..., q_n, ...\}. Write an array with all rationals, in that order, horizontally along the top and all rationals, in that order, vertically on the left. In the cell, i horizontally, j vertically, we have the pair (q_i, q_j). Now zigzag through the array as is done for the proof that Q is countable.

    (That method can be used for a general proof that "If A and B are countable then A X B is countable.)
    Thanks from Tweety
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2008
    Posts
    607

    Re: countable set, Q X Q

    Quote Originally Posted by SlipEternal View Post
    Since \mathbb{Q} is countable, define f:\mathbb{Q} \to \mathbb{N} to be any bijection. Then, define g: \mathbb{N}\times \mathbb{N} \to \mathbb{N} by g(m,n) = (2m-1)2^n.

    Show that g is a bijection.

    Then g\circ(f\times f) is a bijection from \mathbb{Q}\times\mathbb{Q} \to \mathbb{N}.

    I follow your logic, but not sure 'how to show 'g' is a bijection?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: countable set, Q X Q

    Quote Originally Posted by Tweety View Post
    I follow your logic, but not sure 'how to show 'g' is a bijection?
    To prove that g is a bijection you must assume 0\notin\mathbb{N}.

    All you need to do is show that there is a injection.

    I suggest g : (m,n)\mapsto 2^m\cdot 3^n
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    708

    Re: countable set, Q X Q

    Quote Originally Posted by Tweety View Post
    I follow your logic, but not sure 'how to show 'g' is a bijection?
    g can be broken down component-wise into g_1(m) = 2m-1 and g_2(n) = 2^n. In other words, g_1 is a bijection between the set of positive integers and the set of odd positive integers. g_2 is a bijection between the set of natural numbers and the set of powers of 2. Every natural number can be expressed uniquely as 2^k m where k,m \in \mathbb{Z}, k\ge 0, m\ge 0, and 2 does not divide m. In other words, the number is broken into its "odd part" and its "even part". This is a very natural bijection from \mathbb{N}\times \mathbb{N} \to \mathbb{N}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    708

    Re: countable set, Q X Q

    One slight correction: to get bijectivity, you need g_2(n) = 2^{n-1}, so g(m,n) = (2m-1)2^{n-1}. Before, g was a bijection between \mathbb{N}\times \mathbb{N} and positive even integers. Allowing the exponent of 2 to be zero adds in all odd positive integers, as well.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: countable set, Q X Q

    g(m,n) = (2m-1)2^(n-1) maps (m,n) to a double infinity of integers, which you still have to show is countable, using the same method as post #3 , so you might as well use that right off the bat.

    EDIT:

    g maps (m,n) to a unique integer N. ok, but
    does N=(2m-1)2^(n-1) have a unque solution (m,n) for each N?
    Last edited by Hartlw; November 6th 2013 at 08:20 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    708

    Re: countable set, Q X Q

    Quote Originally Posted by Hartlw View Post
    g(m,n) = (2m-1)2^(n-1) maps (m,n) to a double infinity of integers, which you still have to show is countable, using the same method as post #3 , so you might as well use that right off the bat.
    We are not dealing with ordinal numbers. Double infinity does not exist as a cardinal number. I gave a specific method for showing the map is a bijection from \mathbb{N}\times \mathbb{N} to \mathbb{N}. It does not require the method in post #3, although that method would certainly work.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: countable set, Q X Q

    The following is from another post because I wasn't able to post it here.

    First off, previous reply with quote missed the EDIT.

    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+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    708

    Re: countable set, Q X Q

    Copied from the other thread:

    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.

    So, g is, indeed, a bijection as I stated.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: countable set, Q X Q

    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= ...-3,-2,-1,0,1,2,3.... (countable)
    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.
    Last edited by Hartlw; November 7th 2013 at 05:53 AM. Reason: add negative integers to z
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: countable set, Q X Q

    In the spirit of the earlier posts, I'll also take a shot at g:ZXZ->Z+

    g =(m+n) because multiple elements in a set don't count and m+x=n has a unique solution.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: countable set, Q X Q

    Actually, a less obtuse proof that (m+n) is countable comes from *Rudins' and other's counting scheme, (m+n) ls countable by arranging it in a Matrix form:

    2345678....
    3456789....
    456789......
    56789.....
    6789......

    and counting diagonally from upper left.

    *The elements (m,n) are countable by arranging them in matrix form, REGARDLESS of their value.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    708

    Re: countable set, Q X Q

    Quote Originally Posted by Hartlw View Post
    In the spirit of the earlier posts, I'll also take a shot at g:ZXZ->Z+

    g =(m+n) because multiple elements in a set don't count and m+x=n has a unique solution.
    As stated in another thread, this is a SURJECTION, not an INJECTION. So, this function does NOT show countability of the domain. It shows that the domain contains a countably infinite subset.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. Replies: 2
    Last Post: November 11th 2010, 04:56 AM
  3. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  4. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum