Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

12.2: Lattices

( \newcommand{\kernel}{\mathrm{null}\,}\)

In this section, we restrict our discussion to lattices, those posets for which every pair of elements has both a greatest lower bound and least upper bound. We first introduce some notation.

Definition 12.2.1: Join, Meet

Let (L,) be a poset, and a,bL. We define:

  • ab, read “a join b”, as the least upper bound of a and b, if it exists. and
  • ab, read “a meet b”, as the greatest lower bound of a and b, if it exists.

Since the join and meet produce a unique result in all cases where they exist, by Theorem 13.1.1, we can consider them as binary operations on a set if they always exist. Thus the following definition:

Definition 12.2.2: Lattice

A lattice is a poset (L,) for which every pair of elements has a greatest lower bound and least upper bound. Since a lattice L is an algebraic system with binary operations and , it is denoted by [L;,]. If we want to make it clear what partial ordering the lattice is based on, we say it is a lattice under .

Example 12.2.1: The Power Set of a Three Element Set

Consider the poset (P(A),) we examined in Example 13.1.3. It isn't too surprising that every pair of sets had a greatest lower bound and least upper bound. Thus, we have a lattice in this case; and AB=AB and AB=AB. The reader is encouraged to write out the operation tables [P(A);,].

Our first concrete lattice can be generalized to the case of any set A, producing the lattice [P(A);,], where the join operation is the set operation of union and the meet operation is the operation intersection; that is, = and =.

It can be shown (see the exercises) that the commutative laws, associative laws, idempotent laws, and absorption laws are all true for any lattice. A concrete example of this is clearly [P(A);,], since these laws hold in the algebra of sets. This lattice also has distributive property in that join is distributive over meet and meet is distributive over join. However, this is not always the case for lattices in general.

Definition 12.2.3: Distributive Lattice

Let L=[L;,] be a lattice under . L is called a distributive lattice if and only if the distributive laws hold; that is, for all a,b,cL we have

a(bc)=(ab)(ac)anda(bc)=(ab)(ac)

Example 12.2.2: A Nondistributive Lattice

We now give an example of a lattice where the distributive laws do not hold. Let L={00,a,b,c,11}. We define the partial ordering on L by the set

{(00,00),(00,a),(00,b),(00,c),(00,11),(a,a),(a,11),(b,b),(b,11),(c,c),(c,11),(11,11)}

The operation tables for and on L are:

00abc110000abc11aaa111111bb11b1111cc1111c1111111111111100abc11000000000000a00a0000ab0000b00bc000000cc1100abc11

Since every pair of elements in L has both a join and a meet, [L;,] is a lattice (under divides). Is this lattice distributive? We note that: a(cb)=a00=a and (ac)(ab)=1111=11. Therefore, a(bc)(ab)(ac) for some values of a,b,cL. Thus, this lattice is not distributive.

Our next observation uses the term “sublattice”, which we have not defined at this point, but we would hope that you could anticipate a definition, and we will leave it as an exercises to do so.

It can be shown that a lattice is nondistributive if and only if it contains a sublattice isomorphic to one of the lattices in Figure 12.2.1. The ordering diagram on the right of this figure, produces the diamond lattice, which is precisely the one that is defined in Example 12.2.2. The lattice based on the left hand poset is called the pentagon lattice.

clipboard_ed6294eb14e1c07499d036e6ed2294341.pngFigure 12.2.1: Nondistributive lattices, the pentagon and diamond lattices

13.2.1: Exercises

Exercise 12.2.1

Let L be the set of all propositions generated by p and q. What are the meet and join operations in this lattice under implication? What are the maximum and minimum elements?

Exercise 12.2.2

Which of the posets in Exercise 13.1.3 are lattices? Which of the lattices are distributive?

Exercise 12.2.3

  1. State the commutative laws, associative laws, idempotent laws, and absorption laws for lattices.
  2. Prove laws you stated.

Exercise 12.2.4

Demonstrate that the pentagon lattice is nondistributive.

Exercise 12.2.5

What is a reasonable definition of the term sublattice?

Answer

One reasonable definition would be this: Let [L;,] be a lattice and let K be a nonempty subset of L. Then K is a sublattice of L if and only if K is closed under both and

Exercise 12.2.6

Let [L;,] be a lattice based on a partial ordering . Prove that if a,b,cL,

  1. aab.
  2. aba.
  3. ba and cabca.

This page titled 12.2: Lattices is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?