April 16, 2001
Eric Rasmusen, erasmuse@indiana.edu
These are notes by someone learning the material, so they may well
contain mistakes and naive comments.
LATTICE THEORY NOTES
Lattice theory is the mathematics of ordering, of rankings from
highest to lowest. Thus, it does not require us to measure distances
between objects. That is the big difference from working with real
numbers-- no metric is needed for lattices.
To define a lattice you need a set of objects and a partial
ordering on them. Then we will use the ordering to impose some
requirements on what objects are in the set if it is be a lattice.
These requirements need for us to define a minimum and maximum bounds
concept called "meet" and "join".
Here, we will only be concerned with one-dimensional ordering-- is x
greater than y, less, equal, or unrankable relative to y? I can
imagine a theory based on N rankings in N dimensions for any single
pair x and y, and probably mathematicians have come up with such a
theory, but we won't deal with it here.
(1) PARTIAL ORDERING:
A relation, >=, on a set is a partial ordering if it is a
(1) Pre-order --i.e. it is
(a) reflexive. x >= x) and
(b) transitive. x >= y >= z implies x >= z.
and it is
(2) Antisymmetric. x >= y and y >= x implies x >= y.
Antisymmetry says that if two elements in our set are both
"greater than or equal" to each other, then they must be the same
element. Put differently, a partial ordering cannot result in two
elements being different but equal. Antisymmetry is thus a
requirement of the relation >=, restricting the kind of orders that we
will let into the category "partial order", not a definition of
"equals". Antisymmetry says that a partial ordering cannot assign
the same ranking to two elements of a set (though it can refuse to
give one a ranking). No ties are allowed.
If you do not want to impose antisymmetry, you can set up lattices
using "equivalence classes"-- an ordering with just the requirement
(1)-- but that is not standard.
It seems to me that defining a partial ordering using the symbol ">"
and the word "greater" would be
better than ">=" and "greater than or equal to" (by being
narrower but still correct), since no two
different elements of the set are allowed to be equal to each other
anyway. But that isn't how it's done. Instead, the symbol ">" is
defined later, as pertaining to two elements that are not the same but
are rankable.
It is important to note that the ordering is "partial", rather than
"total", because there may exist elements x and y that can't be put
in order: neither x >= y nor y >= x. We do not require that a partial
order be able to rank any two elements of the set. I find it easy to
slip into thinking that "partial" refers to the ranking being greater
than *or equal to*, but that is not what the "partial" is referring
to.
Curiously, a lattice can also be defined in algebra-style, as a set
with two operations, Meet and Join, which have certain properties such
as commutation, and the algebra definition is equivalent to the
ordering one. For details,see Chapter 1 of the free text on the web,A
Course in Universal Algebra: The Millennium Edition, by Stanley N.
Burris and H.P. Sankappanavar,
http://www.thoralf.uwaterloo.ca/htdocs/ualg.html (accessed April 11,
2001).
(2) APPLICATION OF PARTIAL ORDERINGS TO A SET:
Suppose our set is made up of objects which are two-vectors, of the
form (z_1, z_2). It might have just two elements:
SET 1:
x= (.2, .8)
y = (.7, .3)
Which is bigger? That depends on how you define "bigger",
which is what defining a partial order is all about.
Here are some possible partial orders, which use the
natural ranking of real numbers to rank the components, so
.7 >= .2, for example.
COMPONENT-WISE: x >=y iff x_1 >= y_1 and x_2 >= y_2.
According to component-wise ordering, x and y can't be ranked
relative to each other.
This is the least debatable, weakest, kind of ordering.
Only a perverse person would deny that x>=y if x's
components both exceed y's. But of course it will often
leave elements unranked relative to each other.
FIRST COMPONENT: x >=y if x_1 >= y_1. According to
this, x >=y.
MIXED: x >=y if x_1 >= y_1 and x_2 <= y_2. According
to this, x >=y.
PRODUCT: x >=y if x_1*x_2 >= y_1*y_2. According to
this, y >=x.
Note that if we change what is in the set, these
definitions can cease to be partial orders. Suppose we add a
third element,
w = (.8,.2).
Now the PRODUCT relation is no longer a partial order
because it would say that w=x, but w and x are different
elements of the set.
If we add
v= (.2, .3)
then the First Component ordering ceases to be a partial
order, because it says v=x, but v and x are different
elements of the set.
The componentwise ordering is what I'll use in the rest of these
notes.
Note, too, that the elements of the set do not have to be
vectors of identical dimensionality. They could be a mix of
2- and 3-vectors, or functions, or whatever you like.
Fancier objects will require fancier partial orders, though.
(3) MEET AND JOIN.
Once we have a partial order, it is possible to define a
maximum element of the set. The obvious way, though-- to
just pick whichever element of the set comes out biggest
under the partial order-- is unsatisfactory. To be sure,
transitivity and anti-symmetry of the partial order means
that we may have quite a nice sequence of ranked elements,
with one clearly the biggest. (And even if we didn't have
antisymmetry, so some objects were tied, that would be OK--
we'd just have multiple maxima.) But we might not, and that
obvious way turns out to be incoherent. To see that,
consider the set of three elements and apply the
componentwise partial order to it:
SET 2:
x= (.2, .8)
y = (.7, .3)
h= (.1, .3)
Pretty clearly, h is the minimum. It is smaller in both components
than x. How about h and y? In the second component,.3, h is tied
with y.
Nonetheless is true that y >= h, while it is not true that h >= y, so
under our partial order, y is definitely bigger.
What is the maximum of the set? x is bigger than h, so
maybe you'd like to say x is the maximum. But y is also
bigger than h, and x and y can't be ranked relative to each
other. So we can't just say x is the maximum. Rather, there
are two sensible conclusions, depending on two sensible
definitions:
(a) x and y are both maxima, because neither one is less
than any other element.
(b) There is no maximum, because no element is greater than
every other element.
Using definition (a) being the maximum element of the set doesn't
carry much glory in this world, and won't bear much weight in
propositions. Using definition (b), the maximum usually won't exist,
and so is not a very useful concept either.
Instead, what is useful is to define an upper bound to
the size of elements in the set. We should be able to
pick some object Q, not necessarily an element of the set,
which is definitely greater than or equal to anything in
the set. Thus, though we may not be able to say that the
maximum, x, is bigger than some other element, y, we can
say that Q is bigger than x and y (or at least equal to
them).
Thus, we define:
Q= JOIN (x, y) = least upper bound (x,y)= smallest object
(under our partial order) that is greater than or equal to
x and y.
It could be that no such object exists in the world we have defined,
either inside or outside of our set. So the join need not always
exist.
In the same way, it is useful to define and have a term for
a lower bound to a set. That will be the
MEET (x, y) = greatest lower bound (x,y)= largest object
(under our partial order) that is less than or equal to
x and y.
The meet and join could be defined over an entire set rather than
just two elements: MEET(S). Or, if you want to talk about an upper
bound for the set you could say something like "The maximum of join
(x,y) for any two element x and y of the set." I will here refer to
the meet and join defined over the entire set of elements as the
"grand" meet and join.
One might ask why the new terms "meet(x,y)" and "join(x,y)" are
needed, rather than just "lub(x,y)" and "glb(x,y)". Ease of saying the
terms out loud is all I can think of, though the pronunciation
"glub(x,y)" would eliminate that problem.
Let's apply meet and join to the set consisting of just two
elements:
SET 1 again:
x= (.2, .8)
y = (.7, .3)
Under the componentwise order, x and y can't be ranked.
Their join, though, is
JOIN (x,y) = (.7, .8)
This is the join because it is clearly greater than or equal
to both x and y. Similarly, the meet is (.2, .3).
If we added h= ( .1, .3) to the set, the join would be
unchanged at (.7,.8), but the meet would fall to h itself,
(.1, .3).
(4) DEFINING "LATTICE"
Now we are ready to define a lattice. The idea is
something like defining a closed and convex set of ordered
elements. Having done that, we'll be able to talk about
optimization on the lattice-- that is, about choosing the
very best element. To implement the idea, define a lattice
as:
A LATTICE is a set such that for every pair of elements x
and y in the set, Join(x,y) and Meet (x,y) are also elements
of the set.
In other words, a lattice is a set that includes its least upper and
greatest lower bounds, and that in a special sense does not have any
holes in it-- because it must include not only its grand meet and
join, but every other meet and join of its elements too. Note, too,
that there is an implicit requirement that the meets and joins all
exist. If the grand meet and join both exist, this requirement is met.
Let's apply the idea to our set of x and y:
SET 1 again (not a lattice):
x= (.2, .8)
y = (.7, .3)
The set {x, y} is not a lattice under the component-wise
ordering, because it does not include either its meet or its
join. We can make it into a lattice, though, by adding them:
SET 3 (a lattice):
x= (.2, .8)
y = (.7, .3)
MEET (x,y) = (.2, .3)
JOIN (x,y) = (.7, .8)
Now we have a lattice, consisting of four points. In a
special sense it does not have any holes in it, but only in
a special sense, since, after all, on a diagram it would be
4 unconnected dots.
Now let's add h, so we have
SET 4 (a lattice):
x= (.2, .8)
y = (.7, .3)
MEET (x,y) = (.2, .3)
JOIN (x,y) = (.7, .8)
h = (.1, .3).
Do we need to add any other points to keep our set a
lattice? The grand join hasn't changed. The grand meet has changed,
but adding h adds the grand meet automatically. But let's think about
the pairwise meets and joins:
MEET (x,h) = (.1, .3)
MEET (y,h) = (.1, .3)
JOIN (x,h) = (.2, .8)
JOIN (y,h) = (.7, .3)
We're OK there too.
Suppose, instead of adding h, we added a different point to
x and y:
SET 5 (not a lattice):
x= (.2, .8)
y = (.7, .3)
MEET (x,y) = (.2, .3)
JOIN (x,y) = (.7, .8)
m = (.6, .4)
The grand meet and join are unaffected, since m is an interior
point. But now to have a lattice we will need to add 4 other
pairwise meets and joins:
SET 6:
x= (.2, .8)
y = (.7, .3)
MEET (x,y) = (.2, .3)
JOIN (x,y) = (.7, .8)
m = (.6, .4)
MEET (x,m) = (.2, .4)
JOIN (x,m) = (.6, .8)
MEET (m,y) = (.6, .3)
JOIN (m,y) = (.7, .4)
Thus, the requirement that all pairwise meets and joins be
in the set (not just the grand meet and join) for it to be a lattice
has real bite.
How about checking for the pairwise meets and joins of the new points
we just added? (e.g, .2, .4) That isn't necessary-- we aren't going
to get anything new. Introducing the new point, m, introduced the two
new possibilities of z_1=.6 and z_2=.4 for set point z, but we already
have all combinations as set elements.
(5) DRAWING PICTURES OF LATTICES
Before going on to talk about sublattices, it will be useful to draw
some pictures of lattices. With 2-vectors, this seems easy, since we
are used to plotting points in 2-dimensional
space. But plotting is just as possible with more exotic set
elements too, though, because in lattice theory we're boiling all
relationships down to two things. The first thing is whether x and y
can be ranked at all. The second thing is whether x is greater than y
or less, if they can be ranked. Whether x and y themselves are 2-
dimensional or 7-dimensional, points, polygons, or functions, is
unimportant.
The way we will draw pictures is this. First, every element of the set
is represented by an open circle. We'll use an open circle so as not
to confuse elements with points, which they may or may not be,
depending on what set we're analyzing.
Second, if elements x, y, and z can be ranked in that order, we will
draw them with x higher than y and y higher than z. Also, we
will draw lines between x and y and y and z, but not directly between
x and z. The line between x and z is superfluous, given that our
ordering has the transitivity property, and this will reduce clutter.
If x and y are unrankable, we won't be concerned with which is higher,
and we won't have any line between them.
Formally, we say that if x y, we wouldn't be able to say *how much* bigger x was than y.
It was to make that point that I drew the distance in Figure (c) to be
longer than in Figure (b).
Next, look at how we would draw Set 3, in Figure (a). It has four
elements, and all but x and y can be ranked. (.2, .3) is smaller than
any other element, so it has to be drawn lowest. Notice that this
means it has to be lower than (.2,.8), contrary to how we draw things
in Euclidean space.
SET 3 again (a lattice):
x= (.2, .8)
y = (.7, .3)
MEET (x,y) = (.2, .3)
JOIN (x,y) = (.7, .8)
We don't draw a line segment between (.2, .3) and
(.7, .8), even though (.7, .8) is bigger, because (.7,.8) does not
cover (.2,.3). In between those two elements is (.2, .8), which is
bigger than (.2,.3) but not as big as (.7, .8). But by following the
line segment up and across from (.2,.3) to (.2, .8) to (.7, .8) the
diagram helps us see which is bigger.
We don't have to draw the lattice as a skewed rectangle-- that is just
the closest we can get it to look as it would in Euclidean space.
Instead, we could draw it as the diamond in Figure (b).
(6) SUBLATTICES.
The idea of a sublattice is like that of a subgame in game
theory: a subset that satisfies the requirements to be the same kind
of object as the original set.
A SUBLATTICE of lattice L consists of a subset S of L and the same
meet and join definitions as L, where S includes Meet(x,y) and
Join(x,y) for every pair of elements (x,y) in S.
Two key parts of the definition are that a sublattice is itself a
lattice and that a sublattice' set is a subset of the lattice's set.
Examples make this clearer. Set 3 above is a lattice, and it
is a sublattice of Set 6. I've starred the elements common to both:
SET 6 again:
*x= (.2, .8)
*y = (.7, .3)
*MEET (x,y) = (.2, .3)
*JOIN (x,y) = (.7, .8)
m = (.6, .4)
MEET (x,m) = (.2, .4)
JOIN (x,m) = (.6, .8)
MEET (m,y) = (.6, .3)
JOIN (m,y) = (.7, .4)
Set 7 below is also a sublattice of Set 6. Set 7 consists of just
the biggest elements of Set 6.
SET 7 (a sublattice of Set 6):
JOIN (x,y) = (.7, .8)
m = (.6, .4)
JOIN (x,m) = (.6, .8)
JOIN (m,y) = (.7, .4)
Of course, S is not a sublattice of L if its elements are a subset of
L's elements, but it uses a different partial ordering, a different
definition of "greater than or equal to". A more subtle, perhaps
pedantic point is that for S to be a sublattice of L, it is not
sufficient that (a) S is a subset of L, and (b) S is a lattice under
the partial order that makes L a lattice. We must also use the same
set of *possible* elements for calculating the meet and joins in L and
in S.
Consider Set 4 from above.
SET 4 again (a lattice):
x= (.2, .8)
y = (.7, .3)
MEET (x,y) = (.2, .3)
JOIN (x,y) = (.7, .8)
h = (.1, .3).
Set 8 below is a subset of Set 4, and it is a lattice if we say that
the universe of possible elements is only the elements actually in Set
8-- which notably excludes the point (.2, .3) from consideration as
a possible meet for x and y. But because it excludes (.2,.3), Set 8
is not a sublattice of Set 4.
SET 8 (a lattice and a subset of Set 4, but not a sublattice of Set
4):
x= (.2, .8)
y = (.7, .3)
JOIN (x,y) = (.7, .8)
h = (.1, .3).
This may make you wonder whether we did a bad job of defining
"lattice" in the first place. In allowing a lattice to be defined
using whatever universe of possible elements the analyst pleases to
choose, are we being so loose as to make anything into a lattice?
No. Think back to Set 1, which was not a lattice.
SET 1 again (not a lattice):
x= (.2, .8)
y = (.7, .3)
There is no way to define the universe of possible elements to make
Set 1 a lattice. The problem is that x and y can't be ranked, and
so neither one can be a least upper bound for the elements of the set.
It is only when you begin with a set that already has its grand meet
and join inside the set that fooling with the universe of possible
elements affects whether the set is a lattice or not.
(7) MISCELLANEOUS NOTES NOT FINISHED
Meet and join box in elements teling us what is gretaer and what is
lesser. We can't map every element to a single ordering,unless we have
a total ordering, so that is quite useful.
Burris has a completeness discussion.
Since lattices have the concept of BIGGEST and SMALLEST, they are
good for optimization.
A lattice can be an open set, and it does not have to include its
grand meet and join. The definition is a tricky one. Since it only
requires that the lattice set contain join (x,y) for every x and y,
the set can be open-- say, the set of real numbers less than 5. Any
two real numbers in that set have their join-- their maximum-- in the
set, but 5 is *not* in the set.
A *complete* lattice, on the other hand, is closed. It is defined in
terms of subsets' least upper bounds and greatest lower bounds, not
the bounds of pairs of points.
Another example of an incomplete lattice is the set of real numbers,
which does not include positive and negative infinity, its bounds. The
extended real numbers, on the other hand, is a complete lattice.
Why not then just say that a complete lattice is a closed lattice? --
because the idea of closed set is not defined on a lattice, perhaps.
In metric spaces it is defined using an epsilon distance, but here we
have no distance.
The PRODUCT ordering is suggestive of a payoff function. But if we
impose Antisymmetry, that rules out using a lattice to depict a set of
choices and a payoff function that orders them, since no ties are
allowed. In economics, the payoff from two consumption bundles is
often the
same.
A lot of the complications in lattices are due to the ordering not
being total. Why are lattices defined only using a partial ordering?
Probably because in many, perhaps most applications we really can't
rank every element. In economics, though, we can, if the ordering is
in size of payoffs.
What kind of space is the simplest in which convexity has meaning?
Metric spaces? Certainly Euclidean space has more properties than we
need.