Imagine a set of 2D rectangles of different sizes; let's assume for the sake of
simplicity that no two rectangles in this set have *exactly* the same size.
Here is a sample set:

We'll say that box X **fits** inside box Y if we could physically enclose X
inside Y; in other words, if Y's dimensions are larger than X's. In this
example:

- Box A can fit inside box B, but not the other way around
- E can fit inside all other boxes, but no other box can fit inside it
- A, B, D, E can fit inside C, which itself cannot fit in any of the other boxes
- D cannot fit inside A or B; neither can A or B fit inside D

As we're going to see soon, in this case "fits" is a *partial order* on a set of
2D rectangular boxes, because even though we can order some of the boxes
relative to each other, some other pairs of boxes have no relative order among
themselves (for example A and D).

If all pairs of boxes in this set had relative ordering - for example, consider
the set without box D - we could define a *total order* on the set. Another
example for this is a set of 2D *squares* (rather than rectangles); as long
as all the squares in the set have unique sizes [1], we can always define a
total order on them because for any pair of squares either the first can fit in
the second, or vice versa.

## Mathematical definition of relations

To develop a mathematically sound approach to ordering, we'll have to dip our
feet into set theory and *relations*. We'll only be talking about binary
relations here.

Given a set A, a *relation on A* is a set of pairs with elements taken from A.
A bit more rigorously, given that is the set containing all
possible ordered pairs taken from A (a.k.a. the *Cartesian* product of A), then
R is a relation on A if it's a subset of , or .

For example, given the set , then:

Note that we explicitly defined the pairs to be *ordered*, meaning that (1,2)
and (2,1) are two distinct elements in this set.

By definition, any subset of is a relation on A. For example
. In
programming, we often use the term *predicate* to express a similar idea. A
predicate is a function with a binary outcome, and the correspondence to
relations is trivial - we just say that all pairs belonging to the relation
satisfy the predicate, and vice versa. If we defined a predicate `R(x,y)` to
be true if and only if `x==y`, we'd get the relation above.

A shortcut notation that will make definitions cleaner: we say when . In our example set 1R1, 2R2 and 3R3. This notation is a bit awkward, but it's the accepted standard in math; therefore I'm using it for consistency with other sources.

Besides, it becomes nicer when R is an operator. If we redefine R as `==`, it
becomes more natural: `1==1`, `2==2`, `3==3`. The equality relation is
a perfectly valid relation on a set - its elements are all the pairs where both
members are the same value.

## Properties of relations

There are a number of useful properties relations could have. Here are just a few that we'll need for the rest of the article; for a longer list, see the Wikipedia page.

**Reflexive**: every element in the set is related to itself, or
. The `==` relation shown above is
reflexive.

**Irreflexive**: no element in the set is related to itself, or
. For example if we define the `<` less than
relation on numbers, it's irreflexive since no number is less than itself.
In our boxes example, the "fits in" relation is irreflexive because no box can
fit inside itself.

**Transitive**: intuitively, "if x fits inside y, and y fits inside z, then x
fits inside z". Mathematically
.
The `<` relation on numbers is obviously transitive.

**Symmetric**: if x is related to y, then y is related to x. This might sound
obvious with the colloquial meaning of "related", but not in the mathematical
sense. Most relations we deal with aren't symmetric. The definition is
. For example, the relation `==`
is symmetric, but `<` is not symmetric.

**Antisymmetric**: if x is related to y, then y is *not* related to x unless
x and y are the same element; mathematically
.
For example, the relation (less than or equal) is antisymmetric;
if and also then it must be that x and y are
the same number. The relation `<` is also antisymmetric, though in the empty
sense because we won't be able to find any pair x and y to satisfy the left
side of the definition; in logic this is called *vacuously*.

## Partial order

There are two kinds of partial orders we can define - *weak* and *strong*. The
*weak* partial order is the more common one, so let's start with that. Whenever
I'm saying just "partial order", I'll mean a weak partial order.

A *weak partial order* (a.k.a. *non-strict*) is a relation on a set A that is
reflexive, transitive and antisymmetric. The relation on numbers is
a classical example:

- It is reflexive because for any number x we have
- It is transitive because given and , we know that
- It is antisymmetric because given and , we know that x and y are the same number

A *strong partial order* (a.k.a. *strict*) is a relation on a set A that is
irreflexive, transitive and antisymmetric. The difference between weak and
strong partial orders is reflexivity. In weak partial orders,
every element is related to itself; in strong partial orders, no element is
related to itself. The operator < on numbers is an example of strict
partial order, since it satisfies all the properties; while is
reflexive, < is irreflexive.

Our rectantular boxes with the "fits" relation is a good example to distinguish
between the two. We can only define a *strong* partial order on them, because
a box cannot fit inside itself.

Another good example is a morning dressing routine. The set of clothes to wear is {underwear, pants, jacket, shirt, left sock, right sock, left shoe, right shoe}, and the relation is "has to be worn before". The following drawing encodes the relation:

This kind of drawing is called a Hasse diagram, which is useful to graphically represent partially ordered sets [2]; the arrow represents the relation. For example, the arrow from "pants" to "left shoe" encodes that pants have to be worn before the left shoe.

Note that this relation is irreflextive, because it's meaningless to say that
"pants have to be worn before wearing pants". Therefore, the relation defines
a *strong* partial order on the set.

Similarly to the rectangular boxes example, the partial order here lets us order only some of the elements in the set w.r.t. each other. Some elements like socks and a shirt don't have an order defined.

## Total order

A total order is a partial order that has one additional property - any two elements in the set should be related. Mathematically:

While a partial order lets us order *some* elements in a set w.r.t. each other,
total order requires us to be able to order *all* elements in a set. In the
boxes example, we can't define a total order for rectangular boxes (there is
not "fits in" relation between boxes A and D, no matter which way we try).
We *can* define a total order between square boxes, however, as long as their
sizes are unique.

Neither can we define a total order for the dressing diagram shown above, because we can't say either "left socks have to be worn before shirts" or "shirts have to be worn before left socks".

## Examples from programming

Partial and total orders frequently come up in programming, especially when
thinking about sorts. Sorting an array usually implies finding some
*total order* on its elements. Tie breaking is important, but not always
possible. If there is no way to tell two elements apart, we cannot
mathematically come up with a total order, but we can still sort (and we do have
a weak partial order). This is where the distinction between regular and stable
sorts comes in.

Sometimes we're sorting non-linear structures, like dependency graphs in the dressing example from above. In these cases a total order is impossible, but we do have a partial order which can be useful to find a "valid" dressing order - a linear sequence of dressing steps that wouldn't violate any constraints. This can be done with topological sorting which finds a valid "linearization" of the dependency graph.

[1] | You may notice that saying "unique" when talking about sets can sound superfluous; after all, sets are defined to have distinct elements. That said, it's not clear what "distinct" means. In our case, distinct can refer to the complete identities of the boxes; for example, two boxes can have the exact same dimensions but different colors - so they are not the same as far as the set is concerned. Moreover, in programming identity is further moot and can be defined for specific types in specific ways. For these reasons I'm going to call out uniqueness explicitly to avoid confusion. |

[2] | A partially ordered set with R (or poset with R) is a set with
a relation R that is a partial order on it. |