# Countable sets?

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?

• Does it mean that the set of multiples or non-multiples of any natural number is always countable?
– user44375
Oct 11, 2012 at 13:30
• Yes. That is correct, except for non multiples of 1. Oct 11, 2012 at 13:33
• I would say set of non-multiples of $1$ is countable, as it is the empty set; it is just not countably infinite. You have to be very careful when talking about countability to check whether the person speaking treats finite sets as countable, because this is very common in the literature. Oct 11, 2012 at 13:44

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.

• Oh so the $a_n$ implies bijection the book wasn't very clear on that. This book isn't the greatest with how the course is structured. So my answer for 1 isn't correct since I have two functions? Should they be more like $3a_{n-2}+1, n > 3$ Jul 16, 2012 at 2:47
• $a_1=1,a_2=2,a_n=a_{n-2}+3,n>2$. The idea is that you have a bunch of arithmetic sequences with the same increment, as you've noticed. So set up all your initial terms, then just set up the recursion to increment all of them. Since none of them were divisible by $3$ originally, adding $3$ keeps it that way. Jul 16, 2012 at 2:50
• Thank you that makes so much sense now. Jul 16, 2012 at 3:06
• @LF4 to be clear your initial formulation was still correct. defining $a_{2n+1}=3n+1, a_{2n+2}=3n+2, n\geq 0$ generates the same sequence. Jul 16, 2012 at 3:22

If $a$ and $b$ are relatively prime, then the numbers divisible by $a$ but not by $b$ belong to the set $$\{\text{lcm}(a,b)k+a,\text{lcm}(a,b)k+2a, \ldots, \text{lcm}(a,b)k+(b-1)a : k \in \mathbb{Z}\}$$

• Strictly speaking, the questions asks for a bijection between the positive integers and the set. Jul 16, 2012 at 0:03

First of all, both are countable since they are a subsets of the integer which is countable.

Also the $3k + 1$ and $3k + 2$ that you mention does not exactly answer the question since the question asks for a bijection between the desired set and the positive integers. I will provide a bijection between the nonnegative integers and the desired set. You then just shift by one to get it between the positive integers.

For the first one, consider the function

$f(k) = \begin{cases} 1 & \quad k = 0 \\ 2 & \quad k = 2 \\ 3t + 1 & \quad k \neq 0,2 \text{ and } k = 4t \\ 3(-t) + 1 & \quad k \neq 0,2 \text{ and } k = 4t + 1 \\ 3(t) + 2 & \quad k \neq 0,2 \text{ and } k = 4t + 2 \\ 3(-t) + 2 & \quad k \neq 0,2 \text{ and } k = 4t + 3 \end{cases}$

This is a bijection between the nonnegative integers and the set of all integers not divisible by $3$.

For the other one, note that by a similar argument as for $3$, you can find a bijection between the set of all positive integers and numbers that are not divisible by $7$. Let $g$ be this bijection. The numbers that are divisible by $5$ but not divisible by $7$ take for the form $5k$ where 7 does not divide $k$. Hence $5g(k)$ is the desired bijection between the positive integers and the set of integers divisible by $5$ but not $7$.

Hint: On constructing the mapping $f(k)$: you want to include a term $5k$ to ensure divisibility by 5. You also want to skip every multiple of $35.$ This involves $k/35,$ but not quite.

There is a trivial way to get an explicit bijection $f_A$ between $\mathbb{N}$ and any infinite subset $A$ of $\mathbb{N}$, namely $$f_A(0) = \min (A)\\ f_A(k+1) = \min (A \setminus \{ f(0), \ldots, f(k)\})$$

So in your case you can do the following. Let $B \subseteq \mathbb{Z}$ be infinite. Write $B$ as the union of a set $N$ of negative integers and a set $P$ of nonnegative integers. Assuming both of these are infinite, define $$g(2k) = f_{P}(k)\\ g(2k+1) = -f_{-N}(k)$$ Then $g$ will be the desired bijection between $\mathbb{N}$ and $B$. As you can see you do not need a formula for the elements of the set $B$, you only need to know the sets $N$ and $P$ are infinite to construct a specific bijection in this way. By some small modifications you could also handle the case where one of $N$ or $P$ is finite.