Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of countable sets

  1. Apr 8, 2005 #1
    hi there

    i just need a hint for this question please :

    By giving a suitable map to or from N (thats a natural number N) proving that the set
    {nEN | n is not divisible by 3}

    Last edited: Apr 8, 2005
  2. jcsd
  3. Apr 8, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I'm sorry, that doesn't make sense. What does E mean? What does nEN mean? Since N is apparently a natural number, I mean, rather than the set of natural numbers, what's Z? the integers?
  4. Apr 8, 2005 #3
    im sorry maybe i didnt make myself clear enough

    the N i am taking as the 'chalkboard' N used to signify the naturals
    nEN meaning 'n' is an element of N
  5. Apr 8, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    So, you're statement is

    [tex] \{ n \in \mathbb{N}\ Z : n \notin 3\mathbb{N} \}[/tex]

    still what does that Z signify? And filling in, (you ask us to prove something but don't state what exactly), are you're asking for an explicit bijection between the naturals and the set of naturals not divisible by 3? I only ask as there is no need to write down a bijection. The set is an infinite subset of the Naturals and is thus countably infinite, hence in bijection with N.
  6. Apr 8, 2005 #5
    sorry the Z was a typo.

    the question explicitly asks for a suitable map as part of the proof
  7. Apr 8, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    OK. The map is, as always in these questions, since the set in question is a subset of N, we can order its elements using the ordering of N:

    x(1) < x(2) <x(3)

    since the subset is not finite, this produces an infinite string indexed by N. The map

    n ---> x(n)

    is a bijection from N to the subset in question.
  8. Apr 8, 2005 #7


    User Avatar
    Staff Emeritus
    Science Advisor

    matt grime's method surely works. Perhaps because I am not a "mathematically sophisticated" as he is, I didn't think of doing it that way. What I did was think, "All natural numbers that are NOT divisible by 3 are of the form 3n-1 and 3n- 2 (for n a positive integer). Since those are two distinct sets let's try mapping even numbers into one and odd numbers into the other:

    If m is even, f(m)= 3(m/2)- 1, if m is odd, f(m)= 3((m+1)/2)- 2.
    That means f(1)= 3((1+1)/2)- 2= 1, f(2)= 3(2/2)-1= 2, f(3)= 3((3+1)/2)-2= 4,
    f(4)= 3(4/2)-1= 5, f(5)= 3((5+1)/2)- 2= 7, etc. Seems to work!

    Nylex, can you prove that f is a bijection?
  9. Apr 8, 2005 #8
    If a set A is countable than any subset B of a countable set will also be countable (theorem). The set you are descrbing is a subset of the naturals, and therefore countable. You have the set N/{3,6,9,12,15,.......} which is a subset of the naturals and therefore countable. There is no need to find a bijection to show that the set is countable if you don't have to.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?