Results 1 to 14 of 14

Math Help - Show that the sets are countable:

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    71

    Show that the sets are countable:

    (a) {1,3,5,7..}

    (b) {0,1,4,9..}

    I know that by definition a set S is countable if there exists an injective function f: S to N..

    I also know that if f is also surjective (so bijective) then the set is coutably infinite.


    But I don't know how to PROVE IT!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    Have I proved it if I say

    f: Natural numbers to S f(n) = 2n-1

    ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    f: Natural numbers to S f(n) = 2n-1
    According to your definition, you need a function from S to \mathbb{N}... But yes, f:\mathbb{N}\to S defined by f(n)=2n+1 is a bijection for (a). Note that if 0 in considered a natural number (it varies by country ), then you need 2n+1, not 2n-1. You need to show that f is a bijection by proving that it is an injection and a surjection. Then, from a general theorem, you know that the inverse function exists and it is also a bijection. It is also easy to write this inverse function explicitly.

    The set in (b) seems to be the set of squares of all natural numbers, so this tells you what the bijection is.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Looking at question b), I would guess that the author is using the convention that \mathbb{N}=\{0,1,2,\cdots\}.
    That is, zero is the first natural number.
    f(n)=n^2 is a bijection in that case.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    Quote Originally Posted by emakarov View Post
    According to your definition, you need a function from S to \mathbb{N}... But yes, f:\mathbb{N}\to S defined by f(n)=2n+1 is a bijection for (a). Note that if 0 in considered a natural number (it varies by country ), then you need 2n+1, not 2n-1. You need to show that f is a bijection by proving that it is an injection and a surjection. Then, from a general theorem, you know that the inverse function exists and it is also a bijection. It is also easy to write this inverse function explicitly.

    The set in (b) seems to be the set of squares of all natural numbers, so this tells you what the bijection is.
    Sorry I don't quite understand. Are you saying that I haven't proved it yet? I need to show that it is a bijection right?

    Also we have learnt N to be 1,2,3, etc not including 0.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    To prove 2n+1 is injective:

    f(n1) = f(n2) so 2(n1) + 1 = 2(n2) + 2
    2(n1) = 2(n2) so n1 = n2

    This proves it's an injection?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    If your text book uses \mathBB{N}=\{1,2,3,\cdots\}
    then f(n)=2n-1 works for part a) and g(n)=(n-1)^2 works for part b).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Have I proved it if I say

    f: Natural numbers to S f(n) = 2n-1
    Defining a function f does not prove anything. It's the properties of f with respect to S and N that mean something, so they have to be proved.

    I need to show that it is a bijection right?
    Yes. Also note, as I said, that proving that f : N -> S is a bijection is not a proof "by definition" that S is countable. Since your definition talks about a function S -> N, you need to make an extra step by saying that a bijection N -> S implies the existence of a bijection S -> N. It may be easier to define a bijection S -> N to begin with.

    To prove 2n+1 is injective:

    f(n1) = f(n2) so 2(n1) + 1 = 2(n2) + 1
    2(n1) = 2(n2) so n1 = n2

    This proves it's an injection?
    Yes, though, as Plato pointed out, you were right in defining f(n) = 2n - 1.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    Quote Originally Posted by Plato View Post
    If your text book uses \mathBB{N}=\{1,2,3,\cdots\}
    then f(n)=2n-1 works for part a) and g(n)=(n-1)^2 works for part b).
    I meant 2n-1. Is my proof of injection correct? Or is there more to it?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    Thankyou. So now showing that it is surjective.

    Let y = (y+1)/2

    f(2n-1) = 2 [(y+1)/2] -1

    Sof(2n-1) = y

    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    So now showing that it is surjective.

    Let n = (y+1)/2

    f(2n-1) = 2 [(y+1)/2] -1

    Sof(2n-1) = y

    Is this correct?
    Yes. It is easier, though, to define g: S -> N by g(y) = (y + 1) / 2 and to prove that it is an injection: this is all you need to prove that S is countable according to your definition. For every y in S, g(y) is indeed a natural number because y is odd, and so y + 1 is even. Also, for every y1, y2 in S, (y1 + 1) / 2 = (y2 + 1) / 2 implies y1 + 1 = y2 + 1 and so y1 = y2, so g is injective.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    Quote Originally Posted by Plato View Post
    If your text book uses \mathBB{N}=\{1,2,3,\cdots\}
    then f(n)=2n-1 works for part a) and g(n)=(n-1)^2 works for part b).
    Wait a minute. For (b) (n-1)^2 is not injective because for say n = 4 an n = -2 both give the function equalling 9...

    So how is this one done? I can't prove it's injective...
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by chr91 View Post
    Wait a minute. For (b) (n-1)^2 is not injective because for say n = 4 an n = -2
    Come on. Of course it is injective.

    -2\notin \mathbb{N}. There are no negative numbers in \mathbb{N}.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Oct 2010
    Posts
    71
    Quote Originally Posted by Plato View Post
    Come on. Of course it is injective.

    -2\notin \mathbb{N}. There are no negative numbers in \mathbb{N}.
    Oh yeh. I suppose I got confused as we learnt that x^2 is not injective but that was for all real numbers..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 07:14 AM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 02:59 PM
  3. Replies: 1
    Last Post: February 9th 2010, 02:51 PM
  4. Show countable sets.
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: May 18th 2009, 10:10 PM
  5. Replies: 11
    Last Post: October 11th 2008, 07:49 PM

Search Tags


/mathhelpforum @mathhelpforum