Lattices
A Graph of a 3 Element Lattice
The figure to the
right is based on the power set (all possible subsets) of the
three element set {a, b, c}. These subsets form a special
kind of partial order that is referred to as a lattice.
Notice that the set at the top of the figure, U, consists of
all of the elements of the set. Sets D, E, and F are each in
the subset relation to U, (for example, every element of D is
an element of U; and so on. This subset relation is a basis for
partially ordering the sets. The sets D, E and F have
been placed below U and an arrow drawn from each of these sets
to the set U to represent the fact that they are ordered with
respect to U. Note that they are not ordered with respect to
each other. It is for this reason that we refer to this as a
partial order.
Notice further that the set A is a subset of D and
of E; B a subset of D and F and so on. Again the position and
the arrows indicate the ordering relations that hold under the
subset relation. Finally, at the bottom of the figure is the
empty set. It is ordered in the figure with respect to sets A,
B and C.
|
 |
|
 |
Axioms Defining
a Lattice
|
|
The figure above
describes the axioms that define a lattice. In our example, the
subset relation is the relation used to define the partial order.
The subset relation is, of course, a transitive relation and
this property is often exploited to simplify the representation
of a lattice. For example, if A is a subset of D, and D is a
subset of U, then A is a subset of U. The arrows representing
this transitivity are not shown in the figure. Graphs or diagrams
of partial orders that leave out the transitive relations are
referred to as a Hasse diagram.
Axioms 4 and 5 above
make a lattice is a special kind of partial order. For example,
consider first the operation of Union. Consider any pair of sets
in the diagram. The Union of the pair will always yield a set
which contains them both. For example, D Union E equals
U; A Union B equals D; and so on. (If one of the sets
precedes the other in the partial order, then the union yields
the set that occurs higher in the order. For example, A U D equals
D.) The set obtained under union is referred to as the Least
Upper Bound. Next consider the set operation of intersection.
Again consider any pair of sets in the diagram. For example,
D Intersection E equals A; A Intersection B equals
ø; and so on. The set obtained under intersection
is referred to as the Greatest Lower Bound for the pair.
|
| |
|
