How to compare Peano numbers?

Question

How do you compare Peano numbers?

I thought about something like this, but it does not seem to be correct:

$bigger(s(0),0)$

$bigger(x,y) \to bigger(s(x), s(y))$

Then I thought about using a summation:

$sum(x,0,x)$

$sum(x,y,k) \to sum(s(x),y,s(k))$

$sum(z,y,k) \to bigger(x,y)$

So how do you compare Peano numbers?

Answer 1

Henning Makholm's post is something like your second attempt. What follows here is something like your first attempt, a recursive definition analogous to the way $+$ and $\times$ are defined. They key point is that you must define the comparison of larger numbers in terms of the comparison of smaller ones.

$$\begin{align} 0\le y & \text{is true for every $y$} \\ S(x) \le 0 & \text{is false for every $x$} \\ S(x) \le S(y) & \text{is true if and only if $x\le y$} \end{align}$$

So for example to find whether $S(S(S(0))) \le S(S(0))$ you ask whether $S(S(0))\le S(0)$ and then whether $S(0)\le 0$. This is false by the second clause above, so $S(S(S(0))) \not\le S(S(0))$. The recursion must terminate in every case, because either the left-hand or the right-hand argument must eventually become 0. Note that every possible comparison falls under exactly one of these three cases: Either the left-hand argument is zero, or else the left-hand argument is a successor and the right-hand argument is zero, or both arguments are successors.

The first and second clauses here are like your $bigger(S(0), 0)$ idea, but you need to specify how $0$ compares with every other number in order to get the required base cases.

Once you have this you can define the other relations in terms of it. For example, $x<y$ can be defined to mean $(x\le y) \land \lnot( x= y)$.

This is of course equivalent to the other definition: one has $x\le y$ if and only if $\exists z. x+z=y$.

Answer 2

The usual definition of ordering in Peano Arithmetic is

$$ x \le y \quad\text{abbreviates}\quad \exists z : x+z=y $$

$$ x < y \quad\text{abbreviates}\quad x \le y \land x \ne y $$

If you're talking about the second-order Peano axioms, you need to start by defining addition recursively. (Addition is primitive in first-order PA).

There are minor, equivalent, variants, such as defining $x<y$ as $\exists z : x+Sz = y$.

---

Your style of presentation looks like you're concerned more with logic programming than usual quantifier-based first order logic. MJD's answer is good for that perspective.