Fundamental question concerning Partial/Total Orders

Question

Often when reading various texts involving total/partial orders, I come across statements like:

"...thus $\leq$ is a total order on $\mathbb{Z}$ when $a \leq b$ is given its usual meaning."

Is there a precise definition for said "meaning"? I've never actually seen one. Of course one could say $a \leq b$ $\iff$ $-a \geq -b$, but I feel this doesn't really address the issue.

I'm beginning to think that we aren't really giving $\geq$ meaning, we're in fact giving arbitrary integers meaning. For instance, perhaps we define $3$ as: $3 \in \mathbb{Z}$ such that $3 \neq 2,4$ and $2 \leq 3 \leq 4$. But this requires a definition of $2$, which, if we were to formulate in a similar way, would require a definition of $3$. Perhaps this is acceptable, but it seems somewhat circular to me.

Answer 1

Algebraic definition

Here is the typical algebraic way to define usual meaning: $\def\nn{\mathbb{N}}$ $\def\zz{\mathbb{Z}}$

Define "$a \le b$" to mean "$\exists n\in\nn\ ( a+n=b )$".

Note that this definition relies on having defined $\nn$ first, and then later $\zz$ with $\nn$ embedded into it. And when it gets down to $\nn$, you use the Peano Arithmetic axioms for it, which needs non-logical symbols $(\nn,0,1,+,\times)$.

Computational definition

You can define $\zz$ to be the collection of finite strings made up of decimal digits and an optional negative sign at the start. Then you can define $\le$ directly as an algorithm:

If $a$ has a negative sign but $b$ does not, then $a \le b$. Otherwise if both have negative signs, $a \le b$ is the same as $-b \le -a$, where "$-n$" means to toggle the presence of negative sign of $n$. So we can assume both $a,b$ have no negative sign. Pad $a,b$ with zeros at the start so that they are the same length. Go through them simultaneously digit by digit from start to end. Let the current digit in $a,b$ be $x,y$ respectively. If $x < y$, then $a \le b$. If $x > y$, then $\neg a \le b$. If $x = y$, then continue to the next digit. If all the digits are finished, then $a \le b$. All that is left is to define "$<$" for digits, which can be done by a table.

Note that the table used by the above definition would be much simpler if we use binary instead of decimal representation, but either way the idea is the same.

Comparison

It is certainly harder to prove that the computational definition is a total order! That is one main reason to use the algebraic definition. However, it is now obvious that the algebraic definition does not really answer the question, because it is nothing more than just pushing the question under the carpet by assuming the consistency of PA, that is, the existence of a model of PA. In contrast, the computational method is more concrete, since it is actually physically implemented on every computer/calculator in an equivalent form.

Answer 2

I'd agree with your assessment -- the natural numbers and $\le$ are such intertwined concepts for us that attempting to define one pretty much has to involve defining the other.

Here is one possible precise definition of your meaning -- the set-theoretic encoding of natural numbers. This is an effort to represent $\mathbb{N}$ using only sets.

We define

$$ \begin{aligned} 0 &= \{\}\\ n + 1 &= n \cup \{n\}\\ \end{aligned} $$

So each natural number contains all its predecessors. For example,

$$1 = \{\{\}\}$$ $$2 = \{\{\}, \{\{\}\}\}$$

Then we can define

$$x \le y \iff x \subseteq y$$

(Personally, I think this is cute, and interesting from a computer science perspective, but I think $\mathbb{N}$ is just as intuitive a concept as sets and see no reason to privilege them over it. But, it's fun to do.)