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.

  • $\begingroup$ 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. $\endgroup$ – CopyPasteIt Jul 1 at 11:27
  • $\begingroup$ The word commute works better than compose in the title. $\endgroup$ – 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}$.

| cite | improve this answer | |
  • $\begingroup$ I think you are saying to use induction? And that's why these are the only possible types of functions? (which also means my guess about an inverse is wrong, but that makes sense) $\endgroup$ – Burnsba Feb 24 at 16:18
  • $\begingroup$ 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)$. $\endgroup$ – Olivier Roche Feb 24 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.