Does the successor function imply order?

Question

My confusion is how order arises from the Peano axioms (wikipedia link).

From this question I'm not sure that "successor" means "greater than." It seems you could take $\mathbf{0}$ and then the successor could simply be (roughly) "produce a new element not seen before" and then (via the linked question) just name these items $1, 2, 3, ... $. From an outside perspective it seems fine to associate an ordering with these numbers, but it seems to beg the question on whether order is valid and what it "means" in PA.

I must be missing something simple, because arriving at the concept of order seems "obvious" but I'm just not seeing how it arises from the axioms given.

Answer 1

I think underlying this question is the assumption that "order" in PA corresponds to the intuitive notion of "magnitude". In particular, I note that the OP says

I'm not sure that "successor" means "greater than."

This is in fact a very good observation! In general the symbol $ < $ does not necessarily denote a comparison of sizes, and our convention of reading it aloud as "less than" is probably a source of a lot of confusion.

The symbol $<$ means "comes before" (or, if you prefer a single word, "precedes") -- and nothing more than that. $a<b$ means "$a$ comes before $b$". It does not mean that $a$ is "smaller" than $b$ in any sense. There are many ordered structures in which thinking of $<$ as denoting size is really unhelpful and potentially misleading; see Fields that can be ordered in more than one way for examples.

This detail is a source of confusion even in elementary contexts; students often have trouble with the language "$-5$ is less than $-2$", because "less than" connotes a comparison of magnitudes, and all we really mean when we write "$-5<-2$" is that $-5$ is to the left of $-2$ on a number line. It is solely a statement about order, and has nothing to do with size.

Answer 2

Well, there is immediately a partial order that comes from it. We can say that $x\preceq y$ if there is some non-negative integer $k$ such that $s^k(x)=y.$ Proving that this is transitive and antisymmetric are fairly straightforward tasks. If we require $k$ to be a positive integer, then it yields a strict partial order $\prec,$ which in the natural numbers can be proved to be total. Of course, that's a bit boot-strappy. What are integers if you don't know what natural numbers are?

Mauro Allegranza mentions an approach using Peano arithmetic in the comments above, but since Peano addition is recursively-defined, we need induction, so we need the natural numbers.

One way to get past these problems is to produce an explicit model of the natural numbers, such as that discussed here. However, depending on which set-theoretic axioms you take for granted, you may not be able to proceed in this way.

To get around this, we can instead begin with the relation consisting of all pairs $\langle x,s(x)\rangle$ such that $x$ is an element of the Peano set in question, then define $\prec$ to be its transitive closure on said Peano set, then define $\preceq$ to be the reflexive closure of $\prec$ on said Peano set. The trickiest part is proving totality of $\prec$ on the Peano set.

Answer 3

Alright, this is an interesting question that denotes mathematical maturity.

The clean, boring answer is that PA does not determine what order means - our logic would require additional axioms to deal with order.

The interesting follow up question: What axioms can we introduce that would allow us to talk about the usual order in the naturals.

I think the key insight to be had from this is the equivalence between a definition and axioms. In order to define and deal with new concepts, we need to introduce new axioms that set the rules of the math we are working with.

Answer 4

The answer to my title question, "Does the successor function imply order?" seems to be yes.

As Mauro ALLEGRANZA says in a comment:

$$ (x < y) \leftrightarrow \exists z(y = x + s(z)) $$

This works because of axioms

6. For every natural number $n$, $S(n)$ is a natural number.
7. For all natural numbers $m$ and $n$, $m = n$ if and only if $S(m) = S(n)$.

Consider if it were possible that some number $a$ was the same as it's successor: $a = S(a)$. Then the above relation would not hold due to a contradiction:

$$ (a < S(a)) \leftrightarrow \exists z(S(a) = a + S(z)) $$

Perhaps order could still be salvaged (i.e., without the above two axioms) with a different definition for the relation, but I'm not qualified to speculate.

Answer 5

The OP referenced an explicit example of a transformation of the (now given) natural numbers satisfying the Peano axioms. But given the standard successor function $S: n \mapsto n+1$ on $\Bbb N$, if $\beta$ is any bijection of $\Bbb N$ then

$\quad \displaystyle \beta^{-1} \circ S \circ \beta: \Bbb N \to \Bbb N $

satisfies the Peano axioms. So, you can 'algebraically rename' the elements to get more Peano transformations. (see my answer to that explicit example).

The raison d'être for the axioms is an abstract/foundational way of 'getting to the natural numbers', and the successor function does this by 'counting off the numbers' one by one.

To answer the OP's title question - yes:

Starting with the Peano sucessor function $S: \Bbb N \to \Bbb N$ (where, at the starting gate $\Bbb N$ is an abstract set), one can define a endorelation $\rho$ on $\Bbb N$ that is a total ordering on $\Bbb N$. You are now justified in using the symbol $\le$ for the relation $\rho$. As a next foundational step you can show that $(\Bbb N, \le)$ is a well-ordered set.

The program outlined in the above paragraph can be carried out (in say the $\text{ZF}$ framework) before defining addition of the natural numbers, in contrast to the technique used in the wiki article Peano axioms and commented on by Mauro ALLEGRANZA.

The OP's foundation tag is appropriate here and they have asked a good question.