# Showing a mapping has infinitely many solutions

Problem: Define a mapping $\gamma\colon\mathbb{N}\to\mathbb{N}$ such that for each $n\in\mathbb{N}$ the equation $\gamma(x)=n$ has infinitely many solutions.

Book solution: Let $p_n$ denote the $n$th prime ($p_1=2, p_2=3, \ldots$). Define $\gamma$ by $\gamma(p_n^k)=n$ for $k=1,2,3,\ldots$; $\gamma(m)$ can then be anything for $m$ not a prime power.

My solution: Define $\gamma$ by $\gamma(n\cdot\cos(\pi/2\cdot k))=n$ for $k=1,2,3,\ldots$. Doesn't this work? It seems like there are so many trivial ways to answer this problem correctly or am I missing something?

$\color{red}{\text{Edit: Concerning the book's solution:}}$ Suppose $\gamma(x)=5$. Then solutions are $$p_5^k=11^k=\underbrace{11,121,\ldots}_{\text{infinitely many}},$$ where there are evidently infinitely many solutions. Is my understanding correct?

• There are, indeed, many simple answers. But yours isn't clear. What's wanted is a single function $\gamma(x)$. I don't know whether you are defining a single function, or infinitely many functions, one for each $k$. – Gerry Myerson Mar 8 '15 at 11:31
• @GerryMyerson Is the book's clearer? – riddler Mar 8 '15 at 11:34
• To me, yes, it is. – Gerry Myerson Mar 8 '15 at 11:39
• In response to your edit: yes, your understanding certainly appears to be correct. – G. H. Faust Mar 9 '15 at 9:01

The books solution is very nice. Yours doesn't work, because $\cos(\frac{\pi}{2} \cdot k)$ will only produce a few different values as $k$ varies. So even though you've constructed a different equation that has infinite solutions (all the $k$s), the solutions to the new equation don't all produce distinct solutions to the original equation.

Here's how I would do it, in the style of the book's solution to your other question.

$\gamma(0) = 0,$

$\gamma(1) = 0, \gamma(2) = 1,$

$\gamma(3) = 0, \gamma(4) = 1, \gamma(5) = 2,$

$\gamma(6) = 0, \gamma(7) = 1, \gamma(8) = 2, \gamma(9) = 3,$

And so on.

• Or what would be the formula for $\gamma(k)=n$ in this case? Or is that a more difficult question? – riddler Mar 8 '15 at 12:04
• Not strictly. Before, the bound was just giving you a way to compute the value of the function. But it is related, in that a number of the form $\frac{n(n-1)}{2}$ will always be zero. It's still not a nice formula, but I think another way to express $\gamma(k)$ would be: $k - \frac{a(a-1)}{2}$, where $a$ is picked as large as possible without making the function negative. – G. H. Faust Mar 8 '15 at 12:08
• Thanks for your help. I'll digest this more thoroughly once I get some much needed sleep. I understand the book's solution now. Good to have other viewpoints though. Thanks! – riddler Mar 8 '15 at 12:16

$\newcommand{\N}[0]{\mathbb{N}}$The general recipe is to write $\N$ as the union of infinitely many infinite disjoint subsets $A_{n}$, for $n \in \N$, and then define $\gamma(x) = n$ for $x \in A_{n}$, that is, $A_{n} = \gamma^{-1}(\{ n \})$.

My favourite example, which comes from Hilbert's hotel, is to take, for $n \ge 1$ $$A_{n} = \{ x \in \N : x \equiv 2^{n-1} \pmod{2^{n}} \},$$ So $A_{1}$ are the odd numbers, $A_{2}$ are the numbers congruent to $2$ modulo $4$, etc

Using basic facts about cardinality, we can reduce the problem to finding a map $h:\mathbb{Q} \to \mathbb{N}$ such that $h(x) = n$ has infinitely many solutions for every $n\in \mathbb{N}$.

Let $g: \mathbb{Q} \to \mathbb{N}$ be any bijection between $\mathbb{Q}$ and $\mathbb{N}$. Let $h:\mathbb{Q} \to \mathbb{N}$ be the map that sends $\pm\frac{a}{b} \to a$ where $\frac{a}{b}$ is in lowest terms. Then the map $h\circ g^{-1}$ satisfies the desired properties.