Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
1) Integers not divisible by $3$.
2) Integers divisible by $5$ but not by $7$.
I figured out the first one so it was $3k+1$ or $3k+2$ but the second one has thrown me for a loop I was thinking it could be something like $5k$ but that will give me everything divisible by $5$ and $7$, can't figure out what to do about the not divisible by $7$.
Both are countable since I could go though and count the numbers that meet the requirements or am I wrong?
Best Answer
They are both indeed countable. for the second one, you can use the fact that all numbers divisible by $5$ and $7$ are divisible by $35$, so the set is equivalent to
"Integers divisible by $5$ but not by $35$".
Also, for the first part of the question (simply "are they countable?"), you can simply show that they're an infinite set, and that they're a subset of the integers. This immediately pins them as having cardinality $\aleph_0$.
EDIT: There's a fairly easy (though not very elegant) definition in terms of recursion:
$$a_1=5$$
$$a_2=10$$
$$a_3=15$$
$$a_4=20$$
$$a_5=25$$
$$a_6=30$$
$$a_n=a_{n-6}+35, n>6$$
The fact that you're listing them as $a_n$ implies bijection to $\mathbb{N}$. The first sequence works similarly.