I'm working on a math problem and I'm kind of stuck. I have to show whether a set is countable or uncountable, and then as the title implies I have to exhibit a one-to-one correspondence between that set and the set of positive integers.
The set I'm given is: Integers not divisible by 3.
So far I've worked out that with these two cases I can map all positive integers that are divisible by 3 to the positive integers (Z+):
Case n odd: 3((n-1)/2)+1
Case n even: 3(n/2)+2
However I'm missing all the negative integers that are divisible by 3, and I'm struggling to figure out how to map those to Z+.
Best Answer
I might do this in two steps:
First, show that there is a one-to-one correspondence between the natural numbers $\mathbb{N}$ (i.e. the positive integers), and the set of all integers. To do this, we could send the even natural numbers to the positive integers, and the odd natural numbers to the nonpositive integers, perhaps via the following bijection: $$ f : \mathbb{N} \to \mathbb{Z} \quad\text{defined by}\quad f(n) = \begin{cases} \frac{n}{2} & \text{if $n$ is even, and} \\ -\frac{n-1}{2} & \text{if $n$ is odd.} \\ \end{cases} $$ Thus we have a one-to-one correspondence between $\mathbb{Z}$ and $\mathbb{N}$.
Next, as you noted, integers that are not divisible by three can be divided into two groups: those that have remainder 1, and those that have remainder 2, when divided by three. Let's use the same trick: send the odd integers to numbers that have a remainder of 1, and the even integers to numbers that have a remainder 2.
To fix notation, let $S$ be the set of integers that are not divisible by three. Hence $$ S = \{ n \in \mathbb{Z} : n\ne 3k\text{ for some }k\in\mathbb{Z}\} = \underbrace{\{ 3k+1 : k\in\mathbb{Z}\}}_\text{remainder 1} \cup \underbrace{\{ 3k+2 : k\in\mathbb{Z} \}}_\text{remainder 2}. $$ As described above, we want to send even integers to the first set, and odd integers to the second set. We can do this via the following bijective map $$ g : \mathbb{Z} \to S \quad\text{defined by}\quad g(n) = \begin{cases} 3\frac{n}{2}+1 & \text{if $n$ is even, and} \\ 3\frac{n-1}{2}+2 & \text{if $n$ is odd.} \\ \end{cases} $$
We then get the desired one-to-one correspondence by composing the two functions. That is, the function $$ g\circ f : \mathbb{N} \to S $$ is a bijection (i.e. a one-to-one correspondence).