Show that for $\mathbb{N} = \{ 1, 2, 3, \ldots \}$, $s: \mathbb{N} \to \mathbb{N}$ where $s(n) = n + 1$ has infinitely many left inverses.

Question

The exact textbook question is:

Let $\mathbb{N}$ denote the set $\{1,2,3,\ldots,\}$ of natural numbers, and let $s:N \to N$ be the shift map, defined by $s(n) = n + 1$. Prove that $s$ has no right inverse, but that it has infinitely many left inverses.

The only piece of this throwing me off is the infinitely many left inverses part.

The map $s$ is injective and it clearly has a valid left inverse function:

$l(n) = n - 1$.

$l \circ s = \text{id}_\mathbb{N}$

However, I don't see how $s$ has infinitely many left inverses. It seems to have just one left inverse.

Answer 1

Hint: Your definition of $l(n)$ (which is otherwise correct) fails for $n=1$, so you need to define that case separately.

Answer 2

What Ross Millikan is saying is that you can put an arbitrary value for $l(1)$, e.g. if you set $l(1) = 42$ it is still a left inverse. That's why there are infinitely many of them.