Operations on Sets 29"x A y = y A x Commutative Law for Meet
"x V y = y V x Commutative Law for Join
"x A (y A z) = (x A y) A z Associative Law for Meet
"x V (y V z) = (x v y) V z Associative Law for Join
"x A (x V y) = x Absorption Law for Meet
"x V (x A y) = x Absorption Law for Join
To say that something is a lattice, we must explicitly say (i) what the set of objects
is and (ii) what the meet and join operations are. After specifying these, we must show
that meet and join so interpreted satisfy all the required axioms. Meet and join can be any
operations on the set so long as the axioms are satisfied. The operations of meet and join can
be as simple as union and intersection defined on a set of sets. Whatever the operations are
defined to be, however, the first task is to show that the operations satisfy the Commutative
and Associative Laws.
Example 11. Let X be a set, and let L = P(X). Let join be defined as the union of two
subsets of X and meet as the intersection of two subsets of X. Then, L together with union
and intersection is a lattice.Solution. By Theorems 1 and 2 in Section 1.3.1, the Commutative and Associative Laws
hold. To prove that the Absorption Law holds, we use the result of Theorem 5 in Section
1.3.1. EThe next example shows that the interpretation of meet and join can be rather different
from unions and intersections.Example 12. Let X C _R. Let meet be defined as the minimum of two elements of X and
join as the maximum of two elements of X. Then, X together with the minimum and the
maximum operations is a lattice.
Solution. The Commutative Law for Meet in this context says that the minimum of two
real numbers is the same regardless of the order in which you consider the elements. The
remainder of the Commutative and Associative Laws for Meet and Join are straightforward
to verify. The Absorption Law for Meet says that the minimum of an element x together
with the maximum of the two elements x and y where y is any other element is just x.
This just says that either x is the minimum of {x, x} or the minimum of Ix, y} where
y > x. In either case, the result follows. The remaining details are left as Exercise 21 in
Section 1.4. U
There are two additional properties that are used to distinguish different kinds of lat-
tices. The first of these laws, the Distributive Law, is familiar in the context of union and
intersection.
Definition 11. Let X with the operations meet (A) and join (v) be a lattice. X is a dis-
tributive lattice if the following two properties are satisfied for all x, y, z G X: