|
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. We
have placed the sets D, E and F below U and drawn an arrow from
each of these set 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.
|
 |
|
Now
the subset relation is a transitive relation. That is, if A is
a subset of D, and D is a subset of U, then A is a subset of
U. We didn't bother to put arrows into the figure to reflect
this transitivity. Graphs or diagrams of partial orders that
leave out the transitive relations are referred to as a Hasse
diagram.
We
have mentioned that a lattice is a special kind of partial order,
and now it is time to illustrate this claim. 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.
If
every pair of elements in the partial order have a unique Least
Upper Bound and a unique Greatest Lower Bound; than the partial
order is said to form a lattice. In this example shown here,
the elements of the partial order are sets and the ordering relation
is subset.
|