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

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:

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 or $$b 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$$.

• I think I follow the first paragraph but want to check my understanding. Supposing for a contradiction that we have some well-ordering that satisfies $s(n) = \min((n, +\infty])$ for each $n \in N$, we would have both $b = s(a) = \min((a, +\infty])$ (which implies $b > a$) as well as $a = s(b) = \min((b, +\infty])$ (which implies $a > b$), so that's a contradiction. So no such well-ordering can exist. Commented Jun 2, 2023 at 20:45
• Yes, thats correct. Commented Jun 3, 2023 at 14:16

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.

• I agree with everything you wrote in your answer, but I don't know how to make the leap from "this particular ordering is not well-founded" to "therefore there cannot exist any well-ordering such that $s(n) = \min((n, +\infty])$". I may be missing some obvious standard result. Commented May 29, 2023 at 8:58