Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Does it mean that the set of multiples or non-multiples of any natural number is always countable? –  user44375 Oct 11 '12 at 13:30
    
Yes. That is correct, except for non multiples of 1. –  Shahab Oct 11 '12 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. –  Carl Mummert Oct 11 '12 at 13:44

5 Answers 5

up vote 3 down vote accepted

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.

share|improve this answer
    
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$ –  LF4 Jul 16 '12 at 2:47
1  
$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. –  Robert Mastragostino Jul 16 '12 at 2:50
    
Thank you that makes so much sense now. –  LF4 Jul 16 '12 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. –  Robert Mastragostino Jul 16 '12 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}\}$$

share|improve this answer
    
Strictly speaking, the questions asks for a bijection between the positive integers and the set. –  William Jul 16 '12 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$.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.