>Puzzle 141. Give an example of a morphism in some category that has more than one left inverse.

>Puzzle 142. Give an example of a morphism in some category that has more than one right inverse.
Here's an interesting example I found on the arxiv that answers both questions.

Oh, I found an excellent example yesterday while reading up on sequences.

Let our category be sequences of natural numbers with the natural numbers as identity.

>We can start with standard definitions for left and right inverses. Namely, given a sequence \$$a(n)\$$ we say that a sequence \$$b(n)\$$ is a left inverse of a if the sequence \$$b(a(n))\$$ is the natural number sequence. I denote a left inverse sequence as \$$\mathrm{leftInv}(n)\$$. Correspondingly, a right inverse sequence is denoted as \$$\mathrm{rightInv}(n)\$$, and it satisfies the property that the composition sequence \$$a(\mathrm{rightInv}(n))\$$ is the natural numbers sequence. It goes without saying that the sequences \$$\mathrm{leftInv}(n)\$$ and \$$\mathrm{rightInv}(n)\$$ depend on the sequence \$$a\$$. I will sometimes use the notation \$$\mathrm{leftInv}(a)(n)\$$ and \$$\mathrm{rightInv}(a)(n)\$$ in cases where I need this dependency to be explicit.

>**Left inverse.** First we assume that \$$a(n)\$$ is positive. Next, if \$$a(n)\$$ takes the same value for two different indices \$$n\$$, then the left inverse sequence cannot be defined. If \$$a(n)\$$ doesn’t reach a number \$$K\$$ for any index \$$n\$$, then \$$\mathrm{leftInv}(K)\$$ could be any number. That is, in this case the left inverse isn’t defined uniquely.
From here, we see that we can define the left inverse uniquely only if \$$a(n)\$$ is a permutation of natural numbers and in this case the left inverse sequence is the reverse permutation.
Many of the interesting sequences are increasing. To be able to define a left inverse for an increasing sequence, we need this sequence not to take the same value for different indices. This requirement translates into a simple condition: our increasing sequence has to be strictly increasing. Suppose \$$a(n)\$$ is a strictly increasing sequence. In this case the left inverse sequence can be defined. It still might not be unique, or more precisely, it is guaranteed not to be unique unless \$$a\$$ is the sequence of natural numbers.
Each time the left inverse is not unique we have infinitely many left inverses. To enjoy some order in this chaos of left inverses I would like to restrict candidates for the left inverse to non-decreasing sequences. In this case we can define two special left inverse sequences: \$$\mathrm{minimalLeftInv}\$$ and \$$\mathrm{maximalLeftInv}\$$, called the minimal left inverse and the maximal left inverse correspondingly. We define them so that for any non-decreasing sequence \$$b(n)\$$, such that \$$b(n)\$$ is a left inverse of \$$a(n)\$$, the following equations are true:
\$$\mathrm{minimalLeftInv}(n) \leq b(n) \leq \mathrm{maximalLeftInv}(n)\$$.
It is easy to see that the \$$\mathrm{minimalLeftInv}(a)(n)\$$ is the number of elements in \$$a(n)\$$ that are less than or equal to \$$n\$$. Also the \$$\mathrm{maximalLeftInv}(a)(n)\$$ is the number of elements in a(n) that are less than \$$n)\$$, plus \$$1\$$. In particular, \$$\mathrm{maximalLeftInv}(a)(n)− \mathrm{minimalLeftInv}(a)(n)\$$ equals \$$0\$$ if \$$n)\$$ belongs to \$$a(n)\$$ and \$$1\$$ otherwise. From here trivially we get the following equations:
\$\mathrm{minimalLeftInv}(a)(n) + 1 \\\\ =\mathrm{maximalLeftInv}(a)(n) + \text{ characteristic function of } a(n) \\\\ =\mathrm{maximalLeftInv}v(n + 1)\$.

>\$$\cdots\$$

>*Right inverse.* Again we assume that a(n) is positive. It is easy to see that if \$$a(n)\$$ doesn’t reach a number \$$K\$$ for any index \$$n\$$, then the right inverse can’t be defined. If \$$a(n)\$$ takes the same value for two or more different indices \$$n\$$, then the right inverse sequence can reach only one of those index values (and we can choose which one). From here, we see that we can define the right inverse uniquely only if \$$a(n)\$$ is a permutation of natural numbers and in this case the right inverse sequence is the reverse permutation.
Suppose \$$a(n)\$$ is a sequence that reaches every natural number value. Therefore, the right inverse sequence can be defined. The right inverse sequence might not be unique, but we can try to define two special right inverse sequences:
\$$\mathrm{minimalRightInv}\$$ and \$$\mathrm{maximalRightInv}\$$, called the minimal and the maximal right inverse correspondingly. We define them so that for any sequence \$$b(n)\$$, such that \$$b(n)\$$ is a right inverse of \$$a(n)\$$, the following equations are true: \$$\mathrm{minimalRightInv}(n) \leq b(n) \leq \mathrm{maximalRightInv}(n)\$$. It is easy to see that \$$\mathrm{minimalRightInv}(n)\$$ is the smallest index \$$k\$$, such that \$$a(k) = n\$$. Also, \$$\mathrm{maximalRightInv}(n)\$$ is the largest index \$$k\$$, such that \$$a(k) = n\$$. It is easy to see that the minimal right inverse is always defined. At the same time, for the maximal right inverse to be defined, it is necessary and sufficient that \$$a(n)\$$ reaches every value a finite number of times.
Suppose that \$$a(n)\$$ is a non-decreasing sequence that reaches every natural number value a finite number of times. Then the maximal right inverse is defined and

>\$maximalRightInv(n) = minimalRightInv(n + 1) − 1.\$

>Suppose \$$a(n)\$$ is a strictly increasing sequence. Then both the minimal and maximal left inverses are defined. Moreover, both of them are non-decreasing sequences that reach every value a finite number of times. This means that we
can define the minimal and maximal right inverses on the sequences \$$\mathrm{minimalRightInv}(a)(n)\$$ and \$$\mathrm{maximalRightInv}(a)(n)\$$. The following properties are true:

>\$\mathrm{minimalRightInv}(\mathrm{minimalRightInv}(a))(n) = a(n)\\\\ \mathrm{maximalRightInv}(\mathrm{minimalRightInv}(a))(n) + 1 = a(n + 1)\\\\ \mathrm{minimalRightInv}(\mathrm{maximalRightInv}(a))(n + 1) = a(n) + 1\\\\ \mathrm{maximalRightInv}(\mathrm{maximalRightInv}(a))(n) = a(n). \$

- 'How to Create a New Integer Sequence,' Tanya Khovanova

https://arxiv.org/pdf/0712.2244.pdf