Can you prove that this set is countable?

[Nylex]

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}

thanks!

 

[matt grime]

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?

 

[Nylex]

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

 

[matt grime]

So, you're statement is

$$\{ n \in \mathbb{N}\ Z : n \notin 3\mathbb{N} \}$$

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.

 

[Nylex]

sorry the Z was a typo.

the question explicitly asks for a suitable map as part of the proof

 

[matt grime]

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.

 

[HallsofIvy]

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?

 

[gravenewworld]

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.