Results 1 to 5 of 5

Math Help - Cardinality

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    57

    Cardinality

    Can anyone tell me how I could show that the following set is countable?

    Natural numbers and the integers not divisible by 3?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by vexiked View Post
    Can anyone tell me how I could show that the following set is countable?

    Natural numbers and the integers not divisible by 3?
    Recall the theorem that the union of countable sets is countable (in fact, the countable union of countable sets is countable).

    note that the set we wish to prove is countable can be written as \mathbb{N} \cup \{ 3k + 1 \mid k < 0,~ k \in \mathbb{Z} \} \cup \{ 3n + 2 \mid n < 0,~n \in \mathbb{Z} \}

    now show that each of these are countable, shouldn't be that hard. then apply the theorem

    you can show a set is countable by showing that there exists a bijection between the set and the natural numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    57
    I'm sorry but I don't follow. All I have to do is find a function that will ouput all integers not divisible by 3? Maybe an example would push me in the right direction. Thanks for the help!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by vexiked View Post
    I'm sorry but I don't follow. All I have to do is find a function that will ouput all integers not divisible by 3? Maybe an example would push me in the right direction. Thanks for the help!
    for each set that you want to show is countable, find a one-to-one and onto function from the natural numbers to the set.


    example, how to we know that the set of nonnegative even numbers is countable?

    well, let E be the set of nonnegative even numbers.

    the function f: \mathbb{N} \mapsto E given by f(x) = 2x for x \in \mathbb{N} is one-to-one and onto.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    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,

    You can consider only the negative integers not divisible by 3, because the positive ones would be in \mathbb{N}
    So they're in the form -3n-1 and -3n-2, for any n in \mathbb{N}

    Define the function :
    f(x)=\left\{\begin{array}{lll} 3x \text{ if } x \in \mathbb{N} \\<br />
-x \text{ if } \exists n \in \mathbb{N} ~:~ x=-3n-1 \\<br />
-x \text{ if } \exists n \in \mathbb{N} ~:~ x=-3n-2 \end{array} \right.

    prove that this is an injective function :P
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 05:36 PM
  5. Cardinality of a Set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 27th 2009, 03:33 PM

Search Tags


/mathhelpforum @mathhelpforum