Prove existence of a function $f:\Bbb Z^+ \to \Bbb Z^+$ such that for any $a,b,c$ there exists $n$ such that $f(an+b)=c$ I'm trying to solve the following exercise from Velleman's "How to Prove it" book:
Prove that there is a function $f:\Bbb Z^+ \to \Bbb Z^+$ such that for all positive integers $a, b$ and $c$ there is some positive integer $n$ such that $f(an+b) = c$.
I have been trying to use the equinumerous theorems between family of functions, but without success. Could anyone give me a hint on how to approach this problem?
 A: Hint: There are only countably many triples of positive integers $(a,b,c)$.  So, try defining values of $f$ one by one, in each step handling one of the triples.
A: Note that triples of the form $(a,b,c)$ for $a,b,c\in\mathbb{N}$ are countable. Thus, there exists a bijection between triples and the natural numbers. Let $S(n):\mathbb{N}\to (a,b,c)\in\mathbb{N}^{3}$ be any such bijection and define
$$\omega(n)=\omega(n-1)[S_1(n-1)+1]S_2(n-1)$$
where $\omega(1)=1$ (where $S_i(n)$ is the $i$th entry of the $n$th triplet). We will now show
$$S_1(n-1)\omega(n-1)+S_2(n-1)<S_1(n)\omega(n)+S_2(n)$$
For the base case, note that
$$S_1(2)\omega(2)+S_2(2)=S_1(2)\bigg[\omega(1)[S_1(1)+1]S_2(1)\bigg]+S_2(2)$$
$$=S_1(2)[S_1(1)+1]S_2(1)+S_2(2)=S_1(2)S_1(1)S_2(1)+S_1(2)S_2(1)+S_2(1)$$
$$>S_1(1)+S_1(2)=S_1(1)\omega(1)+S_2(1)$$
For the inductive step, we have
$$S_1(n)\omega(n)+S_2(n)=S_1(n)\bigg[ \omega(n-1) [S_1(n-1)+1]S_2(n-1)\bigg]+S_2(n)$$
$$=S_1(n) \omega(n-1) S_1(n-1)S_2(n-1)+S_1(n) \omega(n-1)S_2(n-1)+S_2(n)$$
$$> S_1(n-1)\omega(n-1)+S_2(n-1)$$
We conclude that for $i\neq j$
$$S_1(i)\omega(i)+S_2(i)\neq S_1(j)\omega(j)+S_2(j)$$
We now define the function
$$f(m)=\begin{cases} 
      S_3(m)&& m=S_1(n)\omega(n)+S_2(n)\text{ for }n\in\mathbb{N}\\
      0&& \text{otherwise}
   \end{cases}$$
