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.