# Find all functions that compose with the successor function

In Mac Lane/Birkhoff's Algebra, they spend some time discussing the natural numbers and give the Peano Axioms, roughly (from memory)

• $$\sigma$$ is injective
• 0 is not the successor of any element
• the principle of induction, which yields the natural numbers

My question is about an exercise at the end of the section which asks

For the usual successor function $$\sigma$$, find all functions $$\phi : \mathbb{N} \to \mathbb{N}$$ such that $$\sigma \phi = \phi \sigma$$.

My thought is that $$\phi$$ must commute with addition, which means that functions of the type $$\phi(x) = x + a$$ for some constant $$a \in \mathbb{N}$$. And then there are also inverses of $$\sigma$$ which would commute, and the identity function.

But are those the only functions? I'm not sure how to show that. I feel like the previous exercise is a hint:

For some $$\tau : \mathbb{N} \to \mathbb{N}$$ that satisfies the Peano Axioms, show $$\tau \beta = \beta \sigma$$ for some bijection $$\beta : \mathbb{N} \to \mathbb{N}$$.

I think (guessing here) this other exercise is showing that each model of $$\mathbb{N}$$ is unique (sorry, no model theory), for each function that satisfies the Peano Axioms, but I don't see how to apply this to the other exercise, especially since $$\phi$$ doesn't have to satisfy the Peano Axioms.

• See my 'push-along' algebra. I'm not satisfied with that exposition and plan to rework it with more theoretical details and highlighting the duality behind it all. – CopyPasteIt Jul 1 at 11:27
• The word commute works better than compose in the title. – CopyPasteIt Jul 1 at 11:35

The condition $$\sigma \phi = \phi \sigma$$ induces a recurrence relation, namely : $$\forall n, \phi(n + 1) = \phi(n) + 1$$ Hence, $$\phi$$ is entirely determined by the value $$\phi(0)$$ since $$\phi(n) = \phi(0) + n$$.
The functions $$\phi : \mathbb{N} \mapsto \mathbb{N}$$ satisfying $$\sigma \phi = \phi \sigma$$ are hence precisely the functions of the form $$x \mapsto x + a$$, $$a \in \mathbb{N}$$.
• No I'm not saying to use induction. I just noticed that any function satisfying $\sigma \phi = \phi \sigma$ must be of the form $x \mapsto x + \phi(0)$. – Olivier Roche Feb 24 at 19:10