Order

7 March 2024 (updated 7 March 2024)

% Remco Bloemen % 2015-08-26

\newcommand{\bindingOperator}[3]{\mathrm{#1}^{#3}_{#2}} \newcommand{\set}[1]{\mathcal #1} \newcommand{\nE}[2][]{\bindingOperator{∄}{#1}{#2}} \renewcommand{\A}[2][]{\bindingOperator{∀}{#1}{#2}}

Given a set $\set S$. Assume nothing of this set, other than that it may or may not have elements and that we can check if two elements are the same.

Think for example of a set of instances of a particular class.

I will now explain what it formally means to have an order between the instances. What different kinds of order there are and why it matters.

Relations

Suppose we have a function, taking two elements of this set and giving a boolean in return. We can formally write the type of this function as:

$$ f : \set S × \set S → 𝔹 $$

Such functions, return true or false given two elements, is called a ‘binary relation’. The equality operation on the elements of our set is an example.

In mathematics the function notation is often replaced with an infix notation. Sometimes, the relation is even seen as something different than a function. I disagree with this, I find the function concept very useful when dealing with programming languages. This whole confusion is the reason why C++ has weird special functions like operator==.

Other examples of such functions are ‘divides’ on integers, ‘orthogonal’ on vectors and ‘less than’ on numbers.

Strict partial order

A strict partial order is a binary relation $<$ with the following properties:

Irreflexivity:

$$ \nE[\set S]x \left(x < x\right( $$

Transitivity:

$$ \A[\set S]a\A[\set S]b\A[\set S]c\; \left(a < b\right( ∧ \left(b < c\right( → \left(a < c\right( $$

From this we can derive more properties, for example asymmetry:

$$ \A[\set S]a\A[\set S]b\; \left(a < b\right( → ¬\left(b < a\right( $$

PROOF: Take the transitivity property and with $c = a$: $\A[\set S] a\A[\set S]b\; \left(a < b\right( ∧ \left(b < a\right( → \left(a < a\right($ We can rephrase the irreflexivity as $\A[\set S]a\; ¬\left(a < a\right($ From the law of the excluded middle we then have $\left(a < a\right( ↔ ⊥$, substitute this: $\A[\set S]a\A[\set S]b\; \left(a < b\right( ∧ \left(b < a\right( → ⊥$ Which means that: $\A[\set S]a\A[\set S]b\; ¬ \left( \left(a < b\right( ∧ \left(b < a\right( \right($ $\A[\set S]a\A[\set S]b\; \left(a < b\right( → ¬ \left(b < a\right($ QED.

We can also define a non-strict partial order as

$$ \left(a ≤ b\right( ↔ \left(a < b\right( ∨ \left(a = b\right( $$

and introduce $>$ and $≥$ by flipping the arguments.

It is called a partial order because there can be incomparable objects. Some comparisons are inconclusive, we can have $a ≠ b$ but $a < b$ and $b < a$ can still be both false.

The partial order relation defines a directed acyclic graph over the elements of $\set S$. Conversely, any directed acyclic graph can be turned into a partial order by taking the transitive closure. For example, the divides relation on integers is a partial order, even though it might seem to have little to do with an order.

In particular, any tree structure is a partial order with its non-direct descendant of relation. For example, subset of, substring of, etc…

Strict total order

A strict total order is a strict partial order with an addition axiom:

Totality:

$$ \A[\set S]a\A[\set S]b\; \left(a ≠ b\right( → \left(a < b\right( ∨ \left(b < a\right( $$

That this implies only one of a < b and b < a is true is a consequence of the asymmetry property we have proven.

Strict well-order

An order is well-order if for any element there are only a finite number of elements less than it.

This has a number of interesting mathematical consequences:

Every non-empty subset has a least element
Every strictly decreasing sequence must terminate
Properties can be proven using transfinite induction

These orders allow induction over the element in the

$$ …,-3,-2,-1,0,1,2,3,… $$

has no lest element, but if we re-arrange it to be:

$$ 0,1,2,3,…,-1,-2,-3,… $$

it becomes a well-order of type ω+ω. This order can be easily defined in pseudo code

def a <' b:
	if (a < 0) ≠ (b < 0):
		return b < a
	else:
		return abs(a) < abs(b)

ω-order

The above example for the integers is still not as natural as I would like it to be. The problem is, it has two ellipsis (…). If I start counting from 0, I will never reach the negative numbers. But if we re-arrange it as:

$$ 0, -1, 1, -2, 2, -3, 3, … $$

For example with this function:

def a <' b:
	if abs(a) ≠ abs(b):
		return abs(a) < abs(b)
	else:
		return a < b

then it becomes countable!

A ω-order is countable. It can be brought in to one-on-one correspondence with the natural numbers without rearanging the order. As a consequence, these orders are perfectly concise Gödel numbering.

This conciseness is used in Google’s Protocol Buffers to store signed integers. They call it ZigZag encoding and found an elegant mapping between the integers and naturals by exploiting the twos-complement.

encode n: signed 64 bit
	return (n << 1) ^ (n >> 63)

Well-founded strict total order.

See: http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf