A bijection $\mathbb Z \to \mathbb Z\setminus 5\mathbb Z$

Question

I came across a problem which asked to prove that $\mathbb Z\setminus 5\mathbb Z$ is countable. My first approach was to observe that $\mathbb Z\setminus 5\mathbb Z$ is an infinite subset of $\mathbb Z$ and hence is countable (as is shown here). However, since $\mathbb Z\setminus 5\mathbb Z$ is not too "ugly" I still wonder whether it is possible to have a somewhat more explicit bijection between $\mathbb Z$ and $\mathbb Z\setminus 5\mathbb Z$. I have no precise definition of explicit, but intuitively something not involving taking minima. I know this might be challenging, since the well ordering principle and induction are at the heart of arithmetic.

If the question were to find a bijection $f:\mathbb Z\to \mathbb Z\setminus 2\mathbb Z$ then $f(n)=2n+1$ would easily do the job. I don't see a way to adapt this reasoning to $\mathbb Z\setminus5\mathbb Z$ (or $\mathbb Z\setminus n\mathbb Z$ for any $n>2$ for that matter).

Answer 1

Claim: $f(n)=n+1+\lfloor \frac{n}{4} \rfloor$ is a bijection $\mathbb{Z} \to \mathbb{Z}\backslash 5\mathbb{Z}$

You can note that $f(0)=1$, $f(1)=2$, $f(2)=3$, $f(3)=4$, and $$f(k+4)=k+5+\left\lfloor \frac{k+4}{4} \right\rfloor=k+6+\left\lfloor \frac{k}{4} \right\rfloor=f(k)+5$$ So all the multiples of $5$ are skipped as function values.

Also note that if we replace $k$ by $k-4$ in the main equation, we get $f(k)-5=f(k-4)$, so multiples of $5$ are also skipped in the backwards direction.

Answer 2

There is an explicit, but kind of boring bijection: Consider the explicit bijection $\Bbb{N}\to\Bbb{Z}$ by $1\mapsto 0$, $2\mapsto 1$, $3\mapsto -1$, $4\mapsto 2$, $5\mapsto -2$ and so on - alternatingly filling up the positive and negative numbers. You can do the same for $\Bbb{N}\to \Bbb{Z}\setminus 5\Bbb{Z}$, by just skipping ahead whenever you meet a multiple of $5$. Now, taking the inverse of the first function and composing with the second function, you get an explicit bijection $\Bbb{Z}\to \Bbb{Z}\setminus 5\Bbb{Z}$.

Answer 3

Note that the function $\mathbb Z \to a+b\mathbb Z$ given by $n\mapsto a+bn$ is a bijection for $b\neq 0$. Now, observe that $\mathbb Z\setminus 5\mathbb Z = (1+5\mathbb Z)\sqcup (2+5\mathbb Z)\sqcup (3+5\mathbb Z)\sqcup (4+5\mathbb Z)\cong \mathbb Z \sqcup \mathbb Z \sqcup \mathbb Z \sqcup \mathbb Z$, and similarly $\mathbb Z = (4\mathbb Z)\sqcup (1+4\mathbb Z)\sqcup (2+4\mathbb Z)\sqcup (3+4\mathbb Z)\cong \mathbb Z \sqcup \mathbb Z \sqcup \mathbb Z \sqcup \mathbb Z$ as well.

Answer 4

For an explicit bijection in the spirit of your example: for each $n \in \mathbb{Z}$, use the division algorithm to write $n$ (uniquely) as $4a + b$ where $0 \le b \le 3$. Then the bijection will take $n \mapsto 5a + b + 1$. Since $1 \le b+1 \le 4$, we see that $5a + b + 1$ is guaranteed not to be a multiple of 5, so this does give a function $\mathbb{Z} \to \mathbb{Z} \setminus 5 \mathbb{Z}$. I will leave it as an exercise to find the inverse of this function.