Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 14] ORDERED SETS AND LATTICES 347

Notice that the dual of each axiom of a lattice is also an axiom. Accordingly, the principle of duality holds;
that is:

Theorem 14.2 (Principle of Duality): The dual of any theorem in a lattice is also a theorem.

This follows from the fact that the dual theorem can be proven by using the dual of each step of the proof of
the original theorem.
An important property of lattices follows directly from the absorption laws.

Theorem 14.3 (Idempotent Law): (i)a∧a=a; (ii)a∨a=a.

The proof of (i) requires only two lines:

a∧a=a∧(a∨(a∧b)) (using( 3 b))

=a(using( 3 a))

The proof of (ii) follows from the above principle of duality (or can be proved in a similar manner).

Lattices and Order

Given a latticeL, we can define a partial order onLas follows:

a
b if a∧b=a

Analogously, we could define

a
b if a∨b=b

We state these results in a theorem.

Theorem 14.4: LetLbe a lattice. Then:

(i) a∧b=aif and only ifa∨b=b.

(ii) The relationa
b(defined bya∧b=aora∨b=b)is a partial order onL.

Now that we have a partial order on any latticeL, we can pictureLby a diagram as was done for partially
ordered sets in general.

EXAMPLE 14.10 LetCbe a collection of sets closed under intersection and union. Then(C,∩,∪)is a lattice.
In this lattice, the partial order relation is the same as the set inclusion relation. Figure 14-6 shows the diagram
of the latticeLof all subsets of{a, b, c}.

Fig. 14-6

We have shown how to define a partial order on a latticeL. The next theorem tells us when we can define a
lattice on a partially ordered setPsuch that the lattice will give back the original order onP.