Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

19.1: Lattices

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

Partially Ordered Sets

We begin the study of lattices and Boolean algebras by generalizing the idea of inequality. Recall that a relation on a set X is a subset of X×X. A relation P on X is called a partial order of X if it satisfies the following axioms.

  1. The relation is reflexive: (a,a)P for all aX.
  2. The relation is antisymmetric: if (a,b)P and (b,a)P, then a=b.
  3. The relation is transitive: if (a,b)P and (b,c)P, then (a,c)P.

We will usually write ab to mean (a,b)P unless some symbol is naturally associated with a particular partial order, such as ab with integers a and b, or AB with sets A and B. A set X together with a partial order is called a partially ordered set, or poset.

Example 19.1

The set of integers (or rationals or reals) is a poset where

Solution

ab has the usual meaning for two integers a and b in Z.

Example 19.2

Let X be any set. We will define the power set of X to be the set of all subsets of X. We denote the power set of X by P(X). For example, let X={a,b,c}. Then

Solution

P(X) is the set of all subsets of the set {a,b,c}:

{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}.

On any power set of a set X, set inclusion, , is a partial order. We can represent the order on {a,b,c} schematically by a diagram such as the one in Figure 19.3.

clipboard_e1d09ee3865d3306295195b4aba0056b1.png

Figure 19.3. Partial order on P({a,b,c})

Example 19.4

Let G be a group. The set of subgroups of G is a

Solution

poset, where the partial order is set inclusion.

Example 19.5

There can be more than one partial order on a particular set. We can form a partial order on N by ab if ab. The relation is certainly reflexive since aa for all aN. If mn and nm, then

Solution

m=n; hence, the relation is also antisymmetric. The relation is transitive, because if mn and np, then mp.

Example 19.6

Let X={1,2,3,4,6,8,12,24} be the set of divisors of 24 with the partial order defined in Example 19.5.

Solution

Figure 19.7 shows the partial order on X.

clipboard_e099c47b3f4c6fc4ff388d9f18863e5bc.png

Figure 19.7. A partial order on the divisors of 24

Let Y be a subset of a poset X. An element u in X is an upper bound of Y if au for every element aY. If u is an upper bound of Y such that uv for every other upper bound v of Y, then u is called a least upper bound or supremum of Y. An element l in X is said to be a lower bound of Y if la for all aY. If l is a lower bound of Y such that kl for every other lower bound k of Y, then l is called a greatest lower bound or infimum of Y.

Example 19.8

Let Y={2,3,4,6} be contained in the set X of Example 19.6. Then

Solution

Y has upper bounds 12 and 24, with 12 as a least upper bound. The only lower bound is 1; hence, it must be a greatest lower bound.

As it turns out, least upper bounds and greatest lower bounds are unique if they exist.

Theorem 19.9

Let Y be a nonempty subset of a poset X. If Y has a least upper bound, then Y has a unique least upper bound. If Y has a greatest lower bound, then Y has a unique greatest lower bound.

Proof

Let u1 and u2 be least upper bounds for Y. By the definition of the least upper bound, u1u for all upper bounds u of Y. In particular, u1u2. Similarly, u2u1. Therefore, u1=u2 by antisymmetry. A similar argument show that the greatest lower bound is unique.

On many posets it is possible to define binary operations by using the greatest lower bound and the least upper bound of two elements. A lattice is a poset L such that every pair of elements in L has a least upper bound and a greatest lower bound. The least upper bound of a,bL is called the join of a and b and is denoted by ab. The greatest lower bound of a,bL is called the meet of a and b and is denoted by ab.

Example 19.10

Let X be a set. Then the power set of X, P(X), is a lattice. For two sets

Solution

A and B in P(X), the least upper bound of A and B is AB. Certainly AB is an upper bound of A and B, since AAB and BAB. If C is some other set containing both A and B, then C must contain AB; hence, AB is the least upper bound of A and B. Similarly, the greatest lower bound of A and B is AB.

Example 19.11

Let G be a group and suppose that X is the set of subgroups of G. Then

Solution

X is a poset ordered by set-theoretic inclusion, . The set of subgroups of G is also a lattice. If H and K are subgroups of G, the greatest lower bound of H and K is HK. The set HK may not be a subgroup of G. We leave it as an exercise to show that the least upper bound of H and K is the subgroup generated by HK.

In set theory we have certain duality conditions. For example, by De Morgan's laws, any statement about sets that is true about (AB) must also be true about AB. We also have a duality principle for lattices.

Axiom 19.12. Principle of Duality

Any statement that is true for all lattices remains true when is replaced by and and are interchanged throughout the statement

The following theorem tells us that a lattice is an algebraic structure with two binary operations that satisfy certain axioms.

Theorem 19.13

If L is a lattice, then the binary operations and satisfy the following properties for a,b,cL.

  1. Commutative laws: ab=ba and ab=ba.
  2. Associative laws: a(bc)=(ab)c and a(bc)=(ab)c.
  3. Idempotent laws: aa=a and aa=a.
  4. Absorption laws: a(ab)=a and a(ab)=a.
Proof

By the Principle of Duality, we need only prove the first statement in each part.

(1) By definition ab is the least upper bound of {a,b}, and ba is the least upper bound of {b,a}; however, {a,b}={b,a}.

(2) We will show that a(bc) and (ab)c are both least upper bounds of {a,b,c}. Let d=ab. Then cdc=(ab)c. We also know that

aab=ddc=(ab)c.

A similar argument demonstrates that b(ab)c. Therefore, (ab)c is an upper bound of {a,b,c}. We now need to show that (ab)c is the least upper bound of {a,b,c}. Let u be some other upper bound of {a,b,c}. Then au and bu; hence, d=abu. Since cu, it follows that (ab)c=dcu. Therefore, (ab)c must be the least upper bound of {a,b,c}. The argument that shows a(bc) is the least upper bound of {a,b,c} is the same. Consequently, a(bc)=(ab)c.

(3) The join of a and a is the least upper bound of {a}; hence, aa=a.

(4) Let d=ab. Then aad. On the other hand, d=aba, and so ada. Therefore, a(ab)=a.

Given any arbitrary set L with operations and , satisfying the conditions of the previous theorem, it is natural to ask whether or not this set comes from some lattice. The following theorem says that this is always the case.

Theorem 19.14

Let L be a nonempty set with two binary operations and satisfying the commutative, associative, idempotent, and absorption laws. We can define a partial order on L by ab if ab=b. Furthermore, L is a lattice with respect to if for all a,bL, we define the least upper bound and greatest lower bound of a and b by ab and ab, respectively.

Proof

We first show that L is a poset under . Since aa=a, aa and is reflexive. To show that is antisymmetric, let ab and ba. Then ab=b and ba=a. By the commutative law, b=ab=ba=a. Finally, we must show that is transitive. Let ab and bc. Then ab=b and bc=c. Thus,

ac=a(bc)=(ab)c=bc=c,

or ac.

To show that L is a lattice, we must prove that ab and ab are, respectively, the least upper and greatest lower bounds of a and b. Since a=(ab)a=a(ab), it follows that aab. Similarly, bab. Therefore, ab is an upper bound for a and b. Let u be any other upper bound of both a and b. Then au and bu. But abu since

(ab)u=a(bu)=au=u.

The proof that ab is the greatest lower bound of a and b is left as an exercise.


This page titled 19.1: Lattices is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Thomas W. Judson (Abstract Algebra: Theory and Applications) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?