## “I’ll swap you Grandma for a Pierolapithecus”

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 <...