Does every well-ordered set obeying the non-induction Peano axioms have a well-ordering compatible with the successor operation?

Question

Let $N$ be a well-ordered set together with a unary operation $s$ that obeys the following axioms (they are just the Peano axioms without induction):

1. $0 \in N$
2. for each $n \in N$ we have $s(n) \in N$
3. for every $n \in N$ we have $s(n) \ne 0$
4. for all $n,m \in N$, if $s(n) = s(m)$ then $n=m$.

Importantly, I do not assume that the well-order $\leq_N$ that comes with $N$ is compatible with the successor operation $s$.

From Exercise 1 in these notes I am aware that if I started with just a well-ordered set (but no successor operation), then I can define a successor by the formula $s(n) = \min((n, +\infty])$. I want to know if a kind of converse to this is possible.

To be more precise, my question is: does there always exist a well-ordering of $N$ (which is potentially very different from $\leq_N$) such that $s(n) = \min((n, +\infty])$? If so, please provide a proof. If not, please give a counterexample.

To anticipate a potential confusion: it is not possible to use the well-ordering $\leq_N$ in order to prove that induction holds in $N$, and then use induction to recursively define addition and from there define the usual ordering on the natural numbers. This is because, as I understand it, well-ordering only proves induction if we additionally assume that every non-zero element has a predecessor. I am specifically not assuming this additional property.

This question is similar to but distinct from the following two questions I was able to find on this site:

• Is defining a successor operation equivalent to defining a well-ordering operation?: Not the same because this question is kind of vague. In particular, it doesn't assume that $N$ is well-ordered, and doesn't assume $N$ satisfies the non-induction Peano axioms.
• Prove strict well-order from Peano successor function: This question doesn't assume $N$ is well-ordered. It also is asking if a particular ordering relation is a well-order, whereas I am asking if there is some ordering relation which is a well-order that obeys a certain property.

Answer 1

Your four conditions are satisfied by any injection $s:N\to N$ that omits $0$. In particular, $s$ may have cycles, which cannot happen for functions of the form you seek. To be concrete, we may take $N=\mathbb{N}\cup\{a,b\}$ and define $s$ as the usual succesor on $\mathbb{N}$ as well as $s(a)=b, s(b)=a$. This $s$ cannot be of your desired form since either $a<b$ or $b<a$ for any well-ordering on $N$.

With a bit more care we can show that any $s$ that restricts to a bijection of some nonempty subset of $N$ cannot be of this form. This actually turns out to be an equivalence though: Suppose $s$ is injective but not surjective when restricted to any invariant subset. Then, intuitively, $N$ must split into (possibly many) copies of $\mathbb{N}$, on each of which $s$ acts as the usual successor function. This can be seen like so: Consider the subset $A=N\setminus s(N)$. For each $a\in A$ we obtain an embedding $f_a:\mathbb{N}\to N$ by recursively defining $f_a(0)=a,f_a(n+1)=s(f(n))$. You can then check that

1. Each $f_a$ is an injection.
2. The image $N_a=f_a(\mathbb{N})$ is invariant under $s$.
3. The $N_a$ form a partition of $N$, i.e. $N=\bigcup_{a\in A}N_a$ and $N_a\cap N_b=\emptyset$ for $a\neq b$.

We can then define a well-order $\leq$ on $N$ as follows: Choose any well-order $\leq_A$ of $A$. For $n,m\in N$ we then set $n\leq m$ if either $n\in N_a,m\in N_b$ for $a<_A b$ or if $n,m\in N_a$ and $f_a^{-1}(n)\leq f_a^{-1}(m)$.

It is then straightforward to check that this is indeed a well-order and that $s(n)=\min(n,\infty)$ for all $n\in N$.

Answer 2

Let $N=\mathbb{N}$, with $s$ defined as follows:

• If $n$ is even then $s(n)=n+2$ (with "$+$" being meant in the usual sense).

• On the odds, $s$ induces the ordering $$...<11<7<3<1<5<9<13<17<...$$ (so e.g. $s(11)=7$ and $s(3)=1$).

This satisfies the non-induction Peano axioms but cannot come from a well-ordering on $N$, since the transitive closure of the relation "$x=s(y)$" is not well-founded.