This Friday we will record, and the following Friday we will release, a show on lattice structures.

The main underlying concept is that of a partial order. I’m going to use < as the symbol for an arbitrary partial order in what follows.

Partial Orders

Say we’ve got a set, and we’d like to talk about an ordering on that set. “Xavier is behind Yolanda in line,” for example. We could write that as

x < y

Now, if Xavier is behind Yolanda in line, and Yolanda is behind Zelda in line, we’ve got

x < y and y < z

and, you know from your many experiences standing in line, that x < z must also be true.

In general, a partial order is any ordering which satisfies 3 properties:

1) The ordering is reflexive.

Reflexive means that x < x. (Think of a reflection – x looking back at itself.) Our use of < doesn’t allow that, since Xavier is not behind himself in line. But we could modify that; let’s re-define x < y to mean “x is not further ahead of y in line”. It’s verbally clunky, but now we can use any theorems we can find about general partial orders, and it is true that Xavier is not further ahead of Xavier in line, so our re-defined partial order is reflexive.

2) Transitive

A transitive ordering means that the following is true for any x, y, z in the set we’re working with:

If x < y, and y < z, then x < z.

This is true for <, so we’re good.

That’s it! You’re already familiar with one partial ordering, which we might call “less than or equal to” and designate with the symbol <=. It is true that, say,

3 <= 3

because while 3 is not less than 3, it IS equal to 3. Transitivity is pretty obvious: 3 <= 5, 5 <= 7, and of course 3 <= 7.

And the relation is anti symmetric.  That is, IF x<y and y<x then x = y.

If an order satisfies the first two properties, we call it a quasi-order.  If it also satisfies the last one, then it is a partial order.

The Least Upper Bound

Given two elements x and y of a set X that has a partial order <, the least upper bound (lub) of x and y is the “smallest” element of X that is “at least as big” as both x and y.

For our people in line example, the lub is really easy. Suppose Xavier < Yolanda. Recall that by our redefinition, Yolanda < Yolanda. So

lub(Xavier, Yolanda) = Yolanda

because Xavier is no further ahead in line than Yolanda, and Yolanda is no further ahead in line than Yolanda.

In the standing-in-line partial order, it’s really easy to compute the lub, because it’s just the “biggest” of the given pair.

Our line happens to be not only a quasi order, but a partial order.   A total order has all of the above properties, but also has the following one. Every element is comparable.  That is, either x<y or y<x.  So, total orders are often called linear orders for obvious reasons.

Every total order is a partial order and ever partial order is a quisi order, but not every partial order is a total order, etc.

Primate Partial Orders

What started me on this post was suddenly thinking of two orderings that I think will give us two interesting and primate-y partial orders (with some tweaking).

The Ancestry Ordering

Given two animals x and y, let the least upper bound of x and y be their most recent common female ancestor. So, the lub of you and your sibling is your mom. We can generalize this to species without screwing things up too much. The least upper bound of you and a gorilla is a female animal living 7 million years ago.

I’ve phrased this in terms of least upper bounds without really defining the ordering, but it seems obvious that there’s a partial order in here somewhere.

The Trade Ordering

Let x < y denote “I am willing to trade you an x for a y.” I’m happy to trade you an x for an x, because it’s the same object. And surely, if you would trade x for y, and you would trade y for z, then you should trade x for z. (If you wouldn’t, you are in danger of being screwed by the money pump.) So the trade ordering is reflexive and transitive, therefore it is a partial ordering.

However, it is NOT a partial ordering! To see this, consider

$5 < sandwich

Remember, this means “I am willing to trade you $5 for the sandwich.” Perhaps I’m not that hungry right now, and so it currently is true that

sandwich < $5

because I am willing to make you a sandwich if you give me $5. However, it is NOT true that a sandwich IS $5.

Well that’s interesting…

Numbers are totally ordered. If x <= y and y <= x, then x = y. But as per the above example, goods and services are NOT totally ordered. So what I want to know is: What weird effects occur from projecting the non-total partial ordering of goods to the total partial ordering of currencies?

[ETA: I am totally wrong! A partial order is antisymmetric; it's preorderings (or quasiorderings) which are not antisymmetric. In partial orders, any two elements may simply not be related -- it is possible to have neither a < b nor b < a be true.

We'll hash this out on the podcast next Friday!]